In un sacchetto vi sono quattro palle, di quattro colori diversi. Il giochino consiste nel prendere le palle, due alla volta, in sequenza, e nel colorare la prima dello stesso colore della seconda. Le palle tinte a nuovo vengon rimesse nel sacchetto e, manco a dirlo, fatte girare.
Orbene, ad un certo punto succederà che le palle, a furia di girare, saranno diventate tutte dello stesso colore: quante girate di palle occorreranno in media (expectation) per ottenere tale risultato?

PRIMA estraz.
qualsiasi combinazione porta allo stesso risultato: vengono re-immesse nel sacco
2 palle dello stesso colore e altre due palle diverse tra loro e dalle due uguali, cioè:
AACD

SECONDA estraz.si hanno dodici differenti situazioni equiprobabili (questa volta, conta anche l'ordine di estrazione!)
il risultato è che cinque combinazioni di re-immissione si presentano due volte su 12 e altre due una volta per una, in particolare:
AACD due volte
AAAD "
AAAC "
ACCD "
ACDD "
AACC una volta
AADD "

passo.

Intanto posso dire che una mia simulazione mi porta a concludere che per ottenere il risultato voluto, in media, occorre far girare le palle 9 volte.
Il minimo dei tiri necessari sono 3 e la probabilità che questo avvenga è di 1/12: sinceramente non riesco ancora a vedere come si possa calcolare il numero medio di giri da fare, seguendo la strada del calcolo delle probabilità per il conseguimento del risultato in 3, 4, 5, 6....x giri (per x tendente all'infinito?).

effettivamente, il valore atteso è 9... Volete il malloppo?

sono daccordo con Pasquale: anche la prosecuzione della mia esplorazione analitica, porta, alla terza estrazione, ai primi casi di Monocromia.
Per la precisione abbiamo che 4/12 elle situazioni sono "papabili" per portare alla conclusione alla terza mossa; sto ovviamente parlando delle combinazioni
AAAC
AAAD
che ricorrono due volte ciascuna (sulle 12 combinazioni possibili dopo due mosse)
partendo da questa situazione, accade che 3 volte su 4 la prima estratta è del colore dominante, e la seconda avrà una probabilità SU TRE di essere quella diversa
4/12 * 3/4 * 1/3 = 1/12

Sarei curioso di vedere (pasquale?) il grafico dei risultati, oltre alla distribuzione delle situazioni ad esempio dopo 5, o 10, o 20 "giramenti di palle" (considerando i casi in cui il gioco non sia ancora concluso, of course). Sarei tentato di ipotizzare che la percentuali di casi "con tre palle dello stesso colore" , di "due palle dello stesso colore e due diverse" e di "due coppie di palle" tende a stabilizzarsi

se così fosse, e se la percentuale di AAAX fosse stabile attorno ad 1/3, ogni volta avremmo l'en plein in 1/12 dei casi rimanenti
1/12 + 11/144 + 121/ 1728 .....
se&o

Dato che ci state lavorando tarderò ancora qualche giorno a dare la mia risposta (che è piuttosto articolata)

No Delfo, non ho fatto lo studio che tu chiedi, ma semplicemente ho simulato il gioco così come descritto: ne ho fatti molti ed ho annotato il numero di giri di palle necessario ad ogni gioco (3, 10,15,20,7, etc).
Ho fatto 1000 giochi, poi 10.000, poi 100.000, 1.000.000, 10.000.000 e quindi la somma del numero di giri di palle, diviso il numero dei giochi effettuati, mi ha dato il numero di giri necessario in media: aumentando il numero di giochi, ho potuto vedere che la media si è attestata con sempre maggiore precisione intorno ai 9 giri.

Per Panurgo: direi che ancora è presto per dare la soluzione....può darsi che qualcun altro stia studiando ancora, che altri non si siano accorti del problema, ma che adesso inizino a studiarlo...c'è tempo, c'è tempo....ci sono le richieste di chiarimento, le richieste di suggerimenti, infine la richiesta della soluzione.

Questo era andato nel dimenticatoio e penso che Panurgo a questo punto potrebbe illustrare il suo malloppo.

Ero sempre io

Pasquale ha scritto:Questo era andato nel dimenticatoio e penso che Panurgo a questo punto potrebbe illustrare il suo malloppo.

...ed ecco il...

Malloppo del giramento di palle

Abbiano quattro palle di quattro colori diversi: indichiamo questa situazione con ${\text ABCD}$. Le possibili combinazioni di quattro colori presi a due a due sono dodici (quattro per la prima palla, tre per la seconda).
Vediamo che succede al primo giro di palle:

${\text AB} \to {\text BBCD} \\ {\text AC} \to {\text BCCD} \\ {\text AD} \to {\text BCDD} \\ {\text BA} \to {\text AACD} \\ {\text BC} \to {\text ACCD} \\ {\text BD} \to {\text ACDD} \\ {\text CA} \to {\text AABD} \\ {\text CB} \to {\text ABBD} \\ {\text CD} \to {\text ABDD} \\ {\text DA} \to {\text AABC} \\ {\text DB} \to {\text ABBC} \\ {\text DC} \to {\text ABCC}$

Naturalmente, noi non siamo interessati ad un colore particolare e quindi ${\text A}$, ${\text B}$, ${\text C}$ e ${\text D}$ sono etichette che possono essere scambiate tra di loro: dovrebbe quindi essere evidente che tutte le dodici situazioni che otteniamo sono fra loro equivalenti e le indichiamo con ${\text AABC}$ (due palle dello stesso colore e due di colori diversi).

Vediamo ora che succede al secondo giro di palle:

${\text AA} \to {\text AABC} \equiv {\text AABC} \\ {\text AB} \to {\text ABBC} \equiv {\text AABC} \\ {\text AC} \to {\text ABCC} \equiv {\text AABC} \\ {\text AA} \to {\text AABC} \equiv {\text AABC} \\ {\text AB} \to {\text ABBC} \equiv {\text AABC} \\ {\text AC} \to {\text ABCC} \equiv {\text AABC} \\ {\text BA} \to {\text AAAC} \equiv {\text AAAB} \\ {\text BA} \to {\text AAAC} \equiv {\text AAAB} \\ {\text BC} \to {\text AACC} \equiv {\text AABB} \\ {\text CA} \to {\text AAAB} \equiv {\text AAAB} \\ {\text CA} \to {\text AAAB} \equiv {\text AAAB} \\ {\text CB} \to {\text AABB} \equiv {\text AABB}$

In questo caso abbiamo sei possibilità di rimanere nella stessa situazione (${\text AABC}$, sempre considerando le etichette scambiabili), due di passare a ${\text AABB}$ e quattro di passare a ${\text AAAB}$: notate che non c'è modo di tornare a ${\text ABCD}$ ovvero il numero di colori presenti può solo restare immutato o diminuire.

Per il terzo giro di palle le situazioni possibili sono tre: ${\text AABC}$, ${\text AABB}$ e ${\text AAAB}$. La prima l'abbiamo già studiata; per la seconda

${\text AA} \to {\text AABB} \equiv {\text AABB} \\ {\text AB} \to {\text ABBB} \equiv {\text AAAB} \\ {\text AB} \to {\text ABBB} \equiv {\text AAAB} \\ {\text AA} \to {\text AABB} \equiv {\text AABB} \\ {\text AB} \to {\text ABBB} \equiv {\text AAAB} \\ {\text AB} \to {\text ABBB} \equiv {\text AAAB} \\ {\text BA} \to {\text AAAB} \equiv {\text AAAB} \\ {\text BA} \to {\text AAAB} \equiv {\text AAAB} \\ {\text BB} \to {\text AABB} \equiv {\text AABB} \\ {\text BA} \to {\text AAAB} \equiv {\text AAAB} \\ {\text BA} \to {\text AAAB} \equiv {\text AAAB} \\ {\text BB} \to {\text AABB} \equiv {\text AABB}$

Qui abbiamo quattro modi di rimanere nella stessa situazione (${\text AABB}$) e otto modi di passare a ${\text AAAB}$ (o a ${\text ABBB}$ che è equivalente)

Consideriamo ora ${\text AAAB}$:

${\text AA} \to {\text AAAB} \\ {\text AA} \to {\text AAAB} \\ {\text AB} \to {\text AABB} \\ {\text AA} \to {\text AAAB} \\ {\text AA} \to {\text AAAB} \\ {\text AB} \to {\text AABB} \\ {\text AA} \to {\text AAAB} \\ {\text AA} \to {\text AAAB} \\ {\text AB} \to {\text AABB} \\ {\text BA} \to {\text AAAA} \\ {\text BA} \to {\text AAAA} \\ {\text BA} \to {\text AAAA}$

Qui ci sono tre modi di passare a ${\text AABB}$, sei di rimanere fermi (${\text AAAB}$) e tre di finire il giramento (${\text AAAA}$). Ovviamente, se siamo in ${\text AAAA}$ possiamo solo pescare palle dello stesso colore!

Riassumendo (vedi figura), abbiamo un certo numero di stati: ${\text ABCD}$, ${\text AABC}$, ${\text AABB}$, ${\text AAAB}$, ${\text AAAA}$; abbiamo tre tipi di transizioni: quelle che lasciano tutto immutato, quelle che conservano il numero di colori e quelle che lo diminuiscono di uno.



Raccogliamo in una matrice le probabilità di transizione

${\text M} = \frac{1}{{12}}\left( {\begin{array}{ccccc} 0 & 0 & 0 & 0 & 0 \\ {12} & 6 & 0 & 0 & 0 \\ 0 & 2 & 4 & 3 & 0 \\ 0 & 4 & 8 & 6 & 0 \\ 0 & 0 & 0 & 3 & {12} \\ \end{array}} \right) = \left( {\begin{array}{ccccc} 0 & 0 & 0 & 0 & 0 \\ 1 & {\frac 1 2} & 0 & 0 & 0 \\ 0 & {\frac 1 6} & {\frac 1 3} & {\frac 1 4} & 0 \\ 0 & {\frac 1 3} & {\frac 2 3} & {\frac 1 2} & 0 \\ 0 & 0 & 0 & {\frac 1 4} & 1 \\ \end{array}} \right)$

in un vettore le probabilità iniziali di ciascuno stato: 1 per ${\text ABCD}$, 0 per gli altri stati

${\text y}_{\script 0} = \left( {\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array} } \right)$

E' sufficiente moltiplicare la matrice per il vettore per ottenere un nuovo vettore che contiene le probabilità di ciascuno stato dopo il primo giramento di palle

${ \text y}_{\script 1} = {\text My}_{\script 0} = \left( {\begin{array}{ccccc} 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 1 \hfill & {\frac 1 2} \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 0 \hfill & {\frac 1 3} \hfill & {\frac 1 3} \hfill & {\frac 1 4} \hfill & 0 \hfill \\ 0 \hfill & {\frac 1 6} \hfill & {\frac 2 3} \hfill & {\frac 1 2} \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & 0 \hfill & {\frac 1 4} \hfill & 1 \hfill \\ \end{array} } \right)\left( {\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array} } \right) = \left( {\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ \end{array} } \right)$

La probabilità di ciascuno stato dopo il secondo giramento di palle si ottiene moltiplicando la matrice di transizione per il secondo vettore

${ \text y}_{\script 2} = {\text My}_{\script 1} = \left( {\begin{array}{c} 0 \hfill \\ {\frac 1 2} \hfill \\ {\frac 1 6} \hfill \\ {\frac 1 3} \hfill \\ 0 \hfill \\ \end{array} } \right)$

quella dopo il terzo giramento di palle vale

${ \text y}_{\script 3} = {\text My}_{\script 2} = \left( {\begin{array}{c} 0 \hfill \\ {\frac 1 4} \hfill \\ {\frac 2 9} \hfill \\ {\frac 4 9} \hfill \\ {\frac 1 {12}} \hfill \\ \end{array} } \right)$

quella dopo il quarto

${\text y}_{\script 4} = {\text My}_{\script 3} = \left( {\begin{array}{c} 0 \hfill \\ {\frac 1 8} \hfill \\ {\frac {49} {216}} \hfill \\ {\frac {49} {108}} \hfill \\ {\frac 7 {36}} \hfill \\ \end{array} } \right)$

Come si vede, le probabilità degli stati intermedi diminuiscono mentre aumenta la probabilità dello stato finale: in generale sarà ${ \text y}_{\script r} = {\text M}^{\script r} {\text y}_0$.

Per trovare ${ \text M}^{\script r}$ si procede calcolando gli autovalori di ${ \text M}$, soluzioni dell'equazione $\left| {{\text M} - \lambda {\text I}} \right| = 0$ ovvero

$\left| {\begin{array}{ccccc} {0 - \lambda } \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 1 \hfill & {\frac 1 2 - \lambda } \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 0 \hfill & {\frac 1 3} \hfill & {\frac 1 3 - \lambda } \hfill & {\frac 1 4} \hfill & 0 \hfill \\ 0 \hfill & {\frac 1 6} \hfill & {\frac 2 3} \hfill & {\frac 1 2 - \lambda } \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & 0 \hfill & {\frac 1 4} \hfill & {1 - \lambda } \hfill \\ \end{array} } \right| = 0$

sviluppando il determinante si vede che basta considerare gli elementi intorno alla diagonale della matrice

$\left| {\begin{array}{cccccccc} {0 - \lambda } \hfill &| & {} \hfill &| & {} \hfill & {} \hfill &| & {} \hfill \\ \hline 1 \hfill &| & {\frac 1 2 - \lambda } \hfill &| & {} \hfill & {} \hfill &| & {} \hfill \\ \hline {} \hfill &| & {\frac 1 3} \hfill &| & {\frac 1 3 - \lambda } \hfill & {\frac 1 4} \hfill &| & {} \hfill \\ {} \hfill &| & {\frac 1 6} \hfill &| & {\frac 2 3} \hfill & {\frac 1 2 - \lambda } \hfill &| & {} \hfill \\ \hline {} \hfill &| & {} \hfill &| & {} \hfill & {\frac 1 4} \hfill &| & {1 - \lambda } \hfill \\ \end{array} } \right| = 0$

cioè

$\left( {0 - \lambda } \right)\left( {\frac 1 2 - \lambda } \right)\left| {\begin{array}{cc} {\frac 1 3 - \lambda } & {\frac 1 4} \\ {\frac 2 3} & {\frac 1 2 - \lambda } \\ \end{array} } \right|\left( {1 - \lambda } \right) = 0$

che valgono

$\left( {0 - \lambda } \right)^2 \left( {\frac 1 2 - \lambda } \right)\left( {\frac 5 6 - \lambda } \right)\left( {1 - \lambda } \right) = 0$

La matrice degli autovalori è quindi

${ \text \Lambda } = \text{diag}\left\{ {\text{0}\text{,0}\text{,}\frac{\text{1}}{\text{2}},\frac{\text{5}}{\text{6}},1} \right\} = \left( {\begin{array}{ccccc} 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & {\frac 1 2} \hfill & 0 \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & 0 \hfill & {\frac 5 6} \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 1 \hfill \\ \end{array} } \right)$

Si cercano gli autovettori corrispondenti (preferisco non normalizzarli per avere numeri razionali) e si riuniscono in una matrice di similitudine

${ \text S} = \left( {\begin{array}{ccccc} { - 1} \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 2 \hfill & 0 \hfill & 2 \hfill & 0 \hfill & 0 \hfill \\ 2 \hfill & 3 \hfill & { - 1} \hfill & 1 \hfill & 0 \hfill \\ { - 4} \hfill & { - 4} \hfill & { - 2} \hfill & 2 \hfill & 0 \hfill \\ 1 \hfill & 1 \hfill & 1 \hfill & { - 3} \hfill & 1 \hfill \\ \end{array} } \right)$

della quale si trova l'inversa

${ \text S}^{\script - 1} = \left( {\begin{array}{ccccc} { - 1} \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ {\frac 4 5} \hfill & 0 \hfill & {\frac 1 5} \hfill & {-\frac 1 {10}} \hfill & 0 \hfill \\ 1 \hfill & {\frac 1 2} \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ {\frac 3 5} \hfill & {\frac 1 2} \hfill & {\frac 2 5} \hfill & {\frac 3 {10}} \hfill & 0 \hfill \\ 1 \hfill & 1 \hfill & 1 \hfill & 1 \hfill & 1 \hfill \\ \end{array} } \right)$

E' facile verificare che

${ \text S}^{\script - 1} {\text MS} = {\text \Lambda }$

e quindi

${ \text M} = {\text S\Lambda S}^{\script - 1} \\ {\text y}_{\script r} = {\text M}^{\script r} {\text y}_{\script 0} = {\text S\Lambda }^{\script r} {\text S}^{\script - 1} {\text y}_{\script 0}$

ed infine

${ \text y}_r = \left( {\begin{array}{ccccc} 0 \hfill \\ {2\left( {\frac{1}{2}} \right)^{\script r} } \hfill \\ { - \left( {\frac{1}{2}} \right)^{\script r} + \frac{3}{5}\left( {\frac{5}{6}} \right)^{\script r} } \hfill \\ { - 2\left( {\frac{1}{2}} \right)^{\script r} + \frac{6}{5}\left( {\frac{5}{6}} \right)^{\script r} } \hfill \\ {\left( {\frac{1}{2}} \right)^{\script r} - \frac{9}{5}\left( {\frac{5}{6}} \right)^{\script r} + 1} \hfill \\ \end{array} } \right)$

L'ultimo elemento di questo vettore è la distribuzione cumulativa di probabilità di finire il gioco in $r$ giramenti di palle

$F\left( r \right) = \left( {\frac{1}{2}} \right)^{\script r} - \frac{9}{5}\left( {\frac{5}{6}} \right)^{\script r} + 1$

dato che si tratta di una distribuzione discreta, la distribuzione di densità di probabilità è data da

$p\left( r \right) = \left\{ {\begin{array}{cc} 0 & {\quad r = 1} \\ {F\left( r \right) - F\left( {r - 1} \right)} & {\quad r > 1} \\ \end{array} } \right.$

ovvero

$p\left( r \right) = \left\{ {\begin{array}{cc} 0 & {\quad r = 1} \\ { - \frac{1}{2}\left( {\frac{1}{2}} \right)^{\script r – 1} + \frac{3}{{10}}\left( {\frac{5}{6}} \right)^{\script r - 1} } & {\quad r > 1} \\ \end{array} } \right.$

e l'expectation (valore atteso) di $r$ vale

$\left\langle r \right\rangle = \sum\limits_{\script r = 1}^{\script \infty} {rp\left( r \right)} = - \frac{1}{2}\sum\limits_{\script r = 2}^{\script \infty} {\left [ {r\left( {\frac{1}{2}} \right)^{ \script r - 1} } \right ]} + \frac{3}{{10}}\sum\limits_{\script r = 2}^{\script \infty} {\left [ {r\left( {\frac{5}{6}} \right)^{ \script r - 1} } \right ]}$

ma

$\sum\limits_{\script r = 2}^{\script \infty} {\left[ {r\left( {\frac{1}{2}} \right)^{ \script r - 1} } \right]} = \sum\limits_{\script r = 1}^{\script \infty} {\left[ {r\left( {\frac{1}{2}} \right)^{ \script r - 1} } \right]} - 1$

e

$\sum\limits_{\script r = 2}^{\script \infty} {\left[ {r\left( {\frac{5}{6}} \right)^{ \script r - 1} } \right]} = \sum\limits_{\script r = 1}^{\script \infty} {\left[ {r\left( {\frac{5}{6}} \right)^{ \script r - 1} } \right]} - 1$

quindi

$\left\langle r \right\rangle = - \frac{1}{2}\left\{ {\sum\limits_{\script r = 1}^{\script \infty} {\left[ {r\left( {\frac{1}{2}} \right)^{ \script r - 1} } \right]} - 1} \right\} + \frac{3}{{10}}\left\{ {\sum\limits_{\script r = 1}^{\script \infty} {\left[ {r\left( {\frac{5}{6}} \right)^{ \script r - 1} } \right]} - 1} \right\}$

Per trovare la somma di $\sum\limits_{\script r = 1}^{\script \infty} {\left [ {r\left( {\frac{1}{2}} \right)^{ \script r - 1} } \right ]}$ si può ragionare così: consideriamo una serie geometrica di ragione $\frac 1 2$

$\sum\limits_{\script r = 0}^{\script \infty} {\left( {\frac{1}{2}} \right)^{ \script r} = } \frac{1}{{1 - \frac{1}{2}}}$

derivando entrambi i termini rispetto a $\frac 1 2$

$\frac{d}{{d\left( {\script {\frac{1}{2}}} \right)}}\sum\limits_{\script r = 0}^{\script \infty} {\left( {\frac{1}{2}} \right)^{ \script r} } = \frac{d}{{d\left( {\script {\frac{1}{2}}} \right)}}\frac{1}{{1 - \frac{1}{2}}}$

si ottiene

$\sum\limits_{\script r = 0}^{\script \infty} {\left [ {r\left( {\frac{1}{2}} \right)^{ \script r - 1} } \right ]} = \sum\limits_{\script r = 1}^{\script \infty} {\left [ {r\left( {\frac{1}{2}} \right)^{ \script r - 1} } \right ]} = \frac{1}{{\left( {1 - \frac{1}{2}} \right)^{ \script 2} }}$

e il gioco è fatto!

Per l'altra sommatoria si ragiona in modo analogo e si ottiene

$\left\langle r \right\rangle = - \frac{1}{2}\left\{ {4 - 1} \right\} + \frac{3}{{10}}\left\{ {36 - 1} \right\} = 9$



P.S.: vi abbiamo presentato "le catene di Markov"; a seguire, prossimamente, alcune (per me) mirifiche considerazioni.

Gulp!