da Cmax » 22/05/2007, 13:59
Dal punto di vista didattico è un tipico problema schematizzabile come percorso casuale (random walk). È un procedimento un po' lungo, e ripete in sostanza quanto già detto, ma lo trovo interessante, e soprattutto ho il TeX già pronto per un problema quasi identico, così lo riciclo con poche modifiche e lo propongo.
Rappresentando lo stato in cui ci sono sono stati estratti $i$ cerini da una scatola e $j$ dall'altra come un punto nel reticolo di coordinate intere, lo stato iniziale (certo) è $(0,0)$, e a ciascun punto $(i,j)$ si può arrivare omogeneamente da $(i-1,j)$ o da $(i,j-1)$.
Si può quindi scrivere
(1) $P_{0,0}=1$
(2) $P_{i,j}=\frac{1}{2}P_{i-1,j}+\frac{1}{2}P_{i,j-1}$
(3) $P_{n,j}=\frac{1}{2}P_{n-1,j}$
(4) $P_{i,n}=\frac{1}{2}P_{i,n-1}$
Le ultime due equazioni sono necessarie per assicurarsi che il calcolo si arresti quando una delle due scatole è vuota, ed evitare transizioni del tipo $(n,j-1) -> (n,j)$ o $(i-1,n) -> (i,n)$.
Conto i cerini estratti e non quelli rimasti poichè nella letteratura lo stato iniziale di un random walk è in genere nell'origine, e quindi il TeX era predisposto in questo modo. È noto, ma si verifica facilmente, che la relazione ricorsiva (2) è riferibile all'i-esimo (o il j-esimo, vista la simmetria del problema) termine del binomio $(\frac{1}{2}+\frac{1}{2})^{i+j}$, e quindi $P_{i,j}= \frac{1}{2^{i+j}} ((i+j),(i))$.
Da un punto di vista combinatorio si può spiegare in questi termini: sul reticolo sono possibili tutti i percorsi effettuati con "un passo in su" (estrazione da una scatola) o "un passo a destra" (estrazione dall'altra), che sono rappresentabili da una stringa del tipo $SDDSSD..DSS$ (la sequenza dei passi). Una specifica estrazione di $i$ elementi nel primo campione e di $j$ nel secondo diventa quindi una stringa di $i+j$ simboli $S$ o $D$. Ovviamente, sono possibili $2^{i+j}$ stringhe di questo genere. Di queste, quelle che portano al punto del reticolo $(i,j)$ sono composte da $i$ simboli $D$ e $j$ simboli $S$. Considerando le permutazioni, ce ne sono $((i+j),(i))$ distinte.
In particolare, la distribuzione cercata è quindi (ricordare la simmetria) $P_{i,n}= \frac{1}{2}P_{i,n-1}=\frac{1}{2} \frac{1}{2^{n-1+i}} ((n-1+i),(n-1)) = \frac{1}{2^{n+i}} ((n-1+i),(n-1))$.
Esprimendo la probabilità in termini di cerini rimasti, cioè $k=n-i$, e quindi $i=n-k$, si ha $P_{k,0}=\frac{1}{2^{2n-k}} ((2n-k-1),(n-1))$.