Gambler's ruin
Indice
Introduzione
Supponiamo di avere due giocatori, ognuno di essi con capitale \(\ell_1 \geq 1\) e \(\ell_2 \geq 1\) relativamente.
Ad ogni turno si lancia una moneta non bilanciata di parametro \(p \in (0,1)\).
Se esce testa (con probabilità \(p\)) vince il giocatore 1, guadagnando una unità di capitale tolto al giocatore 2.
Se esce croce (con probabilità \(1-p\)) vince il giocatore 2, guadagnando una unità di capitale tolto al giocatore 1.
Il gioco finisce quando uno dei due giocatori esaurisce il capitale a sua disposizione; in tal caso l’altro giocatore vince il gioco.
Si chiede di calcolare la probabilità \(q = q(\ell_1, \ell_2, p)\) che il giocatore 1 vinca il gioco.
Ovviamente \(q\) dipende dalla somma dei due capitali \(\ell_1 + \ell_2\) e dalla probabilità \(p\) di vincere un signolo round.
Consideriamo l'insieme
\[
V := \lbrace j \in \mathbb{Z} | -\ell_1 \leq j \leq \ell_2 \rbrace
\]
ovvero l'insieme di tutti i possibili guadagni che può avere il giocatore 1.
Ovviamente tale quantità va da \(-\ell_1\) nel caso in cui 1 perde, fino a \(\ell_2\) quando 1 vince.
Costruiamo ora una catena di Markov omogenea \(\lbrace W_t : t \geq 0 \rbrace\) definita su \(V\) tale che:
- \(W_0 = 0\)
- per ogni \(i \notin \lbrace -\ell_1, \ell_2 \rbrace\) si ha che \(p_{i, i+1} = p\) e \(p_{i, i-1} = 1 - p\).
- per \(i \in \lbrace -\ell_1, \ell_2 \rbrace\) si ha che \(p_{ii} = 1\) e \(p_{ij} = 0\) per ogni \(j \neq i\).
In termini formali
\begin{equation*} p_{ij} = \begin{cases} 1 &\mbox{se } i \in \lbrace -\ell_1 , \ell_2 \rbrace \land j = i\\ 0 &\mbox{se } i \in \lbrace -\ell_1 , \ell_2 \rbrace \land j \neq i\\ p &\mbox{se } i \notin \lbrace -\ell_1 , \ell_2 \rbrace \land j = i + 1\\ 1-p &\mbox{se } i \notin \lbrace -\ell_1 , \ell_2 \rbrace \land j = i - 1\\ 0 &\mbox{se } i \notin \lbrace -\ell_1 , \ell_2 \rbrace \land j \notin \lbrace i-1 , i+1 \rbrace \end{cases} \end{equation*}Per esempio, se consideriamo \(\ell_1 + \ell_2 = 6\) avremo che
\begin{equation*} P = \left ( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 1-p & 0 & p & 0 & 0 & 0 \\ 0 & 1-p & 0 & p & 0 & 0 \\ 0 & 0 & 1-p & 0 & p & 0 \\ 0 & 0 & 0 & 1-p & 0 & p \\ 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right ) \end{equation*}Le prime osservazioni che possiamo porre sono:
- gli stati \(-\ell_1, \ell_2\) sono stati ricorrenti (anzi, addirittura assorbenti ).
- qualsiasi altro stato \(i \notin \lbrace -\ell_1 , \ell_2 \rbrace\) sono stati transienti .
Da queste osservazioni possiamo supporre in maniera intuitiva che prima o poi ci sarà un vincitore, perciò la catena finisce in uno dei due stati assorbenti.
\begin{equation*} \lim_{t \to \infty} P(W_t = j) = \begin{cases} q &\mbox{se } j = \ell_2\\ 1-q &\mbox{se } j = -\ell_1\\ 0 &\mbox{altrimenti} \end{cases} \end{equation*}
dove ricordiamo che \(q\) è la probabilità (che stiamo cercando) che il giocatore 1 vinca.
È utile pensare a \(q\) come un valore in funzione dei parametri \(\ell_1, \ell_2, p\), ovvero \[ q = q(\ell_1, \ell_2, p) \]
Ci poniamo quindi il problema di calcolare \(q\) al variare dei suoi parametri.
Calcolo di \(q\) per \(p = 1/2\)
Introduciamo l'evento
\(Q_i\) = "il gioco verrà assorbito da \(\ell_2\) partendo dallo stato \(i\)"
con probabilità \[ q_i = P(Q_i) \;\; \forall i \in V \] Certamente avremo che \[ q_{\ell_2} = 1\\ q_{-\ell_1} = 0 \] mentre per ogni altro stato \(i \notin \lbrace -\ell_1, \ell_2 \rbrace\) si ha che \[ q_i = \frac{1}{2}q_{i+1} + \frac{1}{2}q_{i-1} \] risolvendo il sistema
\begin{cases} q_i &= \frac{1}{2}q_{i+1} + \frac{1}{2}q_{i-1} \;\;\; \forall i \notin \lbrace -\ell_1, \ell_2 \rbrace\\ q_{\ell_2} &= 1\\ q_{-\ell_1} &= 0 \end{cases}
si ottiene che per ogni stato \(i \in V\) abbiamo che
\[
q_i = \frac{\ell_1 + i}{\ell_1 + \ell_2}
\]
(convincersi di questo).
Ponendo \(i = 0\) avremo trovato il nostro valore di \(q\) \[ q = q_0 = \frac{\ell_1}{\ell_1 + \ell_2} \]
Calcolo di \(q\) per \(p \neq 1/2\)
Come prima, consideriamo la stessa famiglia di eventi \(\lbrace Q_i : i \in V \rbrace\).
In questo caso avremo che
\[
q_i = pq_{i+1} + (1-p)q_{i-1}
\]
mentre \(q_{-\ell_1} = 0\) e \(q_{\ell_2} = 1\).
Come prima, risolvendo il sistema avremo che \[ q_i = \frac{ 1 - \alpha^{i + \ell_1} }{ 1 - \alpha^{\ell_1 + \ell_2} } \] con \[ \alpha = \frac{1-p}{p} \]
In conclusione \[ q = q_0 = \frac{ 1 - \alpha^{\ell_1} }{ 1 - \alpha^{\ell_1 + \ell_2} } \]
Osservazioni su \(q\)
Al variare dei parametri \(\ell_1, \ell_2, p\) avremo che
- Se \(p = 1/2\), avremo \(q = \frac{\ell_1}{\ell_1 + \ell_2}\). Osserviamo che al crescere di \(\ell_2\) avremo che la probabilità \(q\) che il giocatore 1 vinca decresce a 0.
- Se \(p < 1/2\), avremo \(q = \frac{ \alpha^{\ell_1} - 1 }{ \alpha^{\ell_1 + \ell_2} - 1 }\). Al crescere di \(\ell_2\) avremo che la probabilità \(q\) che il giocatore 1 vinca decresce a 0, perchè \(\alpha > 1\).
- Se \(p > 1/2\), avremo \(q = \frac{ 1 - \alpha^{\ell_1} }{ 1 - \alpha^{\ell_1 + \ell_2} }\). Al crescere di \(\ell_2\) avremo che la probabilità \(q\) che il giocatore 1 vinca decresce a \(1 - \alpha^{\ell_1}\), perchè \(\alpha < 1\). Questo è l'unico caso in cui si favorisce il giocatore 1, in quanto al crescere del capitale \(\ell_1\) avremo che \(1 - \alpha^{\ell_1}\) tende ad 1, indipendentemente da \(\ell_2\). Inoltre, essendo sempre vero che \(1 - \alpha^{\ell_1} \geq 1 - \alpha\) (sempre per \(\alpha < 1\)), allora la probabilità di vittoria di \(q\) non scenderà mai al di sotto di \(1 - \alpha\), indipendentemente da qualsiasi capitale.