Hard | Probability |

What is the expected number of cards that need to be turned over in a regular 52-card deck in order to see the first ace?

Hint

Hint: the locations of the four aces in the deck divide it into the five groups X1, ...,X5.

Answer

53/5

Solution

Define X1,X2…X48, such that Xi = 1 if ith card turns over before 4 aces, 0 otherwise. Thus, total number of cards turned to see first ace = 1 + sum (Xi)

using linearity of expectation, E(X) = 1 + sum ( E(Xi))

Now consider the ith card and the four aces, all the orders are equally likely: X,A,A,A,A Or A,X,A,A,A, or 3 others. They are equally likely when we have no knowledge about position of these Aces with respect of the deck. Hence we have 5 equally likely slots for ith card: 1 A 2 A 3 A 4 A 5. We are interested in 1st slot.

Hence E(Xi) = 1/5 for all i = 1 to 48

Thus E(X) = 1 + 48/5 = 53/5 = 10.6

This can be done by recursive equation f(n) = (4/n)*1 + ((n-4)/n)*(1+f(n-1), where f(n)=expected cards to flip in a deck of n cards, but I definitely can't solve this without a computer.

A shorter explanation is to consider the 52 cards uniformly distributed over (0,1), so on average they're at k/53 for k=1,2,3,…,52. The four aces are on average at 1/5, 2/5, 3/5, 4/5. So 0.2=k/53 implies k=10.6, done!

using linearity of expectation, E(X) = 1 + sum ( E(Xi))

Now consider the ith card and the four aces, all the orders are equally likely: X,A,A,A,A Or A,X,A,A,A, or 3 others. They are equally likely when we have no knowledge about position of these Aces with respect of the deck. Hence we have 5 equally likely slots for ith card: 1 A 2 A 3 A 4 A 5. We are interested in 1st slot.

Hence E(Xi) = 1/5 for all i = 1 to 48

Thus E(X) = 1 + 48/5 = 53/5 = 10.6

This can be done by recursive equation f(n) = (4/n)*1 + ((n-4)/n)*(1+f(n-1), where f(n)=expected cards to flip in a deck of n cards, but I definitely can't solve this without a computer.

A shorter explanation is to consider the 52 cards uniformly distributed over (0,1), so on average they're at k/53 for k=1,2,3,…,52. The four aces are on average at 1/5, 2/5, 3/5, 4/5. So 0.2=k/53 implies k=10.6, done!

Hard | Probability |

x & y are two random points selected uniformly between 0 & 1. Using them, create a point uniformly random in circle of radius 1. (uniform means that the probability density is constant)

Hint

Suppose x & y are outcomes of blackbox. [ x*cos(2 pi y) , x* cos(2 pi y) ] is not a uniform point on disc. Neither is the point (x,y)/sqrt(x^2+y^2) uniform.

Solution

theta = 2pi*x and r = squareroot(y). the take the point as (r*cos(theta),r*sin(theta))

Explanation:

The idea is that the probability of a point to be between r and r+dr is 2pi*r*dr. Hence to choose a radius we need to generate a number from random number generator which follows probability distribution 2*r.To generate random number which follows above probability distribution which follows uniform distribution we simply take the square root of the number generated by uniform distribution.

Explanation:

The idea is that the probability of a point to be between r and r+dr is 2pi*r*dr. Hence to choose a radius we need to generate a number from random number generator which follows probability distribution 2*r.To generate random number which follows above probability distribution which follows uniform distribution we simply take the square root of the number generated by uniform distribution.

Source: Quant Interview

Enable Like and Comment Hard | Probability |

N points are chosen at random on the cicumference of a circle. A convex n-gon (n sided polygon) is drawn by joining these n points. What is the probability that the center of circle lies inside the region of n-gon?

Solution

Source: a nice senior

Enable Like and Comment 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 Latest solved Puzzles

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

© BRAINSTELLAR |