Here we go again. Perhaps the only product of china which is lasting for even more than a year. Stay at home, as they are saying and the message has not yet changed after an year. Forgetting my PIN number when the supermarket checkout asked me to pay through my ATM was one of those moments when I was happy to admit the grey matter has let me down.
But wait a minute our loved ones are only a text or FaceTime away. The saviour of all the crap in our head for now again is the Instagram stories. Parents will definitely say that their kids in this childhood 2.0 are finding the social networking sites equally playable as playgrounds were there in their times back in 90s. And with all the debates I know we are going to arrive on the very old slang of parents “Instagram pe bohat time waste ho rha hai bacchon ka”(too much time is wasted on Instagram). I have a solution to this. Lemme help all of you with some maths.
I am not a nerd, I just am a well wisher.
The Problem Statement :
Let the given child has N friends and the child wants to check the Instagram stories of all his friends (ya ya including girlfriends/boyfriends if any). And at each time your child opens up instagram he/she has equal chances of seeing any one of his/her friend’s story. But these n friends can upload any number of stories. So what is the minimum number of times a child has to login to Insta till he/she checks the stories of all his/her friends. Note-we are assuming that the friends are uploading at least one story.
Since we are dealing with randomness, a natural first question to ask is about the expected number of Logins child needs to do.
To compute this expectation, for every i = 1, …, N, we define the random variable Xᵢ as follows. X₁ is equal to the number of Logins child needs to do until he/she sees the story of 1st friend. Clearly, we always have X₁ = 1. We continue with X₂, which is equal to the number of additional Logins child needs to do (not counting the X₁ Logins we have already counted) until he/she sees story of two distinct friends. Similarly, X₃ is equal to the number of additional Logins child needs to do (not counting the X₁+X₂ ) ) until he/she sees story of three distinct friends, and so on.
Let’s clarify this a bit with an example. Suppose N = 3, and here is a sequence of Logins child needs to do where N represents the name of the friends like 1,2,3,…,N , one by one, from left to right
1, 1, 3, 1, 3, 3, 2.
In the above example, we have X₁ = 1, since a child always discovers a new friend in the first Login. Then, the second Login shows the story of the friend number 1, which he/she has already seen . The child continues Logins for the third time, and now he/she sees the story of the friend number 3. Thus, X₂ = 2, since the child has to Login for two more time in order to see the story of his new friend. We continue and we see that the child has to Login four more time in order to encounter the Insta story of a new friend , namely friend number 2. Thus, X₃ = 4. In total, Child is ending up with X₁+X₂+X₃ = 7 Logins in order to encounter the Insta stories of all his/her friends. We conclude that, given the above definition of random variables, the total number of Logins the child needs to do is
So, the goal now is to compute the expected value of the random variable X, which describes the sum of the random variables Xᵢ, for i = 1, …, N. To do so, we will use an extremely useful property of the expected value, which is called Linearity of Expectation. This implies that
Thus, the main task now is to compute E[X]ᵢ, for i = 1, …, N. We start with X₁. As we discussed, we always have X₁ = 1, and so we get that E[X₁] = 1.
We continue with X₂. Since the child has already seen the Insta story of one of his friend after one Login (it does not matter who is that friend), the probability seeing the Instagram story of a new friend in the next Login of the child is (N-1)/N. This is because the only way that the child is are not getting a new friend is when the new login makes the story of the same friend available whom we saw for the first time.
By assumption, each new choice independently makes ith friend available with probability 1/N. This means that the random variable X₂ has a geometric distribution with probability of success (N-1)/N. We will not go into details about the geometric distribution. The only property we need from the geometric distribution is that its expected value is 1/“probability of success”, and so we conclude that
Continuing in a similar way, for the variable Xᵢ, the probability of success when the child encounters a new friend is exactly equal to 1-(i-1)/N= (N-i+1)/N, since we already have seen i-1 distinct friends before . Thus, its expected value is
Putting everything together, we get that
Which is equal to the Number of friends ‘N’ times the nth harmonic number
Was it cool. Well it depends if you have been reading me with all your senses without yawning. Will the Number of logins be Infinity if the Number of friends tends to infinity? Think about it..
Until Next Blog stay crazy stay safe