Hard | Probability |

On pressing a button, a random number is generated uniformly between 0 & 1. You keep on generating these numbers until their sum exceeds 1. What is the probability that you need to press the button more than n times? What is the expected number of times you need to press the button?

Hint

Probability by conditioning

Answer

Probability: 1/n! ; Expected times: e

Solution

Probability of more than n throws is equivalent to saying X1+..+Xn <=1, this is the volume of n dimensional symplex from origin, its volume is 1/n! and can be proved by induction. This can be used to calculate expected number of button presses, sum( 1/n! * n ) = sum( 1/(n-1)!) = e^1

Otherwise, set up a (lag)differential equation for f(x), the expected number of draws needed for the sum to exceed x. For x=0,f(x)=1. For x>0, suppose a draw gave number t, then f(x)= 1 + integral (t=0 to x)f(x-t)dt, which is same as f(x) = 1 + integral(t=0 to x) f(t)dt, differentiate wrt x, we get f'(x) = 0 + f'(x). This has the solution f(x)=e^x and x=1 gives e.

To take derivative, we used leibniz integral rule:

d/dx ( integral( a(x) to b(x) ) f(t) dt = f(b(x))*b'(x) - f(a(x))*a'(x) = f(x)*1 - f(x)*0 = f(x)

Otherwise, set up a (lag)differential equation for f(x), the expected number of draws needed for the sum to exceed x. For x=0,f(x)=1. For x>0, suppose a draw gave number t, then f(x)= 1 + integral (t=0 to x)f(x-t)dt, which is same as f(x) = 1 + integral(t=0 to x) f(t)dt, differentiate wrt x, we get f'(x) = 0 + f'(x). This has the solution f(x)=e^x and x=1 gives e.

To take derivative, we used leibniz integral rule:

d/dx ( integral( a(x) to b(x) ) f(t) dt = f(b(x))*b'(x) - f(a(x))*a'(x) = f(x)*1 - f(x)*0 = f(x)

Hard | Probability |

You are initially located at origin in the x-axis. You start a random walk with equal probability of moving left or right one step at a time. What is the probability that you will reach point a before reaching point -b? What is the expected number of steps to reach either a or -b? (a,b are natural numbers)

Answer

b/(a+b) and ab

Solution

If you try markov chain approach, this question will never end! For this problem, we will use Martingales.

Let N = number of steps to reach any of a or -b. Let SN = X1+...+XN. Suppose Pa = probability of touching a before -b, and Pb = the opposite. We use the fact that both SN and (SN^2-N) are martingales, thus:

0 = E(SN) = a*Pa + (-b)*Pb

This gives Pa = b/(a+b)

Similarly, 0 = E(SN^2-N) = Pa*a^2 + Pb*b^2 - E(N)

This gives E(N) = ab

Let N = number of steps to reach any of a or -b. Let SN = X1+...+XN. Suppose Pa = probability of touching a before -b, and Pb = the opposite. We use the fact that both SN and (SN^2-N) are martingales, thus:

0 = E(SN) = a*Pa + (-b)*Pb

This gives Pa = b/(a+b)

Similarly, 0 = E(SN^2-N) = Pa*a^2 + Pb*b^2 - E(N)

This gives E(N) = ab

Source: Top Quant Interview

Enable Like and Comment Hard | Probability |

You are taking out candies one by one from a jar that has 10 red candies, 20 blue candies, and 30 green candies in it. What is the probability that there are at least 1 blue candy and 1 green candy left in the jar when you have taken out all the red candies? (Candies of same color are indistinguishable!)

Hint

Combinatorial problem. Consider a sequence of 60 candies, in which red candies finish before blue and green.

Answer

7/12

Solution

It can be done using combinatorics as well as conditional probability. I don't have time today, but please remind me to put proper solution by commenting down below or by sending me a message. Thank you.

Medium | Probability |

A & B are alternately picking balls from a bag without replacement. The bag has k black balls and 1 red ball. Winner is the one who picks the red ball. Who is more likely to win, the on who starts first, or second?

Hint

Look at k=0,1,2,3... Write down probability of starter being a winner.

Answer

Begin!

Solution

A & B keep on picking the balls without looking at their color. After all balls have been picked, the one who starts the game will have more balls (if k=even, total balls=odd) and hence higher probability of winning.

Solution by Palak Bhushan:

(prob of A winning in first chance = 1/(k+1)) +

(prob of A winning in 3rd chance = (1-(1/k+1))*(1-1/k)*1/(k-1) = 1/(k+1)) + ... +

(prob of A winning in 2r+1-th chance = 1/(k+1)) + ... .

When k=2n+1, there are n+1 such terms, giving the prob as (n+1)*1/(k+1)=1/2.

When k=2n, there are n+1 such terms, giving prob as (n+1)*1/(k+1)=(n+1)/(2n+1)>1/2.

Hence, doesnt matter who starts first when k is odd.

The first player has higher chance of winning when k is even

Solution by Palak Bhushan:

(prob of A winning in first chance = 1/(k+1)) +

(prob of A winning in 3rd chance = (1-(1/k+1))*(1-1/k)*1/(k-1) = 1/(k+1)) + ... +

(prob of A winning in 2r+1-th chance = 1/(k+1)) + ... .

When k=2n+1, there are n+1 such terms, giving the prob as (n+1)*1/(k+1)=1/2.

When k=2n, there are n+1 such terms, giving prob as (n+1)*1/(k+1)=(n+1)/(2n+1)>1/2.

Hence, doesnt matter who starts first when k is odd.

The first player has higher chance of winning when k is even

Source: 40 Puzzles

Enable Like and Comment Medium | Probability |

A postman brought N letters to a house with two letter-boxes. Since the two boxes were empty, he puts 1 mail in each of the two mail boxes. Then he chooses one of boxes with probability proportional to number of letters present in that box, and puts the 3rd letter in it. He does this for all subsequent letters. What is the expected number of letters in the box with lower letters?

Hint

This can be made equivalent to randomly splitting a deck of n cards into two parts. (n>2)

Solution

Suppose I have a stack of 2 black cards and one red card. Initially I put red between 2 black cards. Now I add black cards randomly between any two cards (so, initially it is either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be: if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent.

Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest box contains n/2 letter or 1 letter (or any number of letters between 1 and n/2) are all same. So, expected number of letters in the smaller box is asymptotically n/4

Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest box contains n/2 letter or 1 letter (or any number of letters between 1 and n/2) are all same. So, expected number of letters in the smaller box is asymptotically n/4

Source: P. Winkler

Enable Like and Comment Latest solved Puzzles

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

© BRAINSTELLAR |