Sequence A181784, Related to a Game of Chance
This problem originated in China in 2005 or earlier (see ), and made it to me via the My Math Forum (see  and ). I noticed it because a reader had tried to solve part of the problem with RIES.
Consider the following game of chance:
- Flip a coin. If you get heads, your score increases by π, if you get tails, your score diminishes by 1.
- Repeat as many times as you wish but if your score ever goes negative, you lose.
Assuming the player keeps playing indefinitely (motivated by the temptation of getting an ever-higher score), what are the odds of losing?
No matter how high the score gets, it is always possible to lose eventually. To compute the odds, one could set up a computer program to check every combination of heads and tails. It is a little more efficient to enumerate just the ways of losing than to try to trace out all the possibilities.
An initial tails leads to a loss, and that will happen in 1/2 of the games.
The next most common type of loss is a heads followed by four tails in a row: HTTTT, which happens 1/32 of the time.
Two heads and seven tails will cause a loss, and that can happen in a bunch of ways that do not cause an earlier loss by the aforementioned 1/2 and 1/32 cases:
HHTTTTTTT HTHTTTTTT HTTHTTTTT HTTTHTTTT
for a contribution of 4/29 = 1/128.
Similarly, three heads and ten tails will cause a loss. For this to happen (without an earlier loss in the ways already mentioned) requires that the first flip and one of the following 4 flips be heads, along with any other flip out of the first 9:
HHHTTTTTT HTHHTTTTT HTTHHTTTT HTTTHHTTT
HHTHTTTTT HTHTHTTTT HTTHTHTTT HTTTHTHTT
HHTTHTTTT HTHTTHTTT HTTHTTHTT HTTTHTTHT
HHTTTHTTT HTHTTTHTT HTTHTTTHT HTTTHTTTH
HHTTTTHTT HTHTTTTHT HTTHTTTTH
for 7+6+5+4=22 possibilities, adding 22/213 = 11/4096 to the odds of losing.
Continuing in a similar manner gives a series sum:
1/2 + 1/25 + 4/29 + 22/213 + 140/217 + 969/221 + 7084/225 + 53820/229 + 420732/234 + 3782992/238 + ...
which gives the answer to 6 figures after about a day of computation: 0.543643... The numerators of this series are Sloane's A181784:
1, 1, 4, 22, 140, 969, 7084, 53820, 420732, 3782992, 32389076, 275617830, 2350749914, 20140518790, 173429992350, 1500850805160, 14550277251918, 133009333771170, 1198324107797254, ...
The denominators are all powers of 2, and the exponents of 2 are:
1, 1+ceil(π)=5, 2+ceil(2π)=9, 3+ceil(3π)=13, 4+ceil(4π)=17, ...
where ceil(x) is the "ceiling" function, giving the least integer c such that c≥x. This sequence (1, 5, 9, 13, 17, 21, 25, 29, 34, 38, 42, 46, 50, 54, ...) is N plus A004084(N).
A more sophisticated analysis can be done to produce exact answers for games in which the reward for heads is a rational number (see , which summarizes the work from the Chinese sites). Using a series of fractions that converge on π (including such fractions as 355/113), this method converges on the answer more quickly than the preceding method can, giving us 0.54364331210052407755147385529445...
Here is a rough translation of the problem as originally stated:
A and B start at the same place. Using rock-paper-scissors1, A wins to advance 1 meter, B wins to advance π meters (they move in the same direction) until B is [sufficiently far in front] of A. Find the probability that A will ever walk in front of B.
1. Literally, "finger-guessing game"