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. 441456 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 nonnegative halfline and quarterplane
respectively, are used, as case studies, to illustrate the `naive' methodology of guessandcheck, 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 onedimensional 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 twodimensional walks

W3D,
to discover and prove theorems about the enumeration of threedimensional 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 onedimensinal walks with a given set of steps, for 16 different
choices of stepsets 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 onedimensinal walks with a given set of steps, for 32 different
choices of stepsets 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 onedimensinal walks with a given set of steps, for 16 different
choices of stepsets 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 onedimensinal walks with a given set of steps, for 32 different
choices of stepsets 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 OneDimensional (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 OneDimensional (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 OneDimensional (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 OneDimensional (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 OneDimensional (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 onedimensinal walks with a given set of steps, for 16 different
choices of stepsets 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 nstep
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 nstep
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 threefaced 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 threefaced 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 fourfaced 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 nstep 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
nonnegatives,
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 BousquetMelou

If you want to see 50 exciting theorems (proofs ommited, since we know they exist!) for
walks in the infinite chessboard starting at the bottomleft corner
with THREE kingsteps, 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 bottomleft corner
with FOUR kingsteps, 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 bottomleft corner
with FIVE kingsteps, 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 bottomleft corner
with SIX kingsteps, 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 bottomleft corner
with SEVEN kingsteps, 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 bottomleft corner
with ALL the EIGHT kingsteps, 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
Doron Zeilberger's Home Page