Tower of Hanoi with random moves
Martin Fuller
martin_n_fuller at btinternet.com
Tue Feb 5 18:11:33 CET 2008
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
> >
> >
>
More information about the SeqFan
mailing list