Tower of Hanoi with random moves

[Maximilian Hasler]

I used this well-known self-similarity to generate the set of
fixed-point relations
x[i] = 1+sum( T[i,j] x[j], j=1..3^n \ 2 )
of which the expectation values for running times are the unique solution.
(The \2 I added stands for the fact that the symmetry of the graph
allows to restrict oneself to one half of the graph.)

Maximilian Hasler
PS: The problem is solved, I don't know if this has been e-mailed to
the seqfan list.

On Feb 5, 2008 1:11 PM, Martin Fuller <martin_n_fuller at btinternet.com> wrote:
> The transition graph of towers of Hanoi is a like the iterations
> towards Sierpinski's triangle.  It is made from three copies of the
> (n-1) transition graph connected at the corners [Ian Stewart, The
> Magical Maze]. The corners correspond to all the disks on the same peg.
>
> Transition graph with 2 disks:
>         A
>        / \
>       B---C
>      /     \
>     D       E
>    / \     / \
>   F---G---H---I
>
> I think it ought to be possible to generate a recurrence for the
> sequence using this self-similarity, but it seems messy.  Any takers?
>
> Martin Fuller