Probability - Puzzle Prime

How Many Times on Average?

Section: School Category: Quant Interview

Tags: Probability

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:

Puzzle February 16, 2024

0 Comments

Fish Eat Fish

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced Tags: Probability

A hundred fish are swimming along a stream at different velocities. If one fish catches up to another fish, it eats it and continues swimming. What is the expected number of fish that will survive?

SOLUTION

Notice that the N-th fish in the stream survives if and only if it is the fastest among the first N fish. The probability of this event happening is equal to 1/N. Since the expected number of fish that survive is equal to the sum of the survival probabilities for each of them, the answer is 1+1/2+1/3+…+1/N.

For more details on the last claim, consider reading our blog post “How Many Times on Average?”

Unknown Author February 7, 2024

0 Comments

The Die Game

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced Tags: Probability

You pick a number between 1 and 6 and keep throwing a die until you get it. Does it matter which number you pick for maximizing the total sum of the numbers in the resulting sequence?

In the example below, the picked number is 6 and the total sum of the numbers in the resulting sequence is 35.

SOLUTION

No matter what number you pick, the expected value of each throw is the average of the numbers from 1 to 6 which is 3.5. The choice of the number also does not affect the odds for the number of throws until the game ends, which is 6. Therefore, the total sum is always 3.5 × 6 = 21 on average, regardless of the chosen number.

Unknown Author December 7, 2022

7 Comments

FEATURED

Population

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced Tags: Featured, Probability

In certain society all parents stop having children right after they get their first boy. After 1000 years, approximately what will be the percentage of the women in the society?

SOLUTION

The answer is 50%. The reason is that no matter what birth plan the society comes up with, the chance for having a boy or a girl during every birth is 50/50.

Unknown Author May 7, 2022

0 Comments

FEATURED

The Monty Hall Show

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced Tags: Featured, Probability

You are in Monty Hall’s TV show where in the final round the host gives you the option to open one of three boxes and to receive the reward inside. Two of the boxes contain just a penny, while the third box contains $1.000.000. In order to make the game more exciting, after you pick your choice, the rules require the host to open one of the two remaining boxes, such that it contains a penny inside. After that he asks you whether you want to keep your chosen box or to switch it with the third remaining one. What should you do?

SOLUTION

This is the so called “Monty Hall” problem. The answer is that in order to maximize your chances of winning $1.000.000, you should switch your box. The reason is that if initially you picked a box with a penny, then after switching you will get a box with $1.000.000. If initially you picked a box with $1.000.000, then after switching you will get a box with a penny. Since in the beginning the chance to get a penny is 2/3, then after switching your chance to get $1.000.000 is also 2/3. If you stay with your current box, then your chance to get $1.000.000 will be just 1/3.

Unknown Author April 10, 2022

0 Comments

FEATURED

Gun Duel

Section: Brain Teasers Category: Mathematics

Difficulty: Advanced Tags: Featured, Probability

Mick, Nick, and Rick arrange a three-person gun duel. Mick hits his target 1 out of every 3 times, Nick hits his target 2 out of every 3 times, and Rick hits his target every time. If the three are taking turns shooting at each other, with Mick starting first and Nick second, what should be Mick’s strategy?

SOLUTION

Clearly, Mick should not aim for Nick, because if he kills him, then he will be killed by Rick. Similarly, Nick should not aim for Mick, because if he kills him, then he also will be killed by Rick. Therefore, if Rick ends up against alive Mick and Nick, he will aim at Nick, because he would prefer to face off a weaker opponent afterward. This means that if Nick is alive after Mick shoots, he will shoot at Rick.

Thus, if Mick shoots at Rick and kills him, then he will have to face off Nick with chance of survival less than 1/3. Instead, if he decides to shoot in the air, then he will face off Nick or Rick with chance of survival at least 1/3. Therefore, Mick’s strategy is to keep shooting in the air, until he ends up alone against one of his opponents.

Unknown Author January 16, 2022

4 Comments

Envelopes with Numbers

Section: Brain Teasers Category: Mathematics

Difficulty: Hard Tags: Probability

You are given 2 sealed envelopes with numbers inside. You are told that one of the numbers is twice as much as the other one. You grab one of the envelopes and right before you open it, you make the following calculation:

“If this envelope contains X inside, then the other envelope contains either X/2 or 2X inside. Since the chance that the other envelope contains a larger number is exactly 50%, the expected money I will get after switching is X/4 + X = 1.25X > X. Therefore, I should switch!”

Clearly, this reasoning is wrong, since you can’t possibly deduce which envelope of the two contains a larger number. Where is the mistake?

SOLUTION

The trick is that conditionally on the fact that your envelope contains X, it is not true that the other envelope has 50% chance of containing either X/2 or 2X. The reason is that it is impossible that all amounts of dollars appear in the envelopes with the same probabilities (densities). Thus, for example, if it is very unlikely that an envelope contains more than 1000, and you open an envelope with 800 inside, you will not think that the other envelope has 50% chance of containing 1600.

Unknown Author October 10, 2021

5 Comments

Fish in a Pond

Section: Brain Teasers Category: Mathematics

Difficulty: Expert Tags: Probability

There are 5 fish in a pond. What is the probability that you can split the pond into 2 halves using a diameter, so that all fish end up in one half?

SOLUTION

Let us generalize the problem to N fish in a pond. We can assume that all fish are on the boundary of the pond, which is a circle, and we need to find the probability that all of them are contained within a semi-circle.

For every fish Fᵢ, consider the semi-circle Cᵢ whose left end-point is at Fᵢ. The probability that all fish belong to Cᵢ is equal to 1/2ᴺ⁻¹. Since it is impossible to have 2 fish Fᵢ and Fⱼ, such that the semi-sircles Cᵢ and Cⱼ contain all fish, we see that the probability that all fish belong to Cᵢ for some i is equal to N/2ᴺ⁻¹.

When N = 5, we get that the answer is 5/16.

Unknown Author August 10, 2021

3 Comments

Moms’ Talk

Section: Brain Teasers Category: Mathematics

Difficulty: Hard Tags: Probability

Two moms, Sarah and Courtney, are talking to each other.

Sarah: I have two children.
What is the probability that both of Sarah’s children are boys?

Courtney: Me too! Do you have any boys?
What is the probability that both of Courtney’s children are boys?

Sarah: Yes, I do! What is your younger child?
What is the probability that both of Sarah’s children are boys?

Courtney: It is a boy. He is so mischievous!
What is the probability that both of Courtney’s children are boys?

Sarah: Is he Sagittarius? Sagittarius boys are known to drive their mothers crazy. I can testify from personal experience.
What is the probability that both of Sarah’s children are boys?

Courtney: No, but actually I have the opposite personal experience to yours.
What is the probability that both of Courtney’s children are boys?

Sarah: Well, I guess astrology does not always get it right.

Courtney: I assume it does about half of the time.

SOLUTION

The answers are: ~1/4, ~1/4, ~1/3, ~1/2, ~23/47, 1.

Explanation:

Initially, we do not have any information about the children and therefore the chance that both of them boys is 1/2 × 1/2. This applies to the first and the second question.

After Sarah says that she has at least one boy, there are equal possibilities that she has Boy + Boy, Boy + Girl, or Girl + Boy. Therefore, the chance that both children are boys is 1/3.

After Courtney says that her younger child is a boy, the only remaining question is what is the gender of her older child, and therefore the chance is 1/2.

The fifth exchange implies that Sarah has a Sagittarius boy. There are 23 combinations such that both children are boys and at least one of them is Sagittarius. There are 47 combinations such that at least one of the children is a Sagittarius boy. Therefore, the chance that both children are boys is 23/47.

Finally, Courtney says that her younger child, which is a boy, is not Sagittarius, but her personal experience with Sagittarius boys is positive. Therefore, her older child is a Sagittarius boy and the chance is 1.

Puzzle Prime July 28, 2019

4 Comments

Royal Wedding

Section: Brain Teasers Category: Mathematics

Difficulty: Expert Tags: Probability

A prince decides to get married to the prettiest girl in his kingdom. All 100 available ladies go to the palace and show themselves to the prince one by one. He can either decide to marry the girl in front of him or ask her to leave forever and call the next one in line. Can you find a strategy which will give the prince a chance of 25% to get married to the prettiest girl? Can you find the best strategy?

Remark: Assume that the prince can objectively compare every two girls he has seen.

SOLUTION

A strategy which ensures a chance of 25% is the following:
The prince banishes the first 50 girls which enter the palace and then gets married to the first one which is prettier than all of them (if such one arrives). If the prettiest girl in the kingdom is in the second 50, and the second prettiest girl is in the first 50, he will succeed. The chance for this is exactly 25%.

The best strategy is to wait until ~1/e of all girls pass, and then choose the first one which is more beautiful than all of them. This yields a chance of ~37% for succeeding. The proof is coming soon.

Unknown Author April 19, 2019

0 Comments