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
HHTTTTTHT   HTHTTTTTH
HHTTTTTTH

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 cx. 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...

Footnotes

 My Math Forum, discussion thread, 2008 Oct 10

 "duz", Random Walking (blog post) 2008 Sep 23

 "East corner", the probability of the strong[er] man out of [[game, i.e. eliminated]] (forum posting), 2005 Sep 21 (in Han Simplified Chinese)

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"

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2019 Jan 05. s.11