mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-02-03, 21:34   #1
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default 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
m_f_h is offline   Reply With Quote
Old 2008-02-03, 22:42   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×61×83 Posts
Default

Quote:
Originally Posted by m_f_h View Post
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
xilman is offline   Reply With Quote
Old 2008-02-04, 01:25   #3
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by xilman View Post
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
m_f_h is offline   Reply With Quote
Old 2008-02-04, 09:16   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×61×83 Posts
Default

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

Paul
xilman is offline   Reply With Quote
Old 2008-02-04, 20:39   #5
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

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.
maxal is offline   Reply With Quote
Old 2008-02-05, 12:30   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·61·83 Posts
Default

Quote:
Originally Posted by maxal View Post
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
xilman is offline   Reply With Quote
Old 2008-02-05, 17:04   #7
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

What if you stipulated that it takes more time to move the bigger discs?
Kevin is offline   Reply With Quote
Old 2008-02-05, 17:14   #8
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
maxal is offline   Reply With Quote
Old 2008-03-15, 06:38   #9
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

18110 Posts
Default

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.
nibble4bits is offline   Reply With Quote
Old 2008-03-15, 08:56   #10
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by nibble4bits View Post
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.
maxal is offline   Reply With Quote
Old 2013-10-10, 04:17   #11
maxal
 
maxal's Avatar
 
Feb 2005

FC16 Posts
Default

If anybody still cares, here is a preprint about solving Tower of Hanoi with random moves:
http://arxiv.org/abs/1304.3780
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
random comments, random questions and thread titles made for Google jasong Lounge 46 2017-05-09 12:32
GPU and Random P-1 jocelynl Factoring 1 2016-11-25 05:14
Random bit in a word Prime95 Programming 19 2012-10-06 09:34
About random number (random seed) in Msieve Greenk12 Factoring 1 2008-11-15 13:56
Commons Moves to Erode Nobles’ Power in Britain ewmayer Lounge 4 2007-03-08 20:31

All times are UTC. The time now is 10:36.

Wed Oct 28 10:36:23 UTC 2020 up 48 days, 7:47, 2 users, load averages: 1.00, 1.38, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.