4

I've worked out the result to a basic coin flipping problem and want to generalize it.

The basic problem is: there are N players, and they take turns of flipping a coin (in the same cyclical order) until the first person to get 1 heads wins. Coin is not necessarily fair so give it probability p of Heads. The answer I worked out is as follows. Say P(m) represents the probability that player m (of the N players) wins. Then:

$$ P(m) = \frac{(1-p)^{m-1}p}{1-(1-p)^{N}} $$ This is because for player m to win, the m-1 preceding players must get tails with probability (1-p). It also uses the convergence formula for the sum of a geometric series.

----------------------------------------------------------------------------

Now my question is how to generalize this from: "winning"= first person to get 1 Heads, to "winning"= first person to get K heads? In other words, players take turns (in the same order as before) of flipping a coin a single time. Once all the players have flipped, then as before, the cycle repeats from player 1. But this time, the winner is the first person to get K heads (not necessarily in a row) before anyone else gets K heads. I'm having difficulty because the tree of possibilities expands very quickly. For instance, I'd be happy to at least see the derivation for the case of K=2.

sambajetson
  • 645
  • 1
  • 5
  • 16
  • 2
    interesting question. for now I can only say that as $k$ gets bigger and bigger we should get $p(m)$ to converge to $\frac {1}{N}$...as it clear the first player advantage is shrinking as $k$ is larger. – d_e Jun 17 '16 at 19:16

1 Answers1

1

Turns out it's not too bad. The probability that player m wins, when winning is defined as getting k good flips of the coin, is just a combination of 3 conditions:

P(player m wins) = ${\sum_{T=k}^{\infty}(C_1)\cap(C_2)\cap(C_3)}$, meaning it's the sum of the probability that player m wins in exactly k turns + P(m wins in k+1 turns), ... P(m wins in infinity turns). And for a given k, P(m wins in k turns) requires 3 independent conditions.

$C_1$: player m gets $\leq{(k-1)}$ good flips in T-1 turns, and good flip on turn T:

${T-1 \choose k-1}p^{k-1}(1-p)^{(T-1)-(k-1)}p={T-1 \choose k-1}p^{k}(1-p)^{T-k}$

$C_2$: all the players preceding player m do not win, i.e. they get anywhere from 0 to k-1 good flips. This means player 1 gets 0,1,..., or k-1 good flips over T turns AND player 2 gets 0,1,..., or k-1 good flips over T turns, ..., AND player m-1 gets 0,1,..., or k-1 good flips over T turns:

for just player 1: ${\sum_{i=0}^{i=k-1}{T \choose i}p^{i}(1-p)^{T-i}}$

Each player's coin flips are independent, so for all m-1 players, $C_2$ is: $[{\sum_{i=0}^{i=k-1}{T \choose i}p^{i}(1-p)^{T-i}}]^{m-1}$

$C_3$: players m+1 to N all have 1 fewer turn since player m has won the game. So in their T-1 turns, players m+1 to N must have gotten anywhere from 0 to k-1 good flips. Each player is independent, so: $[{\sum_{j=0}^{j=k-1}{T-1 \choose j}p^{j}(1-p)^{T-j}}]^{N-m}$

So, finally, combining all 3 conditions: P(m)= ${\sum_{T=k}^{\infty}{T-1 \choose k-1}p^{k}(1-p)^{T-k}}[{\sum_{i=0}^{i=k-1}{T \choose i}p^{i}(1-p)^{T-i}}]^{m-1}[{\sum_{j=0}^{j=k-1}{T-1 \choose j}p^{j}(1-p)^{T-j}}]^{N-m}$

sambajetson
  • 645
  • 1
  • 5
  • 16