Random Funstuff

[Polo]

Aufgabenstellung bei mir ausm Studium:


3 (eindimensionale Irrfahrt). In einer Straße liegen (in dieser Reihenfolge) n + 1
Gaststätten G0,G1,G2, ... ,Gn, wobei n € N (natürliche Zahlen). Eine fröhliche Gruppe verlässt gerade Gn, um sich zu ihrem Nachtlager in G0 zu begeben. Wann immer die Gruppe an einer anderen Gaststätte als G0 vorbeikommt, kehrt sie dort ein, um "einen Letzten zu heben". Wenn die Gruppe wieder die Straße betritt, schlägt sie mit
Wahrscheinlichkeit 1/2 die richtige Richtung (nach G0) ein; aber mit Wahrscheinlichkeit 1/2 geht sie in die falsche Richtung (unabhängig von allen anderen Richtungsentscheidungen). Bei Gn ist die Straße allerdings zu Ende, weswegen die Gruppe dort immer die richtige Richtung nimmt, und wenn die Gruppe G0 erreicht, geht sie schnurstracks ins Bett. Wir möchten wissen, wieviele "Letzten" vorher gehoben werden.
Für i = 1,2,3, ... n, sei A(i) die erwartete Anzahl der noch ausstehenden Gaststätten-
besuche (das letzte Betreten von G0 auch mitgerechnet), wenn die Gruppe
Gi verlässt (man kann zeigen, dass diese Erwartungswerte existieren ) und sei A(0) = 0.

Bestimmen Sie den exakten Wert von A(n).