Tower of Hanoi with random moves

[Martin Fuller]

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

--- Max Alekseyev <maxale at gmail.com> wrote:

> Neil,
> 
> This is the next term of the expectation:
> 
> e(5) = 348722/81
> 
> I will try to compute further term(s) soon.
> 
> Regards,
> Max
> 
> On Feb 1, 2008 5:32 PM, N. J. A. Sloane <njas at research.att.com>
> wrote:
> > My former colleague Toby Berger (now at U of Va)
> > has been looking at this problem.  Has anyone seen
> > anything like this before?
> >
> > %I A134939
> > %S A134939 0,2,64,1274,21760
> > %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
> probabilty 1/2, and each of the three allowable transitions out of
> any of the other 3^n - 3 states have probabilty 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(4) are 0, 2, 64/3, 1274/9,
> 21760/27.
> > %K A134939 nonn,frac,more,new
> > %Y A134939 Cf. A134940.
> > %O A134939 0,2
> > %A A134939 Toby Berger (tb6n(AT)virginia.edu), Jan 23 2008
> >
> > Neil
> >
> >
>