La Trave di Equilibrio

Per risparmiare denaro per una nuova stalla nella sua fattoria, Bessie la mucca ha iniziato a esibirsi nel circo locale, dimostrando il suo notevole senso dell'equilibrio mentre cammina con attenzione avanti e indietro su una trave di equilibrio sopraelevata!

L'ammontare di denaro che Bessie guadagna per la sua esibizione dipende da dove alla fine salta giù dalla trave. Le posizioni sulla trave sono etichettate $0$, $1$, $\dots$, n + 1 da sinistra a destra. Se Bessie raggiunge mai la posizione $0$ o n + 1, cade da una delle estremità della trave e, purtroppo, non riceve alcun pagamento.

Quando Bessie si trova nella posizione $k$, può fare una delle seguenti cose:

1. Lanciare una moneta. Se esce croce, si sposta nella posizione k - 1; se esce testa, si sposta nella posizione k + 1 (cioè, ciascun esito si verifica con probabilità $1/2$).

2. Saltare giù dalla trave e ricevere un pagamento di f(k)~(0 \le f(k) \le 10^9).

Bessie si rende conto che non può garantirsi un pagamento particolare, poiché il suo movimento è governato da lanci di moneta casuali. Tuttavia, per ciascuna posizione di partenza, vuole determinare il suo pagamento atteso se prende una sequenza ottimale di decisioni (cioè, decisioni che portano al più alto pagamento atteso possibile). Per esempio, se la sua strategia le fa guadagnare un pagamento di $10$ con probabilità $1/2$, $8$ con probabilità $1/4$, e $0$ con probabilità $1/4$, allora il suo pagamento atteso è la media pesata 10 \cdot (1/2) + 8 \cdot (1/4) + 0 \cdot (1/4) = 7.