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 .

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

• SnakesAndLadders.txt

• PosPileGames.txt

• GenPileGames.txt

• VGPileGames.txt

Sample Input and Output Files for SnakesAndLadders.txt

• If you want to see the list of length 99 whose i-th entry is the rational function in t whose coefficient of tⁿ (in its Maclaurin expansion) is the probability of a Solitaire "Chutes and Ladders" (American version, manufactured by Winning Moves Games) ending after n moves, lasting if you are currently at position i
  The input gives you the output.

• If you want to see the list of length 99 whose i-th entry is the rational function in t whose coefficient of tⁿ (in its Maclaurin expansion) is the probability of a Solitaire "Traditional Snakes and Ladders" (manufactured by Cardinal Industries) ending after n moves, if you are currently at position i
  The input gives you the output.

• If you want to see a computer-generated article about a very simple "Snakes and Ladders games" where there are neither snakes nor ladders, and at each move you can advance either one or two moves (both with probability 1/2) and you finish as soon as you reach 30 or 31
  The input gives you the output.

• If you want to see a computer-generated article about a very simple "Snakes and Ladders games" where there are 50 squares, and at each move you advance 1 with probability 1/3 and 2 with probability 2/3 where there is one chute (snake) from position 6 to 3, and one ladder from position 8 to 15,
  The input gives you the output.

• If you want to see a computer-generated article about the actual Chutes and Ladders game manufactured by Winning Moves Games
  The input gives you the output.

• If you want to see a computer-generated article about the actual Snakes and Ladders game manufactured by Cardinal Industries
  The input gives you the output.

Sample Input and Output Files for PosPileGames.txt

• If you want to see an article about the random variable (expectation, variance, etc.) "number of donors" that a beggar needs until he has at least n dollars, and each donor donates one dollar with probability 1/2 and two dollars with probability 1/2
  The input gives you the output.

• More generally, if you want to see an article about the random variable (expectation, variance, etc.) "number of donors" that a beggar needs until he has at least n dollars, and each donor donates one dollar with probability p and two dollars with probability 1-p, for arbitrary p (between 0 and 1)
  The input gives you the output.

• If you want to see an article about the random variable (expectation, variance, etc.) "number of donors" that a beggar needs until he has at least n dollars, and each donor donates 1, 2, 3, 4, 5, 6 dollars each with probability 1/6
  The input gives you the output.

• If you want to see an article about the random variable (expectation, variance, etc.) "number of donors" that a beggar needs until he has at least n cents, and each donor donates a penny, a nickel, a dime, or a quarter, each with probability 1/4
  The input gives you the output.

• More generally, if you want to see an article about the random variable (expectation, variance, etc.) "number of donors" that a beggar needs until he has at least n cents, and each donor donates a penny with probability p1, a nickel with probability p5, a dime with probability p10, and a quarter with probability 1-p1-p5-p10, in terms of the symbols p1,p5,p10,
  The input gives you the output.

• More generally, if you want to see an article about the random variable (expectation, variance, etc.) "number of donors" that a beggar needs until he gets n cents, if each donor gives 1,2, ..., k, cents, each with probability 1/k, for general k (as well, as of course, n) [These are, up to exponentially small terms, polynomials in n but rational functions in k]
  The input gives you the output.

• If you want to see an article about the sequence a(n), the probability of the first player winning if each, independently take 1 or 2 tokens each with probability 1/2, and the first player to gather n chips is declared the winner
  The input gives you the output.
  [Note that the linear recurrence is of order 4.]

• More generally, if you want to see an article about the sequence a(n), the probability of the first player winning if each, independently take 1 or 2 tokens each with probability p and 1-p respectively, and the first player to gather n chips is declared the winner
  The input gives you the output.
  [Note that the linear recurrence is of order 4.]

• If you want to see an article about the sequence a(n), the probability of the first player winning if each, independently take 1 or 2 or 3 tokens each with probability 1/3 each, and the first player to gather n chips is declared the winner
  The input gives you the output.
  [Note that the linear recurrence is of order 10.]

• If you want to see an article about the sequence a(n), the probability of the first player winning if each, independently take 1 or 2 or 4 tokens each with probability 1/2,1/4,1/4 respectively each, and the first player to gather n chips is declared the winner
  The input gives you the output.
  [Note that the linear recurrence is of order 20.]

Sample Input and Output Files for GenPileGames.txt

• If you want to see a computer-generated article about the random variable (expectation, variance, etc.) "number of coin-tosses needed until you accumulate n dollars", if at each coin toss you win a dollar with probability p and lose a dollar with probability 1-p (where p>1/2, to make sure that you achieve that goal with probability 1)
  The input gives you the output.

• More generally, if you want to see a computer-generated article about the random variable (expectation, variance, etc.) "number of coin-tosses needed until you accumulate n dollars",if at each coin toss you win a dollar with probability p and lose k dollars with probability 1-p (where p>k/(k+1), to make sure that you achieve that goal with probability 1)
  The input gives you the output.

• If you want to see a computer-generated article about the random variable (expectation, variance, etc.) "number of coin-tosses needed until you accumulate ONE dollar", if at each coin toss you LOSE 1 dollar with probability p and WIN 2 dollars with probability 1-p (where p<2/3, to make sure that you achieve that goal with probability 1). You get algebraic expression in terms of the symbol p.
  The input gives you the output.

• Consider a game where players take turns tossing a fair coin and at each step either move left or right one unit (each with probability 1/2), and whoever reaches the location m first is declared the winner. What can you say about the probability of the first player winning the game? It is (1+f(m))/2, where f(m) satisfies a certain second-order (inhomogeneous) linear recurrence equation that enables (found using the amazing Zeilberger algorithm), that enables you to compute many terms efficiently once you know, thanks to Maple, that
  f(1)=1-Pi/4, f(2)=5 -16/Pi
  
  The input gives you the output.

• Consider a game where players take turns and at each turn move one unit to right with probability p and move k units to the left with probability 1-p and whoever reaches the location m first is declared the winner, for various k and various NUMERIC p (>=k/(k+1)) What can you say about the probability of the first player of winning the game? Using the amazing Zeilberger algorithm you can find a linear recurrence equation that enables you to compute many terms efficiently once you computed the few initial conditions.
  The input gives you the output.

• Consider a game where players take turns and at each turn move one unit to right with probability p and move k units to the left with probability 1-p and whoever reaches the location m first is declared the winner, where p is SYMBOLIC and assumed that (>k/(k+1)), so the game is guaranteed to terminate. What can you say about the probability of the first player of winning the game? Using the amazing Zeilberger algorithm you can find a linear recurrence equation that enables you to compute many terms efficiently once you computed the few initial conditions.
  • For the case k=1:
    The input gives you the output.

  • For the case k=2:
    The input gives you the output.

  • For the case k=3:
    The input gives you the output.

  • For the case k=4:
    The input gives you the output.

  • For the case k=5:
    The input gives you the output.

• If you want to see 4 computer-generated articles demonstrating the numerical procedures NS and ProbAheadN
  The input gives you the output.

Sample Input and Output Files for VGPileGames.txt

• • If you want to see statistical analysis of a certain gambling game where at each round you lose a dollar with probability 1/4, lose two dollars with probability 1/8, win one dollar with probability 1/4 and win 2 dollars with probability 3/8
    The input gives you the output.

  • If you want to see statistical analysis of a certain gambling game where at each round you lose a dollar with probability 1/8, lose two dollars with probability 1/8, win one dollar with probability 1/4 and win 2 dollars with probability 1/2
    The input gives you the output.

  • If you want to see the probability generating function of the random variable `number of rounds until the FIRST time of having at least one dollar', for the gambling game where at each round you lose a dollar with probability 1/4, lose two dollars with probability 1/4, win one dollar with probability 1/4 and win 3 dollars with probability 1/4
    The input gives you the output.

• If you want to see several other computer-generated articles about games inspired by gambler's ruin with unlimited credit, for various dice, using exact formulas
  The input gives you the output.

• If you want to see 100 computer-generated propositions about games inspired by gambler's ruin with unlimited credit, for various dice, using approximate, but very reliable, computations, using symbolic computations
  The input gives you the output.

• If you want to see 45 computer-generated propositions about games inspired by gambler's ruin with unlimited credit, for various kinds of coins using approximate, but very reliable, computations, using symbolic computations
  The input gives you the output.

• If you want to see 47 propositions about enumerating walks with various sets of steps, that start and end at the x-axis, and never go above it, using Bryan Ek's algorithm re-implemented here
  The input gives you the output.

• If you want to see many propositions about enumerating walks with various 2-element sets of steps, one positive and one negative, that start and end at the x-axis, and never go above it, using Bryan Ek's algorithm re-implemented here
  The input gives you the output.

• If you want to see the first 40 terms of 215 sequence about enumerating walks with various sets of steps, that start and end at the x-axis, and never go above it
  The input gives you the output.

• If you want to see the first 40 terms of 19 sequence about enumerating walks with all 2-element sets of steps, one positive, one negative, {-a,b}, for 1<=a The input gives you the output.

• • If you want to see the numerical algorithm in action, to compute, and then (if possible) identify the expected duration of the "One Step Back with probability p and Two Steps Forward with probability 1-p" game until reaching for the first time >=n0 dollars for 1<=n0<=10
    The input gives you the output.

  • If you want to see the numerical algorithm in action, to compute, and then (if possible) identify the expected duration of the "One Step Back with probability p and Two Steps Forward with probability 1-p" game until reaching for the first time >=n0 dollars for 1<=n0<=10
    with p=1/2,
    The input gives you the output.

  • If you want to see the numerical algorithm in action, to compute, and then (if possible) identify the expected duration of the "One Step Back with probability p and Two Steps Forward with probability 1-p" game until reaching for the first time >=n0 dollars for 1<=n0<=10 with p=1/3,
    The input gives you the output.

  • If you want to see the numerical algorithm in action, to compute, and then (if possible) identify the expected duration of the "One Step Back with probability p and Two Steps Forward with probability 1-p" game until reaching for the first time >=n0 dollars for 1<=n0<=10
    with p=1/4,
    The input gives you the output.

  • If you want to see the numerical algorithm in action, to compute, and then (if possible) identify the expected duration of the "One Step Back with probability p and Two Steps Forward with probability 1-p" game until reaching for the first time >=n0 dollars for 1<=n0<=10
    with p=1/5,
    The input gives you the output.

  • If you want to see the numerical algorithm in action, to compute, and then (if possible) identify the expected duration of the "One Step Back with probability p and Two Steps Forward with probability 1-p" game until reaching for the first time >=n0 dollars for 1<=n0<=10
    with p=1/6,
    The input gives you the output.

  ---

  Papers of Doron Zeilberger

  Doron Zeilberger's Home Page