Probability puzzles
| 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 | 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 Latest solved Puzzles
Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level
| © BRAINSTELLAR |