[math-fun] Tower of Hanoi with random moves
My former colleague Toby Berger (now at U of Va) has been looking at this problem. Has anyone seen anything like this before? %I A134939 %S A134939 0,2,64,1274,21760 %N A134939 Consider a 3-pole Tower of Hanoi configuration which begins with n rings on pole 1. Moves are made at random, where the 1-step transition probabilities out of any state are equal. Let e(n) be the expected number of transitions to reach the state in which which all rings are on pole 3. Sequence gives a(n), the numerator of e(n). %C A134939 Both allowable transitions out of any of the three special states in which all the rings are on one of the poles have probabilty 1/2, and each of the three allowable transitions out of any of the other 3^n - 3 states have probabilty 1/3. %C A134939 It appears that the denominator of e(n) for n>=1 is 3^(n-1). %e A134939 The values of e(0), ..., e(4) are 0, 2, 64/3, 1274/9, 21760/27. %K A134939 nonn,frac,more,new %Y A134939 Cf. A134940. %O A134939 0,2 %A A134939 Toby Berger (tb6n(AT)virginia.edu), Jan 23 2008 Neil
The following paper may be relevant "Shortest Paths in the Tower of Hanoi Graph and Finite Automata" by Dan Romik http://arxiv.org/PS_cache/math/pdf/0310/0310109v1.pdf Reference [7] in that paper is to Hinz and Schief "The average distance on the Sierpinski Gasket" Probability Theory and Related Fields,v87 (1990), pp 129-138, which looks closely connected to Berger's question. On Feb 1, 2008 8:32 PM, N. J. A. Sloane <njas@research.att.com> wrote:
My former colleague Toby Berger (now at U of Va) has been looking at this problem. Has anyone seen anything like this before?
%I A134939 %S A134939 0,2,64,1274,21760 %N A134939 Consider a 3-pole Tower of Hanoi configuration which begins with n rings on pole 1. Moves are made at random, where the 1-step transition probabilities out of any state are equal. Let e(n) be the expected number of transitions to reach the state in which which all rings are on pole 3. Sequence gives a(n), the numerator of e(n). %C A134939 Both allowable transitions out of any of the three special states in which all the rings are on one of the poles have probabilty 1/2, and each of the three allowable transitions out of any of the other 3^n - 3 states have probabilty 1/3. %C A134939 It appears that the denominator of e(n) for n>=1 is 3^(n-1). %e A134939 The values of e(0), ..., e(4) are 0, 2, 64/3, 1274/9, 21760/27. %K A134939 nonn,frac,more,new %Y A134939 Cf. A134940. %O A134939 0,2 %A A134939 Toby Berger (tb6n(AT)virginia.edu), Jan 23 2008
Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Neil, This is the next term of the expectation: e(5) = 348722/81 I will try to compute further term(s) soon. Regards, Max On Feb 1, 2008 5:32 PM, N. J. A. Sloane <njas@research.att.com> wrote:
My former colleague Toby Berger (now at U of Va) has been looking at this problem. Has anyone seen anything like this before?
%I A134939 %S A134939 0,2,64,1274,21760 %N A134939 Consider a 3-pole Tower of Hanoi configuration which begins with n rings on pole 1. Moves are made at random, where the 1-step transition probabilities out of any state are equal. Let e(n) be the expected number of transitions to reach the state in which which all rings are on pole 3. Sequence gives a(n), the numerator of e(n). %C A134939 Both allowable transitions out of any of the three special states in which all the rings are on one of the poles have probabilty 1/2, and each of the three allowable transitions out of any of the other 3^n - 3 states have probabilty 1/3. %C A134939 It appears that the denominator of e(n) for n>=1 is 3^(n-1). %e A134939 The values of e(0), ..., e(4) are 0, 2, 64/3, 1274/9, 21760/27. %K A134939 nonn,frac,more,new %Y A134939 Cf. A134940. %O A134939 0,2 %A A134939 Toby Berger (tb6n(AT)virginia.edu), Jan 23 2008
Neil
participants (3)
-
Max Alekseyev -
N. J. A. Sloane -
victor miller