Non-holonomicity conjecture for the two-player winning probability

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ˉ(n1)++pN(n)wˉ(nN)=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.

Sources & referencesView supporting material

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.