mersenneforum.org Towers of Hanoi with random moves
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2008-02-03, 21:34 #1 m_f_h     Feb 2007 24·33 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 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 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^(n-1). > %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 2008-02-03 at 21:37
2008-02-03, 22:42   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×72×109 Posts

Quote:
 Originally Posted by m_f_h 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 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 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^(n-1). > %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.
The two cases are different. The first has a random initial configuration (presumably, this means a configuration selected with probability 1/P where P is the number of configurations) whereas the second has the initial configuration where all disks are on pole 1.

Paul

2008-02-04, 01:25   #3
m_f_h

Feb 2007

6608 Posts

Quote:
 Originally Posted by xilman The two cases are different. The first has a random initial configuration (presumably, this means a configuration selected with probability 1/P where P is the number of configurations) whereas the second has the initial configuration where all disks are on pole 1. Paul
Thanks for that clarification. Indeed I did not initially think of this possibility.
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 2008-02-04 at 01:32 Reason: probabilities > expectation values

2008-02-04, 09:16   #4
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

1068210 Posts

Quote:
 Originally Posted by m_f_h But do you have more information on this?
Nope. All I did was read the text you posted.

Paul

 2008-02-04, 20:39 #5 maxal     Feb 2005 22·32·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.
2008-02-05, 12:30   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

246728 Posts

Quote:
 Originally Posted by maxal 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.
That's corrected only in the sense that it replaces "time" in the original with "number of moves". Admittedly it's a better phrasing, in my opinion, but the original seemed clear enough to me.

Paul

 2008-02-05, 17:04 #7 Kevin     Aug 2002 Ann Arbor, MI 6618 Posts What if you stipulated that it takes more time to move the bigger discs?
2008-02-05, 17:14   #8
maxal

Feb 2005

FC16 Posts

Quote:
 Originally Posted by xilman That's corrected only in the sense that it replaces "time" in the original with "number of moves". Admittedly it's a better phrasing, in my opinion, but the original seemed clear enough to me.
Not only that. Please notice another important difference between A134939 and A007798:
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.

 2008-03-15, 06:38 #9 nibble4bits     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 (aleph-null -> aleph-null). 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.
2008-03-15, 08:56   #10
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by nibble4bits 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?
I think it is rather simple question to answer, taking into account recent developments. But first, please clearly specify what is "solution" in your case as there are so many variations of the puzzle around.

 2013-10-10, 04:17 #11 maxal     Feb 2005 22·32·7 Posts If anybody still cares, here is a preprint about solving Tower of Hanoi with random moves: http://arxiv.org/abs/1304.3780

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Lounge 46 2017-05-09 12:32 jocelynl Factoring 1 2016-11-25 05:14 Prime95 Programming 19 2012-10-06 09:34 Greenk12 Factoring 1 2008-11-15 13:56 ewmayer Lounge 4 2007-03-08 20:31

All times are UTC. The time now is 00:13.

Sat May 15 00:13:21 UTC 2021 up 36 days, 18:54, 0 users, load averages: 2.53, 2.53, 2.26