Thanks to David L. Morgan, who set a short paper and simulation, we now have connecting information for Chutes and Ladders. [Update Jan 2006 -- the original data from DLM are incorrect according to a picture of the board at http://www.boardgamegeek.com/image/79293 . Thanks to Todd Neller for catching this. The following presentation has been corrected.] Additional analyses available on the web e.g. at http://www.math.byu.edu/~jeffh/mathematics/games/chutes/ http://www.findarticles.com/p/articles/mi_qa3997/is_200312/ai_n9338086 http://www.math.temple.edu/~zeilberg/tokhniot/ChutesAndLadders and in the literature e.g. in Althoen, S. C., L. King, and K. Schilling. 1993. How Long is a Game of Snakes and Ladders'? Mathematical Gazette. 77(478): 71-76. Gadbois, Steve. 1993. Mr. Markov Plays Chutes and Ladders. The UMAP Journal. 14(1): 31-38. The game consists of 100 states -- 101, if we include a state "0" where the players begin. With each turn, the marker moves with fixed probabilities to another state. Nominally, the probability p_ij of moving from state j to state i is 0 unless i = j+1, ..., j+6; each of those probabilities is 1/6. However, there are two exceptions: First, the presence of chutes and ladders changes some probabilities to 0 and raises others. Second, we declare the marker to move to state 100 if a roll of the die would move it past square 100. So we define a matrix P to contain these transition probabilities. We also let V_n be the vector whose i-th coordinate is the probability that the marker is in state i after n moves. (Note that we start our enumeration with state 0, so that e.g. V_0 = [1, 0, ..., 0]' , where the dash indicates transpose.) Then we have V_n = P V_{n-1} = P^n V_0. Note in particular that if U = [0, ..., 0, 1]' then U' V_n is the probability that the piece is in state 100 after n moves; thus the probability that the marker reaches state 100 precisely on the n-th move is U'(P^n - P^{n-1}) V_0. Therefore, we may calculate the expected number of moves after which the marker (first) reaches state 100 as the sum sum( n U'(P^n - P^{n-1}) V_0 , n >= 1 ) . It is possible to estimate this numerically, since for large n the multiplier of n decreases as a b^n for some b < 1. Rather than show these estimates, we use some algebraic feats to get the exact value. (We compare this to numerical estimates below.) OK, This is an infinite sum, which we must treat as a limit of the partial sums sum( n U'(P^n - P^{n-1}) V_0 , 1 <= n <= N ) = U' sum( n (P^n - P^{n-1}) , 1 <= n <= N ) V_0 = U' [ - I - sum( P^n , 1 <= n <= N-1 ) + N P^N ] V_0 Unfortunately, N P^N does not converge to zero. But if we let J be the 101x101 matrix with all columns equal to U and let Q = P - J, then we observe Q J = P J - J^2 = J - J = 0 and J Q = J P - J^2 = J - J = 0 so that P^n = (Q + J)^n = Q^n + J^n = Q^n + J for n > 0. Thus P^n - P^{n-1} = Q^n - Q^{n-1} for n > 1, and equals Q - I when n=1. Therefore, we have essentially the same expansion as above, = U' [ J - I - sum( Q^n , 1 <= n <= N-1 ) + N Q^N ] V_0 except that now the series converges; Q has no eigenvalues of norm 1 or more. Indeed, if we let X = [ I + sum( Q^n , 1 <= n <= N-1 ) - N Q^N ] V_0, so that we are seeking U' ( J V_0 - X ) = 1 - U' X, then we find (I - Q)X = [ (I - Q^N) - N(I-Q)Q^N ] V_0 = [ I - Q^N(I + N(I-Q)) ] V_0 --> V_0 so we may compute our X as the solution to (I - Q) X = V_0. As above, the expected number of games will be 1 - U' X . Very well, then, let's do it. Note that all matrix entries indexed by a counting number i refer to state i-1 (= 0, 1, ..., 100 ). Here we do this in Maple: #Declare the Chute and Latter links. If State a forces a move to State b, #then [a,b] is on this list. CL:=[ [98,78],[95,75],[93,73],[87,24],[62,19],[64,60],[56,53],[49,11],[48,26],[16,6], [1,38],[4,14],[9,31],[21,42],[28,84],[36,44],[51,67],[71,91],[80,100] ]; with(linalg): P:=matrix(101,101): for i to 101 do for j to 101 do P[i,j]:=0:od:od: for j to 101 do for k to min(6,101-j) do P[j+k,j]:=1/6:od:od: for j from 96 to 100 do P[101,j]:=(j-94)/6:od: # That line assumes it's OK to reach the last square by rolling too high # a number. Neller informs me the rules require an exact roll to 100. # Thus we should replace the previous line with # for j from 96 to 100 do P[j,j]:=(j-95)/6: od: P[101,101]:=1: for c in CL do for j to 101 do P[c[2]+1,j]:=P[c[2]+1,j]+P[c[1]+1,j]:P[c[1]+1,j]:=0:od:od: Q:=matrix(101,101): for i to 100 do for j to 101 do Q[i,j]:=P[i,j]:od:od: for j to 101 do Q[101,j]:=P[101,j]-1:od: #Now I-Q: R:=matrix(101,101): for i to 101 do for j to 101 do R[i,j]:=-Q[i,j]:od:od: for i to 101 do R[i,i]:=1 + R[i,i]:od: V0:=vector(101,[1,seq(0,i=1..100)]): ans:=linsolve(R,V0): #To multiply by -U' we simply look at the negative of the last entry: #Don't forget the "1+": 1-ans[101]; 4701963530284262061680976447702295260969373555678655812977547 ------------------------------------------------------------- 118741353443887754043709082737855602672874458412108079756280 > evalf(%); 39.59836564 #So the expected length of a game is a bit longer than 36 moves. #(Using the more permissive rule that it suffices to _pass_ square 100 # to win, the length of a game drops a bit, to about 36.19307022 moves.) #Note: we can prove convergence of the series since the eigenvalues are small: S:=matrix(101,101): for i to 101 do for j to 101 do S[i,j]:=1.0*Q[i,j]:od:od: EV:=[eigenvalues(S)]; #Answer is .9578063604, .3986347422 + .6511180886 I, ... We remark that numerical simulations of the game show roughly the expected number of games ending after n moves. As above, we have found that the fraction of games ending after n moves is exactly U'(P^n - P^{n-1}) V_0 = U'(Q^n - Q^{n-1}) V_0 Here are the first few values. For the larger ones which we have computed, we get an excellent fit to the data with a formula which states that the probability of finishing on the nth move is about (.0770680411)(.9578063749)^n. (It can be argued on general principles that when the largest eigenvalue is e and e is real, positive, and less than 1, then the probability is for large n roughly equal to a e^n for some a. The largest eigenvalue is .9578063604 .) *** WARNING: the following data computed from incorrect ladder data *** *** I have not recomputed the actual correct values but the general *** *** patterns should still be correct. *** 2 0 3 0 4 0 5 .001028806584362139918 = 1/972 6 .004865397805212620027 227/46656 7 .007183784865112025606 2011/279936 8 .007712477137631458619 2159/279936 9 .009092852175735406188 30545/3359232 10 .012406026800834899829 750145/60466176 11 .016808727907648732409 677573/40310784 12 .019935227001033510775 21697325/1088391168 13 .020900593924456885462 136488131/6530347008 14 .021259105513575387223 1665952033/78364164096 15 .022534197095967451127 1765873519/78364164096 16 .024579600756331576009 23113918405/940369969152 17 .026301724756827448261 55650042221/2115832430592 18 .027050359246779380977 114468054707/4231664861184 19 .027083725475615978859 16503731914337/609359740010496 20 .026998627938604251080 4112969225327/152339935002624 21 .027045376684169935396 296646546685531/10968475320188928 22 .027034279824652630108 1779148986334703/65810851921133568 23 .026700477754458100819 1757181187722163/65810851921133568 24 .026005905241419176904 123225896082100951/4738381338321616896 25 .025123385167345761372 714265076594503607/28430288029929701376 26 .024239856840946974105 4134876670754306059/170581728179578208256 27 .023420868457712456903 3995172216983163419/170581728179578208256 28 .022626510204739238013 138948091682302122169/6140942214464815497216 29 .021803118805260645351 9917903161349390357/454884608478875222016 30 .020943839931661281529 2315068393847987884753/110536959860366678949888 31 .020082443209002432639 26638226626699143556885/1326443518324400147398656 32 .019254488442365432815 153239948358166222998577/7958661109946400884391936 33 .018471615844670596096 34 .017724427561924814808 35 .016999886600835364603 36 .016293588802962357271 37 .015609636056289876152 38 .014953627429237159719 39 .014327279434734782953 40 .013728256347285985345 41 .013153175211133782125 42 .012600116449551833745 43 .012068899251618205080 44 .011559858483080066572 45 .011072720726221450394 46 .010606427854323110571 47 .010159657452920947094 48 .009731346261395654642 49 .009320808431587618434 50 .008927527062677727404 51 .008550920022790505239 52 .008190275062329734846 53 .007844834632347475521 54 .007513901194485850390 55 .007196871414619109968 56 .006893201566031289771 57 .006602359464959731249 58 .006323805735644835473 Notice that the numbers are first rising then falling _except_ in the range n=19, 20, 21 ! It's not clear what other questions are interesting. We can compute the average position at stage n; that's Z' P^n V_0 where Z=[0,1,2,...100]'. Here are a few values: 1 8.833333333333333333 2 16. 3 22.046296296296296296 4 26.519290123456790123 5 30.814171810699588477 8 42.242258944901691815 12 52.533961594036014816 16 60.714751450793112733 20 67.535235944340794482 24 72.907061819879920958 28 77.239279576618381361 32 80.859388908507168439 40 86.448068225480113960 48 90.401549080886731647 56 93.201381743726723964 A future line of inquiry: what happens with multiple players? (The game stops when the first person reaches 100, right?) Anyone reading this who has a specific question about the game is invited to ask for details!