Linear Recurrence Equations Satisfied by the Expected Number of Rounds in Simple Urn Solitaire By Shalosh B. Ekhad We start with, m, White balls and, n, Black balls in our urn, and we are playing Simple Urn Solitaire In this game, you draw a ball at random, and keep drawing balls if they are \ of the same color as the initial ball as soon as you get a ball of the other color, the round ends, and a new roun\ d starts Let E(m,n) be the expected number of rounds. Theorem 1: The diagonal sequence, E(n,n), satisfies the linear recurrence equation with\ polynomial coefficies 2 2 (n + 2) (n + 1) E(n, n) - (n + 2) (5 n + 12 n + 5) E(n + 1, n + 1) 2 + 2 (2 n + 3) (n + 1) E(n + 2, n + 2) = 0 and in Maple input format (n+2)^2*(n+1)*E(n,n)-(n+2)*(5*n^2+12*n+5)*E(n+1,n+1)+2*(2*n+3)*(n+1)^2*E(n+2,n+ 2) = 0 23 subject to the initial conditions, E(1, 1) = 1, E(2, 2) = 5/3, E(3, 3) = -- 10 Proof: Routine computations in the holonomic ansatz Using this recurrence, we can compute many terms for example, E(i,i)/i, for i from, 9991, to , 10000, are [0.6666889104, 0.6666889082, 0.6666889059, 0.6666889037, 0.6666889015, 0.6666888993, 0.6666888970, 0.6666888948, 0.6666888926, 0.6666888904] We also have: Theorem 2: Let F(n,n,x) be the probability generating function of the r.v. "\ number of rounds" in Simple Urn Solitaire It satisfies the linear recurrence equation with polynomial coefficies 2 -x (n + 2) (n + 1) F(n, n, x) 2 2 + (n + 2) (4 n x + 4 n x + 8 x + n + 4 x + 1) F(n + 1, n + 1, x) - 4 (2 n + 3) (2 n x + n + 5 x + 2) F(n + 2, n + 2, x) + 4 (2 n + 5) (2 n + 3) F(n + 3, n + 3, x) = 0 and in Maple input format -x^2*(n+2)*(n+1)*F(n,n,x)+(n+2)*(4*n*x^2+4*n*x+8*x^2+n+4*x+1)*F(n+1,n+1,x)-4*(2 *n+3)*(2*n*x+n+5*x+2)*F(n+2,n+2,x)+4*(2*n+5)*(2*n+3)*F(n+3,n+3,x) = 0 2 Subject to the initial conditions, F(1, 1, x) = x, F(2, 2, x) = 2/3 x + 1/3 x, 3 2 F(3, 3, x) = 2/5 x + 1/2 x + 1/10 x Theorem 3: The sequence of variances V(n,n) satisfies the linear recurrence \ equation -(n + 2) 3 2 (738827419605 n + 5765983631851 n + 14729120554372 n + 12257971956900) 2 5 4 (n + 1) V(n, n) + (n + 2) (12560066133285 n + 87539641895072 n 3 2 + 123814397664067 n - 352366528160012 n - 1079318300908468 n 5 - 759057805246464) V(n + 1, n + 1) + (472063826859600 n 4 3 2 + 5138943375840688 n + 21877648416147136 n + 45487155000087336 n + 46154873112291720 n + 18291869599837680) V(n + 2, n + 2) - 4 (2 n + 5) ( 5 4 3 25120132266570 n + 375185645603149 n + 1973349278988005 n 2 + 4732957353234322 n + 5252130101572944 n + 2180223951997680) V(n + 3, n + 3) + 16 (2 n + 5) 3 2 (1477654839210 n + 7537664441837 n + 12109578419925 n + 6185694065670) 2 (2 n + 7) V(n + 4, n + 4) = 0 and in Maple input format -(n+2)*(738827419605*n^3+5765983631851*n^2+14729120554372*n+12257971956900)*(n+ 1)^2*V(n,n)+(n+2)*(12560066133285*n^5+87539641895072*n^4+123814397664067*n^3-\ 352366528160012*n^2-1079318300908468*n-759057805246464)*V(n+1,n+1)+( 472063826859600*n^5+5138943375840688*n^4+21877648416147136*n^3+ 45487155000087336*n^2+46154873112291720*n+18291869599837680)*V(n+2,n+2)-4*(2*n+ 5)*(25120132266570*n^5+375185645603149*n^4+1973349278988005*n^3+ 4732957353234322*n^2+5252130101572944*n+2180223951997680)*V(n+3,n+3)+16*(2*n+5) *(1477654839210*n^3+7537664441837*n^2+12109578419925*n+6185694065670)*(2*n+7)^2 *V(n+4,n+4) = 0 271 Subject to the initial conditions, V(1, 1) = 1, V(2, 2) = 17/9, V(3, 3) = ---, 100 4301 V(4, 4) = ---- 1225 Using this recurrence, we can compute many terms for example, V(i,i)/i, for i from, 9991, to , 10000, are [0.8148345870, 0.8148345850, 0.8148345831, 0.8148345811, 0.8148345791, 0.8148345771, 0.8148345751, 0.8148345732, 0.8148345712, 0.8148345692] ------------------------------------- This ends this article, that took, 33.289, seconds to generate.