Medium | Probability |

What is the expected number of coin tosses required to get n consecutive heads?

Hint

That sum wont work! Just find the recursive relation.

Answer

En = 2En−1 + 2, giving En = 2^(n+1)-2

Solution

Define let Xn = number of tosses to get n consecutive heads; E(Xn) = expected number of coin tosses we require from now on, to get n consecutive heads. Recall the law of total probability,

E(Xn) = E ( E(Xn) |Y) )

where Y = current toss (either Head or tail).

En = (1/2)( E(Xn) | H) + (1/2)( E(Xn) | T)

En = (1/2)( E(X(n-1)) + 1 |H) + (1/2)( E(Xn) + 1 | T)

the extra 1 is because we just used a toss

En = 1 + (1/2)*E(n-1) + (1/2)*En

This above equation is logical and should be written directly.

=> En = 2E(n-1) + 2

This simplifies to 2^(n+1)-2 as E0 = 0. (not required)

E(Xn) = E ( E(Xn) |Y) )

where Y = current toss (either Head or tail).

En = (1/2)( E(Xn) | H) + (1/2)( E(Xn) | T)

En = (1/2)( E(X(n-1)) + 1 |H) + (1/2)( E(Xn) + 1 | T)

the extra 1 is because we just used a toss

En = 1 + (1/2)*E(n-1) + (1/2)*En

This above equation is logical and should be written directly.

=> En = 2E(n-1) + 2

This simplifies to 2^(n+1)-2 as E0 = 0. (not required)

Source: Top Quant Interview

Enable Like and Comment Medium | Probability |

A chess tournament has K levels and 2^K players with skills 1 > 2 > ... >2^K. At each level, random pairs are formed and one person from each pair proceeds to next level. When two opponents play, the one with better skills always wins. What is the probability that players 1 and 2 will meet in the final level?

Hint

Consider K=1 (2 players), the probability is 1.

Consider K=2 (4 players); first round can be in following ways:

1-2 | 3-4

1-3 | 2-4

1-4 | 2-3

They don't meet in finals in first case (of 3). Thus, for K=2, the probability that they meet is 2/3.

I assure you that this probability gets close to 1/2 for large K. Just notice that if 1 and 2 meet before final, they dont meet at final.

Consider K=2 (4 players); first round can be in following ways:

1-2 | 3-4

1-3 | 2-4

1-4 | 2-3

They don't meet in finals in first case (of 3). Thus, for K=2, the probability that they meet is 2/3.

I assure you that this probability gets close to 1/2 for large K. Just notice that if 1 and 2 meet before final, they dont meet at final.

Answer

N/2(N-1)

Solution

If you worked out conditional probability, that is fine. Here we present the combinatorial solution. Imagine the levels proceed in any random way such that player X and Y appear for final level. This can be imagined as N players getting partitioned into two groups of N/2 players each, with player X topping in first group and player Y in second. The best player of each partition reaches final. We only need to ensure that above partition separates player 1 from 2. The probability that a random partition separates 1 & 2 is (N/2) / (N-1) (how?)

Here is how: for creating a partition to separate them, we pick (N/2) people from N, wishing to take player 1, but not player 2.

Here is how: for creating a partition to separate them, we pick (N/2) people from N, wishing to take player 1, but not player 2.

Medium | Probability |

A coin is tossed 10 times and the output written as a string. What is the expected number of HH? Note that in HHH, number of HH = 2. (eg: expected number of HH in 2 tosses is 0.25, 3 tosses is 0.5)

Hint

Recursion

Solution

Let the expected number of HH for n tossed is E(n). So, probability that an (n-1) toss experiments, ends in T is 1/2.

So, E(n) = 1/2*E(n-1) + 1/2*( 1/2*(E(n-1)+1) + 1/2*(E(n-1)))

(The first case when it ends in T. & The second case when it ends in H.

In the second case, if you get an H then, you get 1 more HH. )

So, E(n) = E(n-1) + 1/4, us E(2) = 1/4

So, E(n) = (n-1)/4

For n=10, E(10) = 2.25

So, E(n) = 1/2*E(n-1) + 1/2*( 1/2*(E(n-1)+1) + 1/2*(E(n-1)))

(The first case when it ends in T. & The second case when it ends in H.

In the second case, if you get an H then, you get 1 more HH. )

So, E(n) = E(n-1) + 1/4, us E(2) = 1/4

So, E(n) = (n-1)/4

For n=10, E(10) = 2.25

Source: Placement Test

Enable Like and Comment Medium | Probability |

The stick drops and breaks at a random point distributed uniformly across the length. What is the expected length of the smaller part?

Solution

The probability that the break point belongs to first half is 1/2. In this case, the expected length of the small part is L/4. Its L/4 in the other case too. Hence E = 1/2*L/4 + 1/2*L/4 = L/4

Source: Quant Interview

Enable Like and Comment Medium | Strategy |

100 prisoners are lined up and assigned a random hat These hats are available in 10 different unique and distinguishable colors. Each prisoner can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be the color like "red" or "blue" or "green" etc. If the word matches their hat color they are released, if not, they are killed on the spot. They can hear each others answers, no matter how far they are on the line. What strategy should be used to help release maximum number of prisoners?

Hint

Try prisoner's Hat puzzle first

Solution

Call the first person in back of row the 100th prisoner. The 10 colours will be given codes from 0 to 9. The 100th prisoner will sum the numbers associated with the 99 colours he sees and will say the colour corresponding to it modulo 10. This is enough for 99th person. All he needs to do now is connect the dots, sum the number of hats he can see, calculate modulo 10, and compare it with what 100th prisoner said. This way all 99 prisoners will be saved, and 100th prisoner dies with probability 9/10.

Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |