I gormiti

[panurgo]

La prima metà è giusta. La seconda no!

supponiamo che sia $n = 4$

vado da $0$ a $1$ in $\frac 4 4$ passo, da $1$ a $2$ in $\frac 4 3$ passi, da $2$ a $3$ in $\frac 4 2$ passi, da $3$ a $4$ in $\frac 4 1$ passi: quindi vado da $0$ a $3$ in $\frac {25} 3$ passi


P.S.: $I$ è l'insieme delle informazioni che definiscono il problema (cioè la probabilità è sempre condizionata)

[Admin]

Ok Guido, grazie mille!
adesso ci sono!

ora il valore atteso finale che tu hai calcolato, cioè quello non dipendente da $k$, ci dice in media quanti gormiti dobbiamo acquistare per incrementare la collezione di un pezzo, indipendentemente da quandi già ne possediamo della collezione.

in effetti ciò non è vero, in quanto per ottenere ciò si deve dividere per $n$ il valore atteso finale $\left \langle {r \/ | \/ I} \right \rangle \/ = \/ n \/ \sum \limits_{\script k = 1}^{\script n} {\frac 1 k}$.

Mi è tutto più chiaro.
Adesso ho "rieducato" un pò di più la mia intuizione.

Ciao
Admin

[panurgo]

Eh! Ma non crederete mica che sia finita qui? come! Mi conoscete così bene e pensate che io possa accontentermi di una risposta così semplice?

Identifichiamo dunque $n \/ + \/ 1$ stati: possiedo almeno $0$ gormiti diversi, possiedo almeno $1$ gormita diverso, possiedo almeno $2$ gormiti diversi ecc.

Se possiedo almeno $0$ gormiti diversi, ho una probabilità di $\frac n n$ di passare a possedere, al turno successivo, almeno $1$ gormita diverso;se possiedo almeno $1$ gormita diverso, ho una probabilità di $\frac {n - 1} n$ di passare a possedere, al turno successivo, almeno $2$ gormiti diversi ecc.

La situazione è riassunta in questo diagramma



Raggruppando le probabilità di transizione in una matrice si ottiene

${\mathbf M} \/ = \/ \frac 1 n \/ \left ( \begin{array}{c30c30c30c30c30c30c30C20C20C20C20C20C20C20} 0 & & & & & & \\ n & 1 & & & & & \\ & n-1 & 2 & & & & \\ & & n-2 & \ddots & & & \\ & & & \ddots & n-2 & & \\ & & & & 2 & n-1 & \\ &&&&&1&n \\ \end{array} \right )$

cioè

$M_{\script i,i} \/ = \/ \frac {i-1} n \\ M_{\script i+1,i} \/ = \/ \frac {n - i + 1} n$

Una matrice di questo tipo ha per determinante il prodotto degli elementi della diagonale che corrispondono quindi agli autovalori della matrice stessa

$\lambda_{\script i} \/ = \/ \frac {i - 1} n$

Proviamo con $n \/ = \/ 4$, la matrice di transizione è

${\mathbf M} \/ = \/ \frac 1 4 \/ \left ( \begin{array}{c30c30c30c30c30C20C20C20C20C20} 0&0&0&0&0 \\ 4&1&0&0&0 \\ 0&3&2&0&0 \\ 0&0&2&3&0 \\ 0&0&0&1&4 \\ \end{array}\right)$

i suoi autovalori sono

${\mathbf \lambda} \/ = \/ \frac 1 4 \/ \left \{ 0, \/ 1, \/ 2, \/ 3, \/ 4\right \}$

risolvendo il sistema

$\left ({\mathbf M} \/ - \/ {\text diag} \/ \lambda_{\script k} \right ) \/ {\mathbf S}_{\script k} \/ = \/ {\mathbf 0}$

si trova la matrice degli autovettori: per il primo autovalore

$\left ( \begin{array}{c30c30c30c30c30C20C20C20C20C20} 0&0&0&0&0 \\ 4&1&0&0&0 \\ 0&3&2&0&0 \\ 0&0&2&3&0 \\ 0&0&0&1&4 \\ \end{array}\right) \left ( \begin{array}{c30C20C20C20C20C20} S_{\script 1,1} \\ S_{\script 2,1} \\ S_{\script 3,1} \\ S_{\script 4,1} \\ S_{\script 5,1} \\ \end{array}\right ) \/ = \/ \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array}\right ) \qquad \Rightarrow \qquad \left \{ {\begin{array} {l C30C30C30C30C30} 0\/ = \/ 0 \\ S_{\script 2,1} \/ = \/ - \frac 4 1 S_{\script 1,1} \\ S_{\script 3,1} \/ = \/ - \frac 3 2 S_{\script 2,1} \/ = \/ \frac {4 \cdot 3} {1 \cdot 2} S_{\script 1,1} \\ S_{\script 4,1} \/ = \/ - \frac 2 3 S_{\script 3,1} \/ = \/ - \frac {4 \cdot 3 \cdot 2} {1 \cdot 2 \cdot 3} S_{\script 1,1} \\ S_{\script 5,1} \/ = \/ - \frac 1 4 S_{\script 4,1} \/ = \/ \frac {4 \cdot 3 \cdot 2 \cdot 1} {1 \cdot 2 \cdot 3 \cdot 4} S_{\script 1,1} \\ \end{array}} \right. \qquad \Rightarrow \qquad \left ( \begin{array}{c30C20C20C20C20C20} 1 \\ -4 \\ 6 \\ -4 \\ 1 \\ \end{array}\right )$

per il secondo autovalore

$\left ( \begin{array}{c30c30c30c30c30C20C20C20C20C20} -1&0&0&0&0 \\ 4&0&0&0&0 \\ 0&3&1&0&0 \\ 0&0&2&2&0 \\ 0&0&0&1&3 \\ \end{array}\right) \left ( \begin{array}{c30C20C20C20C20C20} S_{\script 1,2} \\ S_{\script 2,2} \\ S_{\script 3,2} \\ S_{\script 4,2} \\ S_{\script 5,2} \\ \end{array}\right ) \/ = \/ \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array}\right ) \qquad \Rightarrow \qquad \left \{ {\begin{array} {l C30C30C30C30} -S_{\script 1,2} \/ = \/ 4 \/ S_{\script 1,2} \/ = \/ 0 \\ S_{\script 3,2} \/ = \/ - \frac 3 1 S_{\script 2,2} \\ S_{\script 4,2} \/ = \/ - \frac 2 2 S_{\script 3,2} \/ = \/ \frac {3 \cdot 2} {1 \cdot 2} S_{\script 2,2} \\ S_{\script 5,2} \/ = \/ - \frac 1 3 S_{\script 4,2} \/ = \/ \frac {3 \cdot 2 \cdot 1} {1 \cdot 2 \cdot 3} S_{\script 2,2} \\ \end{array}} \right. \qquad \Rightarrow \qquad \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 1 \\ -3 \\ 3 \\ -1 \\ \end{array}\right )$

per il terzo

$\left ( \begin{array}{c30c30c30c30c30C20C20C20C20C20} -2&0&0&0&0 \\ 4&-1&0&0&0 \\ 0&3&0&0&0 \\ 0&0&2&1&0 \\ 0&0&0&1&2 \\ \end{array}\right) \left ( \begin{array}{c30C20C20C20C20C20} S_{\script 1,3} \\ S_{\script 2,3} \\ S_{\script 3,3} \\ S_{\script 4,3} \\ S_{\script 5,3} \\ \end{array}\right ) \/ = \/ \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array}\right ) \qquad \Rightarrow \qquad \left \{ {\begin{array} {l C30C30C30C30} -2 \/ S_{\script 1,3} \/ = \/ 0 \\ S_{\script 2,3} \/ = \/ 4 \/ S_{\script 1,3} \/ = \/ 0 \\ S_{\script 4,3} \/ = \/ - \frac 2 1 S_{\script 3,3} \\ S_{\script 5,3} \/ = \/ - \frac 1 2 S_{\script 4,3} \/ = \/ \frac {2 \cdot 1} {1 \cdot 2} S_{\script 3,3} \\ \end{array}} \right. \qquad \Rightarrow \qquad \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 0 \\ 1 \\ -2 \\ 1 \\ \end{array}\right )$

per il quarto

$\left ( \begin{array}{c30c30c30c30c30C20C20C20C20C20} -3&0&0&0&0 \\ 4&-2&0&0&0 \\ 0&3&-1&0&0 \\ 0&0&2&0&0 \\ 0&0&0&1&1 \\ \end{array}\right) \left ( \begin{array}{c30C20C20C20C20C20} S_{\script 1,4} \\ S_{\script 2,4} \\ S_{\script 3,4} \\ S_{\script 4,4} \\ S_{\script 5,4} \\ \end{array}\right ) \/ = \/ \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array}\right ) \qquad \Rightarrow \qquad \left \{ {\begin{array} {l C30C30C30C30} -3 \/ S_{\script 1,4} \/ = \/ 0 \\ S_{\script 2,4} \/ = \/ 2 \/ S_{\script 1,4} \/ = \/ 0 \\ S_{\script 3,4} \/ = \/ 3 \/ S_{\script 2,4} \/ = \/ 0 \\ S_{\script 5,4} \/ = \/ - S_{\script 4,4} \\ \end{array}} \right. \qquad \Rightarrow \qquad \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 0 \\ 0 \\ 1 \\ -1 \\ \end{array}\right )$

e per il quinto

$\left ( \begin{array}{c30c30c30c30c30C20C20C20C20C20} -4&0&0&0&0 \\ 4&-3&0&0&0 \\ 0&3&-2&0&0 \\ 0&0&2&-1&0 \\ 0&0&0&1&0 \\ \end{array}\right) \left ( \begin{array}{c30C20C20C20C20C20} S_{\script 1,5} \\ S_{\script 2,5} \\ S_{\script 3,5} \\ S_{\script 4,5} \\ S_{\script 5,5} \\ \end{array}\right ) \/ = \/ \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array}\right ) \qquad \Rightarrow \qquad \left \{ {\begin{array} {l C30C30C30C30} -4 \/ S_{\script 1,5} \/ = \/ 0 \\ S_{\script 2,5} \/ = \/ \frac 4 3 S_{\script 1,5} \/ = \/ 0 \\ S_{\script 3,5} \/ = \/ \frac 3 2 S_{\script 2,5} \/ = \/ 0 \\ S_{\script 4,5} \/ = \/ 2 \/ S_{\script 3,5} \/ = \/ 0 \\ \end{array}} \right. \qquad \Rightarrow \qquad \left ( \begin{array}{c30C20C20C20C20C20} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ \end{array}\right )$

Mettendo tutto insieme otteniamo

${\mathbf S} \/ = \/ \left ( \begin{array}{c30c30c30c30c30C20C20C20C20C20} 1&0&0&0&0 \\ -4&1&0&0&0 \\ 6&-3&1&0&0 \\ -4&3&-2&1&0 \\ 1&-1&1&-1&1 \\ \end{array}\right)$

Questa matrice è davvero ragguardevole: infatti, è una matrice triangolare composta di coefficienti binomiali a segni alternati. Se facciamo la sua inversa otteniamo (provare per credere)

${\mathbf S}^{\script -1} \/ = \/ \left ( \begin{array}{c30c30c30c30c30C20C20C20C20C20} 1&0&0&0&0 \\ 4&1&0&0&0 \\ 6&3&1&0&0 \\ 4&3&2&1&0 \\ 1&1&1&1&1 \\ \end{array}\right)$

la stessa matrice ma in valore assoluto!
A questo punto possiamo calcolare l'$r$-sima potenza della matrice di transizione

${\mathbf M}^{\script r} \/ = \/ {\mathbf S \/ \Lambda}^{\script r} \/ {\mathbf S}^{\script -1}$

dove

${\mathbf \Lambda} \/ = \/ \left ( \begin{array}{c30c30c30c30c30C20C30C30C30C20} 0&&&& \\ &\frac14&&& \\ &&\frac24&& \\ &&&\frac34& \\ &&&&1 \\ \end{array}\right)$

Tale matrice, moltiplicata per un "vettore di posizione"

${\mathbf y}_{\script 0} \/ = \/ \left ( \begin{array}{c30C20C20C20C20C20} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array}\right )$

fornisce un vettore contenente le probabilità di possedere almeno $0$, $1$, $2$, $3$ o $4$ gormiti diversi avendone acquistati $r$

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

Il quinto elemento di questo vettore contiene la probabilità di ottenere i gormiti di tutti e quattro i tipi in $r$ passi: la distribuzione cumulativa di $r$.

In pratica, non è necessario calcolare tutta ${\mathbf M}^{\script r}$ perchè ciò che ci interessa è il primo elemento dell'ultima riga di tale matrice

$\left ( \begin{array}{c20C20C20C20C20C20} {}\\{}\\{}\\{}\\{\text X}\\ \end{array} \right ) \/ = \/ \left ( \begin{array}{c20c20c20c20c20C20C20C20C20C20} &&&&. \\ &&&& \\ &&&& \\ &&&& \\ {\text X}&&&& \\ \end{array} \right ) \/ \left ( \begin{array}{c20C20C20C20C20C20} {1}\\{0}\\{0}\\{0}\\{0}\\ \end{array} \right ) \/ = \/ \left ( \begin{array}{c20c20c20c20c20C30C20C20C20C20} &&&& \\ &&&& \\ &&&& \\ &&&& \\ 1&-1&1&-1&1 \\ \end{array} \right ) \/ \left ( \begin{array}{c20c20c20c20c20C20C30C30C30C20} 0&&&& \\ &\left ( \frac 1 4 \right )^{\script r}&&& \\ &&\left ( \frac 2 4 \right )^{\script r}&& \\ &&&\left ( \frac 3 4 \right )^{\script r}& \\ &&&&1 \\ \end{array} \right ) \/ \left ( \begin{array}{c20c20c20c20c20C20C20C20C20C20} 1&&&&. \\ -4&&&& \\ 6&&&& \\ -4&&&& \\ 1&&&& \\ \end{array} \right ) \/ \left ( \begin{array}{c20C20C20C20C20C20} {1}\\{0}\\{0}\\{0}\\{0}\\ \end{array} \right )$

Quindi

$F \/ \left ( r \/ | \/ n = 4 \/ I \right ) \/ = \/ 1 \/ \cdot \/ \left ( \frac 0 4 \right )^{\script r} \/ \cdot \/ 1 \/ - \/ 1 \/ \cdot \/ \left ( \frac 1 4 \right )^{\script r} \/ \cdot \/ 4 \/ + \/ 1 \/ \cdot \/ \left ( \frac 2 4 \right )^{\script r} \/ \cdot \/ 6 \/ - \/ 1 \/ \cdot \/ \left ( \frac 3 4 \right )^{\script r} \/ \cdot \/ 4 \/ + \/ 1 \/ \cdot \/ \left ( \frac 4 4 \right )^{\script r} \/ \cdot \/ 1$

cioè

$F \/ \left ( r \/ | \/ n = 4 \/ I \right ) \/ = \/ - \/ \begin{pmatrix} 4 \\ 1 \\ \end{pmatrix} \/ \left ( \frac 1 4 \right )^{\script r} \/ + \/ \begin{pmatrix} 4 \\ 2 \\ \end{pmatrix} \/ \left ( \frac 2 4 \right )^{\script r} - \/ \begin{pmatrix} 4 \\ 3 \\ \end{pmatrix} \/ \left ( \frac 3 4 \right )^{\script r} \/ + \/ \begin{pmatrix} 4 \\ 4 \\ \end{pmatrix} \/ \left ( \frac 4 4 \right )^{\script r}$

e, in generale

$F \left ( r \/ | \/ n \/ I \right ) \/ = \/ \sum \limits_{\script k = 0}^{\script n} {\left ( -1 \right )^{\script n - k} {n \choose k} \left ( \frac k n \right )^{\script r}} \hspace{50} \forall \/ r \/ > \/ 0$

Poiché si tratta di una distribuzione cumulativa discreta, la distribuzione di probabilità vale

$p \left ( r \/ | \/ n \/ I \right ) \/ = \/ \left \{ \begin{array}{l250lC25C20} 0 & r \/ \in \/ \left \{ 0, \/ 1 \right \} \\ F \left ( r \/ | \/ n \/ I \right ) \/ - \/ F \left ( r - 1\/ | \/ n \/ I \right ) & r \/ > \/ 1 \\ \end{array} \right.$

cioè

$p \left ( r \/ | \/ n \/ I \right ) \/ = \/ \left \{ \begin{array}{l250lC20C40} 0 & r \/ \in \/ \left \{ 0, \/ 1 \right \} \\ \sum \limits_{\script k = 0}^{\script n} {\left ( -1 \right )^{\script n - k} {n \choose k} \left \{ \left ( \frac k n \right )^{\script r} \/ - \/ \left ( \frac k n \right )^{\script r - 1} \right \}} & r \/ > \/ 1 \\ \end{array} \right.$

ovvero

$p \left ( r \/ | \/ n \/ I \right ) \/ = \/ \left \{ \begin{array}{l250lC20C40} 0 & r \/ \in \/ \left \{ 0, \/ 1 \right \} \\ \sum \limits_{\script k = 0}^{\script n} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac {n - k} n \left ( \frac k n \right )^{\script r - 1} } & r \/ > \/ 1 \\ \end{array} \right.$

dove l’indice $k$ corre da $0$ a $n$.

Dato che

$k \/ = \/ n \/ \neq \/ 0 \qquad \Rightarrow \qquad \frac {n - k} n \/ = \/ 0$

allora

$\sum \limits_{\script k = 0}^{\script n} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac {n - k} n \left ( \frac k n \right )^{\script r - 1} } \/ = \/ \sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac {n - k} n \left ( \frac k n \right )^{\script r - 1} }$

e quindi

$p \left ( r \/ | \/ n \/ I \right ) \/ = \/ \left \{ \begin{array}{l250lC20C40} 0 & r \/ \in \/ \left \{ 0, \/ 1 \right \} \\ \sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac {n - k} n \left ( \frac k n \right )^{\script r - 1} } & r \/ > \/ 1 \\ \end{array} \right.$

dove l’indice $k$ corre da $0$ a $n \/ - \/ 1$.

Il valore atteso di $r$ vale

$\left \langle r \/ | \/ n \/ I \right \rangle \/ = \/ \sum \limits_{\script r = 0}^{\script \infty} {r \/ p \left (r \/ | \/ n \/ I \right )}$

cioè

$\left \langle r \/ | \/ n \/ I \right \rangle \/ = \/ \sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac {n - k} n \sum \limits_{\script r = 2}^{\script \infty} {r \/ \left ( \frac k n \right )^{\script r - 1}}}$

Abbiamo

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

per cui

$\left \langle r \/ | \/ n \/ I \right \rangle \/ = \/ \sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac {n - k} n \left ( \frac n {n - k} \right )^{\script 2}} \/ - \/ \sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac {n - k} n }$

cioè

$\left \langle r \/ | \/ n \/ I \right \rangle \/ = \/ \sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac n {n - k}} \/ - \/ \sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n - 1 \choose k} }$

Ponendo $m \/ = \/ n \/ - \/ 1$ si dimostra, con il teorema binomiale, che il secondo termine è

$\sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n - 1 \choose k} \frac {n - k} n } \/ = \/ \sum \limits_{\script k = 0}^{\script m} {\left ( -1 \right )^{\script m - k} {m \choose k}} \/ = \/ 0$

quindi

$\left \langle r \/ | \/ n \/ I \right \rangle \/ = \/ \sum \limits_{\script k = 0}^{\script n - 1} {\left ( -1 \right )^{\script n - k + 1} {n \choose k} \frac n {n - k}} \/ = \/ n \/ \sum \limits_{\script k = 1}^{\script n} {\frac {\left ( -1 \right )^{\script k + 1}} k {n \choose k}}$

(nel caso di quattro gormiti, $\left \langle r \/ | \/ n = 4 \/ I \right \rangle \/ = \/ 4 \/ \left (\frac 1 1 \/ 4 \/ - \/ \frac 1 2 \/ 6 \/ + \/ \frac 1 3 \/ 4 \/ - \/ \frac 1 4 \/ 1 \right ) = \frac {25} 3$)

Alla fine, confrontando le due soluzioni, ci troviamo con questo bel teorema di calcolo combinatorio da dimostrare

$\sum \limits_{\script k = 1}^{\script n} {\frac {\left ( -1 \right )^{\script k + 1}} k {n \choose k}} = \sum \limits_{\script k = 1}^{\script n} {\frac 1 k}$

Meditate...

[mathmum]

In questo caso ho la CERTEZZA MATEMATICA che vale la pena di sborsare 1Euro e 90 e comprare "al buio" il gormita... sarà poco "tecnico" ma sicuramente meno faticoso...

ciao Pan!

[panurgo]

c'è la possibilità di palpare la confezione e tentare di indovinare l'identità del gormita...

[albumasar]

l'unica cosa che si può dire sui gormiti è...GORMITICO...NON TEME CONFRONTI