Linear Recurrence Equations Satisfied by the Expected Number of Rounds in Oakley-Perry Urn Solitaire By Shalosh B. Ekhad We start with, m, White balls and, n, Black balls in our urn, and we are playing Urn Solitaire invented by B.E. Oakley and R.L. Perry, "A Sampling Process", The Mathematic\ al Gazette, vol. 49, No. 367 (Feb. 1965), pp. 42-44 and polpularized in Peter Winkler's wonderful book "Mathematical Mind Bender\ s", A.K. Peters, 2007, pp. 76 and 79 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, you put it back, and start a n\ ew round. Let E(m,n) be the expected number of rounds. Theorem 1: E(m,n) satisfies the following linear recurrences in m 2 (m + 2) (m + 1) (2 m n + 2 m + 7 n + 9) (3 + m) E(m, n) - (3 + m) (m + 2) 2 2 2 2 (14 m n + 6 m n + 14 m + 83 m n + 21 n + 91 m + 123 n + 128) 3 2 2 3 3 2 E(m + 1, n) + (3 + m) (18 m n + 16 m n + 2 m n + 18 m + 167 m n 2 3 2 2 + 94 m n + 7 n + 169 m + 521 m n + 132 n + 511 m + 537 n + 508) 4 3 2 2 3 4 3 2 2 E(m + 2, n) + (-10 m n - 14 m n - 4 m n - 10 m - 135 m n - 129 m n 3 3 2 2 3 2 - 24 m n - 131 m - 684 m n - 393 m n - 34 n - 639 m - 1535 m n 2 - 396 n - 1380 m - 1286 n - 1116) E(3 + m, n) + (3 + m) (2 m n + 2 m + 5 n + 7) (n + 4 + m) (n + 3 + m) E(m + 4, n) = 0 and in Maple input format 2*(m+2)*(m+1)*(2*m*n+2*m+7*n+9)*(3+m)*E(m,n)-(3+m)*(m+2)*(14*m^2*n+6*m*n^2+14*m ^2+83*m*n+21*n^2+91*m+123*n+128)*E(m+1,n)+(3+m)*(18*m^3*n+16*m^2*n^2+2*m*n^3+18 *m^3+167*m^2*n+94*m*n^2+7*n^3+169*m^2+521*m*n+132*n^2+511*m+537*n+508)*E(m+2,n) +(-10*m^4*n-14*m^3*n^2-4*m^2*n^3-10*m^4-135*m^3*n-129*m^2*n^2-24*m*n^3-131*m^3-\ 684*m^2*n-393*m*n^2-34*n^3-639*m^2-1535*m*n-396*n^2-1380*m-1286*n-1116)*E(3+m,n )+(3+m)*(2*m*n+2*m+5*n+7)*(n+4+m)*(n+3+m)*E(m+4,n) = 0 E(m,n) also satisfies (by symmetry) the following linear recurrences in n 2 (n + 2) (n + 1) (2 m n + 7 m + 2 n + 9) (3 + n) E(m, n) - (3 + n) (n + 2) 2 2 2 2 (6 m n + 14 m n + 21 m + 83 m n + 14 n + 123 m + 91 n + 128) 3 2 2 3 3 2 E(m, n + 1) + (3 + n) (2 m n + 16 m n + 18 m n + 7 m + 94 m n 2 3 2 2 + 167 m n + 18 n + 132 m + 521 m n + 169 n + 537 m + 511 n + 508) 3 2 2 3 4 3 2 2 E(m, n + 2) + (-4 m n - 14 m n - 10 m n - 24 m n - 129 m n 3 4 3 2 2 3 2 - 135 m n - 10 n - 34 m - 393 m n - 684 m n - 131 n - 396 m 2 - 1535 m n - 639 n - 1286 m - 1380 n - 1116) E(m, 3 + n) + (3 + n) (2 m n + 5 m + 2 n + 7) (n + 4 + m) (n + 3 + m) E(m, n + 4) = 0 and in Maple input format 2*(n+2)*(n+1)*(2*m*n+7*m+2*n+9)*(3+n)*E(m,n)-(3+n)*(n+2)*(6*m^2*n+14*m*n^2+21*m ^2+83*m*n+14*n^2+123*m+91*n+128)*E(m,n+1)+(3+n)*(2*m^3*n+16*m^2*n^2+18*m*n^3+7* m^3+94*m^2*n+167*m*n^2+18*n^3+132*m^2+521*m*n+169*n^2+537*m+511*n+508)*E(m,n+2) +(-4*m^3*n^2-14*m^2*n^3-10*m*n^4-24*m^3*n-129*m^2*n^2-135*m*n^3-10*n^4-34*m^3-\ 393*m^2*n-684*m*n^2-131*n^3-396*m^2-1535*m*n-639*n^2-1286*m-1380*n-1116)*E(m,3+ n)+(3+n)*(2*m*n+5*m+2*n+7)*(n+4+m)*(n+3+m)*E(m,n+4) = 0 subject to the initial conditions 19 107 E(1, 1) = 1, E(1, 2) = 4/3, E(1, 3) = --, E(1, 4) = ---, E(2, 1) = 4/3, 12 60 277 397 19 277 E(2, 2) = 17/9, E(2, 3) = ---, E(2, 4) = ---, E(3, 1) = --, E(3, 2) = ---, 120 150 12 120 143 579 107 397 579 E(3, 3) = ---, E(3, 4) = ---, E(4, 1) = ---, E(4, 2) = ---, E(4, 3) = ---, 50 175 60 150 175 4717 E(4, 4) = ---- 1225 Proof E(m,n) satisfies the following recurrence / m \ |----- | | \ binomial(m, k) n E(m - k, n) | E(m, n) = 1 + | ) ------------------------------| | / binomial(m + n, k) (m + n - k)| |----- | \k = 1 / / n \ |----- | | \ binomial(n, k) m E(m, n - k) | + | ) ------------------------------| | / binomial(m + n, k) (m + n - k)| |----- | \k = 1 / subject to the boundary conditions E(m,0)=0 and E(0,n)=0. Verifying this is a routine exercise in the Holonomic Ansatz (e.g. using Chr\ istoph Koutschan's package) that we omit since we verified it for many cases, and since everything is finite, this is\ proof enough for us. Corollary: The diagonal sequence, E(n,n), satisfies the linear recurrence equation with\ polynomial coefficies 4 3 2 2 -2 (18 n + 159 n + 528 n + 779 n + 428) (n + 1) (n + 2) E(n, n) + (n + 2) 6 5 4 3 2 (216 n + 2358 n + 10485 n + 24174 n + 30251 n + 19276 n + 4800) 7 6 5 4 3 E(n + 1, n + 1) + (-324 n - 4032 n - 21015 n - 59334 n - 97813 n 2 - 93898 n - 48288 n - 10080) E(n + 2, n + 2) + 4 3 2 2 2 (n + 2) (18 n + 87 n + 159 n + 128 n + 36) (2 n + 5) E(3 + n, 3 + n) = 0 and in Maple input format -2*(18*n^4+159*n^3+528*n^2+779*n+428)*(n+1)^2*(n+2)*E(n,n)+(n+2)*(216*n^6+2358* n^5+10485*n^4+24174*n^3+30251*n^2+19276*n+4800)*E(n+1,n+1)+(-324*n^7-4032*n^6-\ 21015*n^5-59334*n^4-97813*n^3-93898*n^2-48288*n-10080)*E(n+2,n+2)+2*(n+2)*(18*n ^4+87*n^3+159*n^2+128*n+36)*(2*n+5)^2*E(3+n,3+n) = 0 143 subject to the initial conditions, E(1, 1) = 1, E(2, 2) = 17/9, E(3, 3) = --- 50 Proof: Routine computations in the holonomic ansatz Using this recurrence, we can fompute many terms for example, E(i,i)/i, for i from, 9991, to , 10000, are [0.99998331898767991048, 0.99998332065704986021, 0.99998332232608571545, 0.99998332399478757649, 0.99998332566315554356, 0.99998332733118971688, 0.99998332899889019660, 0.99998333066625708285, 0.99998333233329047571, 0.99998333399999047524] Finally, to illustrate the efficiency of the above-holonomic representation, just for fun, the expected number of rounds when there are, 20000, White balls and, 30000, Black balls is in floating-point (we can also have the exact value as a rational number, but we spare you), 24327.742536120909479 . Note that using the two dimensional, defining recurrence for E(m,n) would have taken for ever. ------------------------------------- This ends this article, that took, 629.324, seconds to generate.