2
$\begingroup$

A game master tells his party of players that he has converted to the school of minimalism, and is going to do away with all of his dice in the campaigns they play from now on. In the place of dice, a single fair coin will now be used to resolve random events.

Say the game master decides that he wants his players to undergo a trial with probability of failure $k / 1000$, where $k$ is an integer between $1$ and $999$. He will engage a (potentially very long) sequence of coin flips: the first coin flip is worth $500$ if it comes up heads, and nothing if it comes up tails; similarly, the second coin flip is worth $250$; the third flip is worth $125$; the fourth flip is worth $62.5$, and so forth. If the sum of all the values won through heads meets or exceeds $k$, the players succeed in the trial. The game master aborts the coin flips as soon as success is guaranteed or made impossible.

For example, suppose a player attempts to scale a fence while drunk. A 67.1% chance of failure sounds fair to the game master. He proceeds to flip the coin repeatedly, coming up heads, tails, heads, tails, heads, heads. This corresponds to $500 + 125 + 31.25 + 15.625 = 671.875 \geq 671$, so the player succeeds.

As another example, a player wants to win a coin flip in-game. A 50.0% chance of failure is, of course, only natural. The game master flips the coin and it comes up tails. Now, even if the coin were to forever come up heads every single time afterward, it would result in a sum $250 + 125 + 62.5 + \dots$ that would never reach $500$ in a finite number of terms. The game master calls it, and the player fails.

Assuming $k$ is chosen uniformly randomly for each trial, how many coin flips can the players expect per trial?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

665/333.

Alternate description of algorithm for most probabilities: 1) Write the probability as an infinite binary decimal. 2) As you flip coins, write "1" for a head and "0" for a tail. 3) As soon as the two sequences disagree, choose success or failure depending on last flip.

At each time, there is one flip that stops the algorithm (p=1/2), and one where it continues in the same state (p=1/2). On average this takes 2 flips to complete.

Exceptions are when the fraction terminates (125, 250, 375, 500, 625, 750, 875), then the algorithm will always finish in a finite number of flips. k=500 always takes 1 flip. k=250 and k=750 have a 50% chance of finishing on the first flip, and will finish on the second if they reach it. E = (1/2)*1 + (1/2)*2 = 1.5 k=125, 375, 625, 875 will finish on the third flip, if they reach it. E = (1/2)*1 + (1/4)*2 + (1/4)*3 = 1.75 For the other 992 values of k, E=2

Overall, E = (1*1 + 2*1.5 + 4*1.75 + 992*2)/999 = (1 + 3 + 7 + 1984)/999 = 1995/999 = 665/333

$\endgroup$
3
  • $\begingroup$ Suppose $k=500$. A head terminates the game, but a tail will only terminate the game as soon as we flip another tail. The expected number of flips is thus $\sum_{n=1}^{\infty}n\cdot\frac{1}{2^n}=\frac{1}{2}\cdot\frac{1}{\left(1 - \frac{1}{2}\right)^2}=2$. $\endgroup$
    – mintmocha
    Apr 29 at 11:24
  • $\begingroup$ @mintmocha The example in the question clearly states that, in this case, we do not continue flipping. For $k=500$, there will always be only one flip. $\endgroup$ Apr 29 at 12:34
  • $\begingroup$ @DanielMathias I see. That's my bad. $\endgroup$
    – mintmocha
    Apr 29 at 16:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.