Fifty Challenging Problems

2 Successive Wins¶

prize if win (at least) 2 sets in a 3-set series to be played with father or champion
father-champion-father
champion-father-champion
middle set is the most important

3 Flippant Juror (DONE)¶

correct decision of 3-man jury
CC = $p^2$
CWH = $p * (1-p) * 0.5 * 2$
Correct decision = $p^2 + p * (1-p) * 0.5 * 2 = p$

4 Trials until First Success¶

Finite Geometric Series: $S_n = a + ar + ar^2 + \ldots + ar^{n-1} = a \cdot \frac{1-r^n}{1-r}$

Infinite Geometric Series: $S_n = a + ar + ar^2 + \ldots = \frac{a}{1-r}$

On average, how many times must a die be thrown until one gets a 6?

$m = 1$ if success on first try. when first toss fails, mean number required is $1+m$. therefore total mean, $m = p(1) + (1-p)(1 + m) = 1 + qm$

5 Coin in square¶

penny is 3/4 inch in diameter
expected cost is 1 cent, profit is 5 cents

6 Chuck-a-kuck¶

three dices rolled. player bet on 6 numbers. If number appears on 1/2/3 of dice, payed 1/2/3 respectively of stake + money back.

Dice Questions¶

Expected Sum of Two Dice Roll two fair dice. What is the expected value of the sum?

$E[X_1 + X_2] = E[X_1] + E[X_2] = 7$

Expected Rolls to Get a 6 or a 5 Roll a die until you get a 5 or a 6. How many rolls on average?

3 rolls. $E[X] = 3$
Success probability per roll: $p = \frac{2}{6} = \frac{1}{3}$
Geometric: $E[X] = \frac{1}{p} = 3$

Expected Rolls Until Two Consecutive 6s Roll a die until you get two 6s in a row. What's the expected number of rolls?

State recursion. Let $E_0$ = expected rolls with no streak, $E_1$ = expected rolls with one 6 already.
$E_0 = 1 + \frac{1}{6}E_1 + \frac{5}{6}E_0$
$E_1 = 1 + \frac{5}{6}E_0$
Solving, $E_0 = 42$

Expected Rolls Until Every Face Has Appeared (Coupon Collector): Roll a die until all six faces have shown at least once. Expected number of rolls?

geometric recursion with n unique heads

Strictly Increasing Order of Dices You roll 3 fair six-sided dice. Conditioned on all three dice showing distinct values, what is the probability that the rolls are in strictly increasing order?

1/6 since 6 distinct ways of arranging values, but only 1 is distinct

Probability of Rolling a 6 Before a 7 (with two dice) Roll two dice repeatedly. What's the probability that a sum of 6 appears before a sum of 7?

Ignore all other outcomes. $P(6) = \frac{5}{36}$, $P(7) = \frac{6}{36}$.
Conditional on the race ending: $P = \frac{P(6)}{P(6) + P(7)} = \frac{5/36}{5/36 + 6/36} = \frac{5}{11}$

Expected Rolls Until a 6, Given You Roll Until a 6 or a 1 Roll a die until you get a 6 or a 1. If it's a 6 you win. What's the probability you win?

The 6 and 1 are equally likely and the game always ends on one of them.
$P(\text{win}) = \frac{1}{2}$

You roll a fair six-sided die repeatedly until either: you roll a 6, or you have rolled three odd numbers in total. What is the probability that the game ends because you roll a 6 first?

$p(6 \mid 1,2,3,4) = 1/4$. $p(2,3,4 \mid 1,2,3,4) = 3/4$
$p(\text{6 first}) = 1 - p(\text{3 odd rolls in a row}) = 1 - (3/4)^3 = 37/64$

Coin Flip Questions¶

Expected Flips Until First Heads Flip a fair coin. How many flips on average until you get a heads?

Geometric. $p=1/2$, $E[X] = 1/p = 2$

Expected Flips Until Two Consecutive Heads Flip a fair coin until you get two heads in a row. Expected number of flips?

State recursion. Let $E_0$ = expected flips with no streak, $E_1$ = expected flips with one head already.
$E_0 = 1 + \frac{1}{2}E_1 + \frac{1}{2}E_0$
$E_1 = 1 + \frac{1}{2}(0) + \frac{1}{2}E_0 = 1 + \frac{1}{2}E_0$
Solving, $E_0 = 6$

Expected Flips Until a Head AND a Tail Flip a fair coin until you've seen at least one head and one tail. Expected flips?

geometric recursion with n unique heads.
First flip is always new (1 flip). Then you need the other side, which appears with probability $\frac{1}{2}$ per flip (geometric, mean 2).
$E = 1 + 2 = 3$
Probability of More Heads Than Tails (n flips) Flip a fair coin $n$ times. What's the probability of getting more heads than tails?
By symmetry, for odd $n$: $P(\text{more heads}) = \frac{1}{2}$
For even $n$, there's a tie possibility: $P(\text{more heads}) = \frac{1 - P(\text{tie})}{2}$, where $P(\text{tie}) = \binom{n}{n/2}\left(\frac{1}{2}\right)^n$

First to Reach 3 Heads Wins (vs Tails) Two players flip a fair coin repeatedly. Player A wins when 3 heads appear, Player B when 3 tails appear. What's the probability A wins?

By symmetry, $\frac{1}{2}$. The game always ends and the roles are symmetric.

Win on Head vs Tail-Tail Flip a fair coin until you get a head (win) or two tails in a row (lose). What's the probability you win?

State recursion. Let $P_0$ = win prob with no current tail, $P_1$ = win prob with one tail already.
$P_0 = \frac{1}{2}(1) + \frac{1}{2}P_1$
$P_1 = \frac{1}{2}(1) + \frac{1}{2}(0) = \frac{1}{2}$
$P_0 = \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}$

Expected Flips (Head vs Tail-Tail) Same game as above. What's the expected number of flips?

$E_0 = 1 + \frac{1}{2}E_1$ (flip head → win, flip tail → $E_1$)
$E_1 = 1$ (flip head → win, flip tail → lose; both end)
Solving, $E_0 = 1.5$

Head Before Two Tails (biased coin) Flip a coin with $P(H) = p$ to get a head until you get a head or two tails. What's the probability you get a head first?

You lose only if the first two flips are both tails.
$P(\text{win}) = 1 - (1-p)^2$
For a fair coin: $P(\text{win}) = 1 - \frac{1}{4} = \frac{3}{4}$

Card Questions¶

Expected Number of Aces in 5 Cards Draw 5 cards from a deck. What's the expected number of aces?

Let $X_i$ = indicator that card $i$ is an ace, each with $P = \frac{4}{52} = \frac{1}{13}$.
$E[X] = 5 \cdot \frac{1}{13} = \frac{5}{13}$

Expected Draws Until an Ace Draw cards one at a time (without replacement) until you draw an ace. What's the expected number of draws?

4 Aces create 5 gaps. Each gap is 48 / 5.
$E[X] = 48/5 + 1 = 53/5$

Probability of a Full House Draw 5 cards. What's the probability of a full house (3 of one rank, 2 of another)?

$P = \frac{13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2}}{\binom{52}{5}} = \frac{13 \cdot 4 \cdot 12 \cdot 6}{\binom{52}{5}} = \frac{3744}{2598960} \approx 0.00144$

Probability of a Flush Draw 5 cards. What's the probability of a flush (all same suit)?

$P = \frac{4 \cdot \binom{13}{5}}{\binom{52}{5}} = \frac{4 \cdot 1287}{2598960} \approx 0.00198$

Expected Draws Until You've Seen All 4 Suits Draw cards one at a time (without replacement) until you've seen all four suits. Expected number of draws?

Coupon collector without replacement. Expected draws to get the $k$-th new suit, with $k-1$ seen, is $\frac{52-(k-1)}{13(4-(k-1))}$.
$E = \frac{52}{52} + \frac{51}{39} + \frac{50}{26} + \frac{49}{13} \approx 1 + 1.31 + 1.92 + 3.77 = 8$

Brain Teasers¶

Series¶

Coupon Collector¶

If there are n distinct types of coupons (or outcomes) and each draw gives you 1 uniformly at random, how many draws on average until you've collected at least one of every type?

General solution-With Replacement

you have 0 types. first draw is always new
you have 1 type, now $n-1$ types are new. each draw is new with probability $\frac{n-1}{n}$. geometric with mean $\frac{n}{n-1}$
stage $k$: you have $k-1$ types. there are $n - (k-1)$ types left, so each draw is $\frac{n-(k-1)}{n}$, with mean $\frac{n}{n-(k-1)}$.
$E[X] = \sum_{k=1}^n \frac{n}{n - (k-1)} = n (1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n}) = n \cdot H_n$
Die: $E = 6(1 + \frac{1}{2} + \ldots \frac{1}{6}) \approx 14.7$
Coin: $ E = 2 (1 + \frac{1}{2}) = 3$
Geometric mean: How many trials required for success?
intuitively, by LLN, 6 rolls to hit 1 instance of trial
generalizing, with probability $p$ success and $q = 1-p$ as failure, you need $m$ more on average, so $1+m$. $m=p(1) + q(1 + m) = 1 + (1-p)m = \frac{1}{p}$

general solution - without replacement

$E[X] = \sum_{k=1}^n \frac{N - (k-1) + 1}{m (n - (k-1)) + 1}$