Towers of Hanoi with random moves

[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.

[xilman]

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

[m_f_h]

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.

[xilman]

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

[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.

[xilman]

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

[Kevin]

What if you stipulated that it takes more time to move the bigger discs?

[maxal]

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.

[nibble4bits]

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.

[maxal]

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.

[maxal]

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