The Method(!) of "Guess and Check"

By
Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex

Posted: Feb. 15, 2015

[This English original is exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, as well as in arxiv.org.
A German translation, by Martin Aigner, appeared in pp. 441-456 of a new edition of the anthology "Alles Mathematik: von Pythagoras zu Big Data" edited by him and Ehrhard Behrends, 2016, Springer.]

The problems of enumerating lattice walks, with an arbitrary finite set of allowed steps, both in one and two dimensions, where one must always stay in the non-negative half-line and quarter-plane respectively, are used, as case studies, to illustrate the `naive' methodology of guess-and-check, where rigorous proofs are possible, but not worth the trouble. We argue that this is a metaphor for future math.

Maple Packages

• W1D, To discover and prove theorems about the enumeration of one-dimensional walks

• W1Dp, To discover and prove theorems about the probability of gambling with an arbitrary loaded die, with arbitrary stakes

• W2D, to discover and prove theorems about the enumeration of two-dimensional walks

• W3D, to discover and prove theorems about the enumeration of three-dimensional walks
[Warning: Very slow, since 3D is (computaionally) hard!]

Some Input and Output files for the Maple package W1D

• If you want to see a webbook with 16 exciting theorems about algebraic equations satisfied by sequences enumerating one-dimensinal walks with a given set of steps, for 16 different choices of step-sets with steps of size at most 2

the input   yields the output

• If you want to see a webbook with 32 exciting theorems about algebraic equations satisfied by sequences enumerating one-dimensinal walks with a given set of steps, for 32 different choices of step-sets with steps of size at most 3

the input   yields the output

[16 of these theorems are already in the previous webbook]

• If you want to see a webbook with 16 exciting theorems about linear recurrence equations satisfied by sequences enumerating one-dimensinal walks with a given set of steps, for 16 different choices of step-sets with steps of size at most 2

the input   yields the output

• If you want to see a webbook with 32 exciting theorems about linear recurrence equations satisfied by sequences enumerating one-dimensinal walks with a given set of steps, for 32 different choices of step-sets with steps of size at most 3

the input   yields the output

[16 of these theorems are already in the previous webbook]

• If you want to see the Asymptotic behavior of the random variable "final Location of a One-Dimensional (LUCKY!) Walker with Step Set, {-1, 1}", or equivalently the amount of money a surviving gambler at a fair casino (with a fair coin where you win a dollar with prob. 1/2 and lose with prob. 1/2),

the input   yields the output

• If you want to see the Asymptotic behavior of the random variable "final Location of a One-Dimensional (LUCKY!) Walker with Step Set, {-1,0, 1}", or equivalently the amount of money a surviving gambler at a fair casino (with a fair die where you win a dollar with prob. 1/3 and lose with prob. 1/3, and nothing happens with prob. 1/3)

the input   yields the output

• If you want to see the Asymptotic behavior of the random variable "final Location of a One-Dimensional (LUCKY!) Walker with Step Set, {-2,-1, 1,2}", or equivalently the amount of money a surviving gambler at a fair casino (with a fair die where you win two dollars with prob. 1/4, you win one dollar with prob. 1/4, you lose two dollars with prob. 1/4, and you lose one dollar with prob. 1/4)

the input   yields the output

• If you want to see the Asymptotic behavior of the random variable "final Location of a One-Dimensional (LUCKY!) Walker with Step Set, {-2,-1,0, 1,2}", or equivalently the amount of money a surviving gambler at a fair casino (with a fair die where you win two dollar with prob. 1/5, you win one dollar with prob. 1/5, you lose two dollars with prob. 1/5, you lose one dollar with prob. 1/5, and nothing happens with prob. 1/5)

the input   yields the output

• If you want to see the Asymptotic behavior of the random variable "final Location of a One-Dimensional (LUCKY!) Walker with Step Set, {-3,-2,-1, 1,2,3}", or equivalently the amount of money a surviving gambler at a fair casino (with a fair die where you win three dollars with prob. 1/6, you win two dollars with prob. 1/6, you win one dollar with prob. 1/6, you lose three dollars with prob. 1/6, you lose two dollars with prob. 1/6, and you lose one dollar with prob. 1/6)

the input   yields the output

• If you want to see the Asymptotics of a Gambler's Chance of Ending with, 0, Dollars and never being in debt after n rolls with a various choices of fair dice

the input   yields the output

[Note that the leading asymptotics is always of the form C*n-3/2, for some constant C]

• If you want to see the Asymptotics of a Gambler's Chance of surviving without debt n rolls with a various choices of fair dice

the input   yields the output

[Note that the leading asymptotics is always of the form C*n-1/2, for some constant C]

• If you want to see a webbook with 16 exciting theorems about algebraic equations satisfied by sequences enumerating one-dimensinal walks with a given set of steps, for 16 different choices of step-sets with steps of size at most 2, with SKETCHES OF PROOFS

the input   yields the output

[Note, that the theorems are the same as the above oW1D1, but now we sketch proofs]

• If you want to see the MONSTER (20th order!) linear recurrence operator annihilating the enumerating sequence of n-step walks with fundamental set of steps, {-3, 1, 2} that start and end at 0 and never venture to the left of 0 , followed by the 20 initial values (n=1 through n=20), in Maple input notation is

the input   yields the output

• If you want to see the MONSTER (21st order!) linear recurrence operator annihilating the enumerating sequence of n-step walks with fundamental set of steps, {-3, 1, 2} that start at 0 and never venture to the left of 0, and are allowed to end anywhere, followed by the 21 initial values (n=1 through n=20), in Maple input notation is

the input   yields the output

Some Input and Output files for the Maple package W1Dp

• If you want to see algebaric equations for the probability generating functions for never going into debt, with any amount, and for breaking even, or ending with one dollar if at each roll of a three-faced die, you win a dollar with prob 1/2, lose a dollar with prob. 1/4, and lose two dollars with prob. 1/4 (so it is unfair to you, your expected loss per roll is a quarter dollar)

the input   yields the output

• If you want to see algebaric equations for the probability generating functions for never going into debt, with any amount, and for breaking even, or ending with one dollar if at each roll of a three-faced die, you win a dollar with prob 1/2, lose a dollar with prob. 1/4, and lose two dollars with prob. 1/4 (so it is unfair to you, your expected loss per roll is a quarter dollar)

the input   yields the output

• If you want to see algebaric equations for the probability generating functions for never going into debt, with any amount, and for breaking even, or ending with one dollar if at each roll of a four-faced die, you win two dollars with prob. 1/5, you win one dollar with prob 1/5, lose a dollar with prob. 3/20, and lose two dollars with prob. 9/20 (so it is unfair to you, your expected loss per roll is 45 cents)

the input   yields the output

• If you want to see the linear recurrence operator annihilating the sequence of probabilities for n-step walks with the probability distribution
{[-2, 9/20], [-1, 3/20], [0, 1/20], [1, 3/20], [2, 1/5]}
that start at 0, never go to the negatives, and end anywhere on the non-negatives, where N is the shift operator in n, (followed by the initial conditions), also those that break even, and those that end with one dollar

the input   yields the output

Some Input and Output files for the Maple package W2D

• If you want to see linear recurrences for the sequence enumerating Kreweras walks both the usual ones, returning to the origin (for which Kreweras found a famous closed form), and those that terminate anywhere, COMPLETE WITH A SKETCH OF PROOF

the input   yields the output

• If you want to see

the input   yields the output

• The six output files below is a redux of work done by Marni Mishna and Mireille Bousquet-Melou
• If you want to see 50 exciting theorems (proofs ommited, since we know they exist!) for walks in the infinite chessboard starting at the bottom-left corner with THREE king-steps, only outputting those whose recurrences have complexity <=12

the input   yields the output

• If you want to see 56 exciting theorems (proofs ommited, since we know they exist!) for walks in the infinite chessboard starting at the bottom-left corner with FOUR king-steps, only outputting those whose recurrences have complexity <=16

the input   yields the output

• If you want to see 22 exciting theorems (proofs ommited, since we know they exist!) for walks in the infinite chessboard starting at the bottom-left corner with FIVE king-steps, only outputting those whose recurrences have complexity <=16

the input   yields the output

• If you want to see 14 exciting theorems (proofs ommited, since we know they exist!) for walks in the infinite chessboard starting at the bottom-left corner with SIX king-steps, only outputting those whose recurrences have complexity <=16

the input   yields the output

• If you want to see 4 exciting theorems (proofs ommited, since we know they exist!) for walks in the infinite chessboard starting at the bottom-left corner with SEVEN king-steps, only outputting those whose recurrences have complexity <=16

the input   yields the output

• If you want to see 2 exciting theorems (proofs ommited, since we know they exist!) for walks in the infinite chessboard starting at the bottom-left corner with ALL the EIGHT king-steps, only outputting those whose recurrences have complexity <=16

the input   yields the output

• If you want to see the last two theorems (about the Chess King walking on an infinite chessboard) with a sketch of their proof

the input   yields the output

• If you want to see the two theorems about recurrences satisfied by simple lattice walks (up,down, left, right), confined to the first quadrant,

the input   yields the output

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger