Non-holonomicity conjecture for the two-player winning probability

About 6 years old · traced to

Let p=q=1/2p=q=1/2, and let Wn,0,0(x)W_{n,0,0}(x) be the probability generating function for the two-player pile game with boundary, with nn the initial pile size. Define the first player's winning probability by

wˉ(n):=Wn,0,0(1).\bar{w}(n):=W_{n,0,0}(1).

A sequence is holonomic if it satisfies a linear recurrence with polynomial coefficients. Non-holonomicity conjecture. The winning probability sequence wˉ(n)\bar{w}(n) is not holonomic: there are no specific NN and polynomials p0(n),p1(n),…,pN(n)p_0(n),p_1(n),\dots,p_N(n) such that

p0(n)wˉ(n)+p1(n)wˉ(n−1)+⋯+pN(n)wˉ(n−N)=0.p_0(n)\bar{w}(n)+p_1(n)\bar{w}(n-1)+\dots+p_N(n)\bar{w}(n-N)=0.

The conjecture concerns the apparent absence of a linear recurrence for the two-player winning probabilities, in contrast with related pile games where the corresponding sequence is holonomic of small order. The evidence presented is computational and the conjecture remains open.

References

Primary source

Ho-Hon Leung and Thotsaporn "Aek'' Thanatipanonda, “Game of Pure Chance with Restricted Boundary”, arXiv:2001.05108 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.