Sequence A181784, Related to a Game of Chance

This problem originated in China in 2005 or earlier (see [4]), and made it to me via the My Math Forum (see [2] and [1]). 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/2⁹ = 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/2¹³ = 11/4096 to the odds of losing.

Continuing in a similar manner gives a series sum:

1/2 + 1/2⁵ + 4/2⁹ + 22/2¹³ + 140/2¹⁷ + 969/2²¹ + 7084/2²⁵ + 53820/2²⁹ + 420732/2³⁴ + 3782992/2³⁸ + ...

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 [2], 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

[1] Math Forums, "I give, duz... what is it?" (discussion thread), 2008 Oct 10 (formerly at "My Math Forum", www.mymathforum.com/viewtopic.php?f=38&t=4629&start=0)

[2] "duz", Random Walking (blog post) 2008 Sep 23 (archived on 2010 Dec 21). The original at zdu.spaces.live.com/blog/cns!C95152CB25EF2037!127.entry is now gone.

[3] 数学研发网 (Mathematics Research and Development Network), Probability issues in random walks, forum discussion, 2008 Apr 10.

[4] "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-scissors¹, 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"

Sequence A181784, Related to a Game of Chance

See Also