Laboratorio virtuale > Rosso e nero > 1 2 3 [4] 5

4. Strategie ottimali

Condizione di ottimalità

Ricordiamo che la regola di arresto nel gioco del rosso e nero è di continuare a giocare finché il giocatore non esaurisce la sua ricchezza o non raggiunge la ricchezza obiettivo a. Pertanto la strategia del giocatore consiste nel decidere quanto puntare in ciascuna prova prima di smettere di giocare. Supponiamo di avere una classe di strategie corrispondenti a puntate e ricchezze valide:

A: insieme di ricchezze, Bx: insieme di puntate valide per x A.

Per esempio, a volte (come avviene nel caso del gioco prudente) possiamo voler restringere le ricchezze agli interi compresi tra 0 e a; altre volte (come avviene nel caso del gioco aggressivo) possiamo voler usare l'intervallo [0, 1] come spazio per le ricchezze. Per quanto riguarda le puntate, assumeremo sempre che il giocatore non possa puntare ciò che non ha e che non punti più di quanto gli serve per raggiungere la ricchezza obiettivo. Si hanno quindi le condizioni minime

x A, y Bx implica 0 y min{x, a - x}.

Restringiamo inoltre le strategie a quelle per cui il tempo di arresto N è finito.

Una strategia con funzione di probabilità di vincita V è ottimale se per ogni altra strategia con funzione di probabilità di vincita U si ha

U(x) V(x) for x A.

Esercizio teorico 1. Mostra che, se esiste una strategia ottimale, la funzione di probabilità di vincita è unica.

Può però non esserci una strategia ottimale, o ce ne possono essere molte. Inoltre, la questione dell'ottimalità dipende dal valore della probabilità di vittoria della prova p, oltre che dalla struttura di ricchezze e puntate.

Supponiamo ora che S sia una strategia con funzione di probabilità di vincita V. Vogliamo mostrare che se

pV(x + y) + qV(x - y) V(x) per x A, y Bx,

allora S è ottimale.

Esercizio teorico 2. Considera la seguente strategia: se la ricchezza iniziale è x in A, prendiamo un y in Bx e puntiamo y sulla prima prova, seguiamo poi la strategia S. Condiziona all'esito della prima prova per mostrare che la funzione di probabilità di vincita per tale nuova strategia è

U(x) = pV(x + y) + qV(x - y).

Pertanto, il teorema che stiamo cercando di dimostrare può essere riespresso come segue: se S è ottimale rispetto alla classe di strategie dell'esercizio 2, allora S è ottimale rispetto a tutte le strategie.

Supponiamo ora che la condizione di ottimalità valga. Sia T una strategia arbitraria con funzione di probabilità di vincita U. La variabile casuale V(Xn) può essere interpretata come probabilità di vincita se la strategia del giocatore è sostituita dalla strategia S da n in poi.

Esercizio teorico 3. Condiziona all'esito della prova n-esima per mostrare che

E[V(Xn) | X0 = x] = E[pV(Xn - 1 + Yn) + qV(Xn - 1 - Yn) | X0 = x].

Esercizio teorico 4. Usa il risultato dell'esercizio 3 e la condizione di ottimalità per mostrare che, per n = 1, 2, ...

E[V(Xn) | X0 = x] E[V(Xn - 1) | X0 = x].

Esercizio teorico 5. Usa il risultato dell'esercizio 4 per provare che

E[V(Xn) | X0 = x] V(x) per n = 1, 2, ...

Esercizio teorico 6. Calcola il limite al crescere di n nell'esercizio 5 per mostrare che

E[V(XN) | X0 = x] V(x) dove N è il tempo di arresto per la strategia T.

Esercizio teorico 7. Prova che E[V(XN) | X0 = x] = U(x)

Abbiamo infine mostrato negli esercizi 6 e 7 che la strategia S è di fatto ottimale:

U(x) V(x) per x A.

Prove favorevoli con puntata minima

Supponiamo ora che p 1 / 2, per cui le prove sono favorevoli (o almeno non sfavorevoli) per il giocatore. Mostreremo ora che se il banco vuole che tutte le puntate siano multiplo di una puntata minima (che è quanto avviene nelle case da gioco reali), la strategia ottimale è quella prudente, facendo la puntata minima ad ogni prova fino alla fine del gioco.

Assumiamo in primo luogo che tutte le puntate siano multipli di un'unità minima, che possiamo assumere essere 1$. Gli insiemi di ricchezze e di puntate valide sono quindi

A = {0, 1, ..., a}, Bx = {0, 1, ..., min{x, a - x}}.

Sia f la funzione di probabilità di vincita per il gioco prudente. Per mostrare che la strategia di gioco prudente è ottimale, basta verificare che la condizione di ottimalità è soddisfatta, cioè in questo caso

pf(x + y) + qf(x - y) f(x) per x in A, y in Bx.

Esercizio teorico 8. Mostra che la condizione di ottimalità è soddisfatta per p = 1 / 2.

Esercizio teorico 9. Se p > 1 / 2, mostra che la condizione di ottimalità è equivalente a

p(q / p)x + y + q(q / p)x - y (q / p)x.

Esercizio teorico 10. Mostra che la disuguaglianza dell'esercizio precedente equivale a

pq(py - qy)(py - 1 - qy - 1) 0.

La disuguaglianza dell'ultimo esercizio è soddisfatta per p> 1 / 2, per cui il gioco prudente è ottimale quando le prove sono favorevoli.

Simulazione 11. Nel gioco del rosso e nero, poni a = 16, x = 8 e p = 0.55. Definisci una strategia a piacimento e gioca 100 partite. Confronta la tua frequenza relativa di vittoria con la probabilità di vincita del gioco prudente.

Prove favorevoli senza puntata minima

Assumiamo ora che il banco ammetta puntate arbitrariamente piccole e che p > 1/2, per cui le prove sono strettamente favorevoli. In questo caso è naturale prendere come obiettivo l'unità monetaria, per cui l'insieme di ricchezze e puntate diventa

A = [0, 1], Bx = [0, min{x, 1 - x}} per x A.

Mostreremo che V(x) = 1 per x in (0, 1]. I risultati ricavati per il gioco prudente ricoprono un ruolo molto importante per la nostra analisi, per cui indicheremo con f(j; a) la probabilità di raggiungere un intero obiettivo a, partendo dall'intero j appartenente a [0, a], con puntate unitarie.

Fissiamo in primo luogo una ricchezza iniziale razionale x = k / n in [0, 1].

Esercizio teorico 12. Sia m un intero positivo. Supponi che, a partire da x, il giocatore punti 1/mn su ciascuna prova. Prova che ciò equivale al gioco prudente con obiettivo mn e ricchezza inziale mk e che quindi la probabilità di raggiungere l'obiettivo 1 è f(mk; mn).

Esercizio teorico 13. Prova che

f(mk; mn) converge a 1 per m converge a infinito.

Esercizio teorico 14. Usa i risultati degli esercizi 6 e 7 per provare che

V(x) = 1 se x (0, 1] è razionale.

Esercizio teorico 15. Usa il risultato dell'esercizio precedente e il fatto che V è crescente per provare che

V(x) = 1 per ogni x (0, 1].

Prove sfavorevoli

Assumiamo ora che p 1 / 2, per cui le prove sono sfavorevoli, o almeno non favorevoli. Mostreremo che il gioco aggressivo è ottimale. Come in precedenza, considereremo la ricchezza obiettivo come l'unità monetaria di base e consentiremo di puntare ogni frazione valida di tale unità. Gli insiemi di ricchezze e puntate sono quindi

A = [0, 1], Bx = [0, min{x, 1 - x}] per x A.

Sia F la funzione di probabilità di vincita per il gioco aggressivo. Per mostrare che tale strategia è ottimale, basta mostrare che soddisfa la condizione generale di ottimalità.

Esercizio teorico 16. Mostra che la condizione di ottimalità è equivalente a

D(r, s) = F[(r + s) / 2] - pF(s) - qF(r) 0 per 0 r s 1.

Esercizio teorico 17. Usa la continuità di F per mostrare che è sufficiente provare la disuguaglianza dell'esercizio 16 nel caso in cui r e s sono binari razionali.

Useremo ora l'induzione su m per mostrare che la disuguaglianza dell'esercizio 16 è verificata se r e s sono binari razionali di rango m o meno, con m = 0, 1, ...

Esercizio teorico 18. Prova che la disuguaglianza dell'esercizio 16 è verificata se r e s hanno rango 0; mostra cioè che la disgugaglianza vale per

  1. r = 0, s = 0,
  2. r = 0, s = 1,
  3. r = 1, s = 1.

Supponiamo ora che la disuguaglianza dell'esercizio 16 valga per r e s di rango m o inferiore, per un dato m. Supponiamo inoltre che r e s abbiano rango m + 1 o inferiore. Mostreremo che la disuguaglianza è soddisfatta in ciascuno dei seguenti quattro casi

  1. r s 1 / 2
  2. 1 / 2 r s
  3. r (r + s) / 2 1 / 2 s
  4. r 1 / 2 (r + s) / 2 s

L'equazione funzionale di base per F sarà il nostro principale strumento di lavoro.

Esercizio teorico 19. Mostra che, nel caso (a), D(r, s) = pD(2r, 2s)

Esercizio teorico 20. Mostra che, nel caso (b), D(r, s) = qD(2r - 1, 2s - 1)

Esercizio teorico 21. Per il caso (c), segui i passi proposti:

  1. D(r, s) = pF(r + s) - p[p + qF(2s - 1)] - q[pF(2r)]
  2. 1 / 2 r + s 1 so F(r + s) = p + qF(2r + 2s - 1)
  3. 0 r + s - 1 / 2 1 / 2 per cui F(r + s - 1 / 2) = pF(2r + 2s - 1)
  4. D(r, s) = q[F(r + s - 1 / 2) - pF(2s - 1) - pF(2r)]
  5. Se 2s - 1 2r allora D(r, s) = (q - p)F(2s - 1) + qD(2s - 1, 2r)
  6. Se 2r 2s - 1 allora D(r, s) = (q - p)F(2r) + qD(2r, 2s - 1)

Esercizio teorico 22. Per il caso (d), segui i passi proposti:

  1. D(r, s) = [p + qF(r + s - 1)] - p[p + qF(2s - 1)] - q[pF(2r)]
  2. 0 r + s - 1 1 / 2 so F(r + s - 1) = pF(2r + 2s - 2)
  3. 1 / 2 r + s - 1 1 per cui F(r + s - 1 / 2) = p + qF(2r + 2s - 2)
  4. D(r, s) = p(q - p) + p[F(r + s - 1 / 2) - qF(2s - 1) - qF(2r)]
  5. Se 2s - 1 2r allora D(r, s) = p(q - p)[1 - F(2r)] + pD(2s - 1, 2r)
  6. Se 2r 2s - 1 allora D(r, s) = p(q - p)[1 - F(2s - 1)] + pD(2r, 2s - 1)

Esercizio teorico 23. Usa l'ipotesi di induzione e i risultati degli esercizi precedenti per terminare la dimostrazione del fatto che il gioco aggressivo è ottimale nel caso in cui le prove siano sfavorevoli.

Simulazione 24. Nel gioco del rosso e nero, poni a = 16, x = 8 e p = 0.45. Definisci una strategia a piacimento e gioca 100 partite. Confronta la tua frequenza relativa di vittoria con la probabilità di vincita del gioco aggressivo.

Laboratorio virtuale > Rosso e nero > 1 2 3 [4] 5
Sommario | Applets | Dati | Biografie | Risorse | Indice analitico | ©