A Multi-Computational Exploration of Some Games of Pure Chance

by Thotsaporn Aek Thanatipanonda and Doron Zeilberger

.pdf   .ps   .tex  

Posted: Sept. 25, 2019.
[Published in J. of Symbolic Computation 104 (2021), 38-68.]

In the spirit of "multi-culturalism", we use four kinds of computations: simulation, numeric, symbolic, and "conceptual" to explore some "games of pure chance" inspired by children board games like "Snakes and Ladders" (aka as "Chutes and Ladders") and "gambler's ruin with unlimited credit". Even more interesting than the many computer-generated actual results described in this paper and its web-site extension, is our broad-minded, ecunemical approach, not favoring, a priori, any one of the above four kinds of computation, but showing that, a posteriori, symbolic computation is the most important one, since (except for simulation, that is very inaccurate) numerics can be made more efficient with the help of symbolics (in the "downward" direction), and, (in the "upward" direction) the mere existence of certain symbolic-computational algorithms imply interesting "qualitative" results, that certain numbers are always rational, or always algebraic, and certain sequences are always polynomial, or C-recursive, or algebraic, or holonomic. This article is accompanied by four Maple packages, and numerous input and output files, that readers can use as templates for their own investigations.

Added Feb. 24, 2020: The editor in charge of this submission, Manuel Kauers, used three referees. Two of them understood our paper, but one of them completely misunderstood both the content and the "big picture". Here is our response .

Added June 11, 2020: Here is a proof of Prop. 17

The problem can be thought as starting at m >=0, find the expected number of rounds until reaching location 0 or less (two steps back or one step forward with 1/2 chance each). Denote this number by g(m).

We see that g(m) satisfies the recurrence relation g(m) = 1+1/2*g(m-2)+1/2*g(m+1) for m >=1 or equavalently g(m) = 2*g(m-1)-g(m-3)-2, m >=2.

With the initial conditions g(-1)=g(0)=0 and g(1)=1+sqrt(5) (that was already proved in chapter 3 using generating function), we have that g(m) and f(m) where f(m) := 2*m+(4-2*phi)+2*(fibonacci(m+2)*phi-fibonacci(m+3)), satisfy the same initial conditions and recurrence relation. Hence g(m)=f(m) for all m>=-1.

Maple packages

Sample Input and Output Files for SnakesAndLadders.txt

Sample Input and Output Files for PosPileGames.txt

Sample Input and Output Files for GenPileGames.txt

Sample Input and Output Files for VGPileGames.txt