20080203, 21:34  #1 
Feb 2007
2^{4}·3^{3} Posts 
Towers of Hanoi with random moves
I think this could interest some freaks here:
Calculate the expected number of moves after which the tower of discs is moved from pole 1 to pole 3, when in any situation any of the possible moves is made with the same probability. Could anyone give a formula? Some contradicting information on OEIS : A007798 : Expected time to finish a random Tower of Hanoi problem with n disks using random moves. = 2, 18, 116, 660, 3542 should IMHO rather be equal to the integer part (or nearest integer) of e = [0, 2, 64/3, 1274/9, 21760/27, 348722/81, ...] used in > %S A134939 0,2,64,1274,21760, 348722 > %N A134939 Consider a 3pole Tower of Hanoi configuration which begins with n rings on pole 1. Moves are made at random, where the 1step 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 probability 1/2, and each of the three allowable transitions out of any of the other 3^n  3 states have probability 1/3. > %C A134939 It appears that the denominator of e(n) for n>=1 is 3^(n1). > %e A134939 The values of e(0), ..., e(5) are 0, 2, 64/3, 1274/9, 21760/27, 348722/81. PS: yes, OEIS is down at present. I found the former seq in google's cache. Last fiddled with by m_f_h on 20080203 at 21:37 
20080203, 22:42  #2  
Bamboozled!
May 2003
Down not across
2^{3}·1,249 Posts 
Quote:
Paul 

20080204, 01:25  #3  
Feb 2007
2^{4}×3^{3} Posts 
Quote:
But can you confirm the values ? Even (or: even more) starting at a random position, I would be surprised of the expectation value being an integer. Thus, at least, there is some rounding process involved. But do you have more information on this? I figured out the topology of the graph given by all possible positions, so either of these expectation values has a (maybe simpler) interpretation as random walk on that graph. Last fiddled with by m_f_h on 20080204 at 01:32 Reason: probabilities > expectation values 

20080204, 09:16  #4 
Bamboozled!
May 2003
Down not across
10011100001000_{2} Posts 

20080204, 20:39  #5 
Feb 2005
2^{2}·3^{2}·7 Posts 
A correct definition for A007798 seems to be:
%N A007798 Expected number of random moves in Tower of Hanoi problem with n disks, starting with a randomly chosen position and ending at a position with all disks on the same peg. 
20080205, 12:30  #6  
Bamboozled!
May 2003
Down not across
2^{3}×1,249 Posts 
Quote:
Paul 

20080205, 17:04  #7 
Aug 2002
Ann Arbor, MI
433 Posts 
What if you stipulated that it takes more time to move the bigger discs?

20080205, 17:14  #8  
Feb 2005
2^{2}×3^{2}×7 Posts 
Quote:
A134939 requires that in the final position all disks are on the third (i.e., fixed) peg while A007798 requires only that in the final position all disks are on the same (any) peg. 

20080315, 06:38  #9 
Nov 2005
2×7×13 Posts 
Firstly, treat this question as equivilent to thinking about all possible moves. It's in theory possible to never have this algorythm halt. Realisticly, that may never happen in practice (see hysteresis in electronics).
The lower bound will of course be the best case solution/s. As far as filtering out duplicate states... That's a little beyond my experience. If you can find a way to enumerate the solutions so that if the same state occurs, parts of the solution are identical for both solutions, then you can at least make it easier. If I find a way to do that, I should patent it (just kidding). It's still an intractable problem since infinite reduced by a finite amount is still infinite (alephnull > alephnull). Using calculus, it's at least possible to treat it as a series. What I mean, is that if you know the rough odds for each branch, then you can at least make a good estimate. What I want to know, is the frequency of solutions in relation to the number of steps. The average could be infinite but that seems against common sense as we most often see solutions in finite time. Perhaps I should requalify that question in terms of frequency divided by number of steps? Note that if you increase the number of towers, the lower the odds of a random set of moves being a solution (or having passed the solved state/s) for a given number of steps. Can someone verify that? I'm pretty sure, but it would be nice to have a counterexample if I'm wrong. 
20080315, 08:56  #10  
Feb 2005
2^{2}·3^{2}·7 Posts 
Quote:


20131010, 04:17  #11 
Feb 2005
2^{2}·3^{2}·7 Posts 
If anybody still cares, here is a preprint about solving Tower of Hanoi with random moves:
http://arxiv.org/abs/1304.3780 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
random comments, random questions and thread titles made for Google  jasong  Lounge  46  20170509 12:32 
GPU and Random P1  jocelynl  Factoring  1  20161125 05:14 
Random bit in a word  Prime95  Programming  19  20121006 09:34 
About random number (random seed) in Msieve  Greenk12  Factoring  1  20081115 13:56 
Commons Moves to Erode Noblesâ€™ Power in Britain  ewmayer  Lounge  4  20070308 20:31 