How Many Times on Average?
A common type of questions which appears on Quant Interviews is:
“You have a sequence of random variables. How many times on average does a certain outcome appear in this sequence?”
Here are a few examples:
- You are throwing a coin 100 times. How many times will you encounter the Heads-Heads-Tails in this sequence?
- Five husbands and five wives have sat around a circle table in random order. What is the average number of spouses which are sitting next to each other?
While such problems can be solved using induction, there is another, more elegant approach. It is based on the following observation:
The average number of successful events is equal to the sum of the probabilities that each of these events is successful. The events do NOT need to be independent.
Written mathematically, this translates to:
\mathbb{E}(\|\{X_i = 1, 1 \leq i \leq n \}\|) = \mathbb{E}(\sum_{i=1}^{n} X_i) = \sum_{i=1}^{n} \mathbb{E}(X_i) = \sum_{i=1}^{n}\mathbb{P}(X_i =1),where X_i is a random variable, such that X_i=1 if the i-th event is successful X_i = 0 otherwise.
- The first equation follows from the definition of X_i.
- The second equation follows from linearity of expectation.
- The third equality is a basic property of expectation.
Let us see how to apply this technique to solve the coin question posed above.
We define a random variable X_i which is equal to 1 if and only if coin tosses i, i+1, i+2 are Tails-Tails-Heads respectively. We have:
\mathbb{E}(\|\{X_i=1, 1\leq i \leq 100\}\|) = \sum_{i=1}^{100}\mathbb{P}(X_i=1)It is easy to see that for each 1\leq i \leq n, X_i = \frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}=\frac{1}{8}. Therefore, the answer to the problem is 100\times \frac{1}{8}=12.5.
To solve the second problem, we define a random variable X_i which is equal to 1 if and only a husband and his wife are sitting on spots i and i+1 around the table. For each i the probability of this happening is equal to \frac{1}{9}. Indeed, no matter who sits on spot i, the chance that their spouse sits on spot i+1 is 1:9. Therefore, the average number of spouses sitting next to each other is:
\mathbb{E}(\|\{X_i=1, 1\leq i \leq 10\}\|) = \sum_{i=1}^{10}\mathbb{P}(X_i=1)=10\times\frac{1}{9}=1\frac{1}{9}As we can see, the presented technique is a simple, but very powerful tool. For extra practice, try to solve this fun puzzle from our blog on your own:
