La funzione del collezionista (1/2)

«Ho comprato un album di figurine: quante ne dovrò acquistare in media per completarlo?»

Può essere formulato così il cosiddetto problema del collezionista. Si suppone che le figurine in vendita abbiano tutte la stessa probabilità di comparire. Se l’album ha $N$ figurine, la probabilità che la prima figurina comprata vada ad occupare un posto libero è naturalmente $p_1=1$; affinché la seguente figurina vada ad allargare la collezione, essa deve essere fra le $N-1$ rimanenti, e quindi la probabilità di allargare la collezione è $p_2=\frac{N-1}N$; una volta che l’album contiene due figurine, la probabilità seguente sarà $p_3=\frac{N-2}N$, ed in generale si avrà $p_n=\frac{N-n+1}N$.

Un evento con probabilità $p$ si realizza in un numero variabile di volte $n$ di cui si può calcolare media (detta anche valore atteso) e varianza, vediamo come: la probabilità che si realizzi la prima volta è, ovviamente, $P(1)=p$, la probabilità che si realizzi la seconda volta è $P(2)=[1-P(1)]p=p(1-p)$, la probabilità che si realizzi la terza volta è $P(3)=[1-P(1)-P(2)]p=p(1-p)^2$ e, in generale, la probabilità che si realizzi la ennesima volta è $P(n)=p(1-p)^{n-1}$. Si ha, come dev’essere, $\displaystyle{\sum_{k=1}^\infty P(k)=1}$, inoltre il valore atteso è $\langle n \rangle =\displaystyle{\sum_{k=1}^\infty k P(k) = \dfrac1p}$, mentre la varianza è $$\operatorname{Var}(n)=\langle n^2 \rangle-\langle n \rangle^2=\sum_{k=1}^\infty k^2 P(k) - \langle n \rangle^2=\left( \frac2{p^2}- \frac1p \right) - \left(\frac1p \right)^2=\frac1{p^2}-\frac1p\ .$$Supponendo di avere già posto $n-1$ figurine nell’album, chiamo $f_n$ il numero di figurine da acquistare per trovarne una nuova e, per quanto osservato prima si avrà $$\langle f_n \rangle = \dfrac1{p_n} = \dfrac N{N-n+1}\ \mathrm{e}\ \operatorname{Var}(f_n)=\left( \dfrac N{N-n+1} \right)^2 - \dfrac N{N-n+1}\ .$$Detto $F$ il numero di figurine da acquistare per completare l’album si ha: $$  \langle F \rangle =\left \langle \sum_{n=1}^N f_n \right \rangle =  \sum_{n=1}^N \langle f_n \rangle=\sum_{n=1}^N \frac N{N-n+1}=\sum_{k=1}^N \frac Nk =N (\ln N + \gamma ) + \frac12 + O \left( \frac1N \right)$$e poiché le probabilità di acquisire le diverse figurine sono indipendenti si ha anche: $$\operatorname{Var}(F) = \sum_{n=1}^N \operatorname{Var}(f_n) = \sum_{n=1}^N \left[ \left( \dfrac N{N-n+1} \right)^2 - \dfrac N{N-n+1} \right] = \\ = \sum_{k=1}^N \left[ \left( \dfrac N{k} \right)^2 - \dfrac Nk \right] = \frac{\pi^2}6 N^2 - N (\ln N + \gamma + 1  ) + O \left( \frac1N \right) \ ,$$da cui si ricava che lo scarto quadratico medio è $$\sigma_F = \sqrt{\operatorname{Var}(F)} = \frac\pi{\sqrt 6} N - \frac{\sqrt{3/2}} \pi  (\ln N  + \gamma + 1  ) + O \left( \frac{\ln^2\! N}N \right) \ .$$Il numero medio di figurine da acquistare per completare l’album è quindi più che proporzionale al numero di figurine dell’album, come si vede anche dalla figura $5$.

Supponiamo ora però di volere avere altre informazioni come ad esempio: quante figurine devo comprare per avere il $50\%$ di probabilità di completare l’album? In questo caso la conoscenza della media e dello scarto quadratico medio non è sufficiente per poter ottenere questo dato, e ci occorre una funzione che ci dica, in funzione di $n$, quale sia la probabilità $p_N(n)$ di completare l’album all’acquisto della ennesima figurina. Tale funzione può essere ottenuta esattamente utilizzando la matrice di Markov associata al problema, seguendo, ad esempio, quanto scritto qui. Se l’album ha $N$ figurine la matrice di Markov può essere scritta in questo modo: $$\mathbf M=\left( \begin{array}{ccccccc} 0 & 1 & 0 & 0  & 0 & \cdots & 0 \\ 0 & \frac1N & \frac{N-1}{N} & 0 & 0  & \cdots  & 0\\ 0 & 0 & \frac2N & \frac{N-2}{N} & 0 & \cdots  & 0\\ \vdots & \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & \frac{N-2}N & \frac2N & 0 \\ 0 & 0 & \cdots & 0 & 0 & \frac{N-1}N & \frac1{N} \\ 0 & 0 & \cdots & 0 & 0 & 0 & 1  \end{array} \right )\ .$$Questo approccio fornisce i numeri esatti ma ha diversi svantaggi tra i quali: primo, la necessità di utilizzare un computer con un software in grado di fare moltiplicazioni fra matrici; secondo, i tempi di calcolo che crescono circa come $N^4\ln N$. Purtroppissimo la funzione non è approssimabile con una gaussiana, come si vede ictu oculi in figura $1$ e in figura $2$, essendo, e questo vale maggiormente per valori piccoli di $N$, molto asimmetrica e “sbilanciata sulla destra”, infatti l’indice di asimmetria è sempre positivo e, benché decresca all’aumentare di $N$, non tende a $0$ ma a $-\dfrac{6\sqrt6}{\pi^3}\psi_2(1)\simeq 1{,}1395$ (limite calcolato con la funzione di Laplace, vedi oltre) dove $\psi_2$ indica la funzione poligamma di second’ordine. Dunque, anche per $N$ che tende ad infinito, la funzione di probabilità non è assimilabile ad una gaussiana (che è simmetrica ed ha pertanto indice di asimmetria pari a $0$).

Mi sono perciò posto il problema di trovare una funzione approssimante relativamente semplice. Ho calcolato i valori di $p_{200}(n)$ e fatto il grafico del logaritmo (vedi figura $4$). Il grafico ha una prima parte crescente, ed una seconda decrescente in modo pressoché lineare. Facendo qualche esperimento ho visto che la funzione $\ln p_{200}(x)$ è ben approssimata da una funzione del tipo $g(x)=-C e^{-\beta x}-\beta x$ che scrivo come $g(x)=-e^{-\frac{x-x_0}a}-\frac xa$ dove $x_0$ corrisponde circa al valore $x$ per cui si ha la massima probabilità e $a$ è circa $199{,}5$. Esaminando i valori delle probabilità in corrispondenza di diversi $N$ ho riscontrato che la “coda” della funzione $p_N(x)$ in generale va come $K e^{-\frac x{N-1/2}}$ con $K$ poco più grande di $1$. Cerco pertanto una funzione approssimante del tipo $f_N(x)=A\,e^{-e^{-\frac{x-x_0}{a}}-\frac xa} $ dove $A=\left[a\,e^{-\frac{x0}a}\left(1-e^{-e^{\frac{x_0}a}}\right)\right]^{-1}$ è il fattore di normalizzazione. La funzione è dunque $$f_N(x)=\dfrac{e^{-e^{-\frac{x-x_0}a}-\frac{x-x_0}a}}{a\left(1-e^{-e^\frac{x0}a} \right )}\ .$$Come scegliere i “migliori” parametri $x_0$ e $a$? Sono possibili diverse scelte, ed avendo due parametri posso imporre al più due condizioni. Quelle che ho scelto io sono che la funzione $f_N$ abbia lo stesso valore atteso e la stessa varianza di $p_N$. Dopo un po’ di integrali e sviluppi asintotici, che ’l tacere è bello, ho ottenuto questi risultati:$$x_0=N\ln N+\frac{3\gamma}{\pi^2} ( \ln N+  \gamma + 1  ) +\frac12 + O \left( \frac{\ln^2\! N}N \right)\ , \\ a = N - \frac3{\pi^2} \left( \ln N + \gamma + 1 \right) + O \left( \frac{\ln^2\! N}N \right)\ .$$«Chi cerca trova, e chi ricerca… ritrova quello che altri hanno già trovato!» ci disse una volta il prof. di Meccanica Quantistica, ed in effetti questa mia ricerca non fa eccezione. Dopo un marasma di tentativi e calcoli trovo su wikipedia inglese due righe che mi informano che monsieur Laplace (1749-1827), ed in seguito Erdős (1913-1996), e Rényi (1921-1970) hanno dimostrato quanto segue: $$\lim_{N\to\infty}\left[\sum_{n=1}^{N\ln N+yN}p_N(n)\right]=e^{-e^{-y}}$$ che porta ad una funzione limite cumulativa $L^{ ^C}_N(x)=e^{-e^{-\frac{x-N\ln N}N}}$, da cui si ricava che la funzione limite è $$L_N(x)=\frac{d L^{ ^C}_N/dx}{1-e^{-N}}=\dfrac{e^{-e^{-\frac{x-N\ln N}N}-\frac{x-N\ln N}N}}{N \left(1-e^{-N} \right )}\ ,$$dove il denominatore $1-e^{-N}$ serve a normalizzare la funzione.

In sostanza la funzione che ho trovato pasticciando empiricamente va a coincidere con quella di Laplace ponendo $x_0=N\ln N$ e $a=N$. Benché la funzione da me trovata approssimi numericamente un po’ meglio la funzione di probabilità esatta (vedi figure $7$-$13$), la funzione di Laplace ha il pregio di essere molto più semplice, è agevole da calcolare e permette di rispondere facilmente alla domanda: quante figurine devo acquistare per avere una certa probabilità $p$ di completare l’album? Basta porre $e^{-e^{-y}}=p,$ da cui $y=-\ln \ln (1/p)$ e la risposta è $x=N\ln N+yN$. Ad esempio se $p=50\%$, il valore $x$ trovato, ovvero la mediana della distribuzione, approssima molto bene il valore esatto anche per valori piccoli di $N$ (vedi la tabella di figura $6$), mentre si trova che il numero medio di figurine da acquistare per completare l’album corrisponde ad una probabilità $p=e^{-e^{-\gamma}}\simeq 57\%$ di completare l’album.

Bene, visto che per completare un album occorrono così tante figurine, conviene avere degli amici che condividano la stessa passione con cui fare degli scambi, no? E in questo caso come va la faccenda?

Stay tuned…

つづく

Il primo a prendere in considerazione il problema del collezionista fu Abraham de Moivre (1667-1754): in De Mensura Sortis (1711) e poi in Doctrine of Chances (1718) ricavò la probabilità che vengano acquisiti tutti gli elementi dell’insieme dopo $k$ estrazioni. Pierre-Simon de Laplace in un articolo del 1774 e poi in Théorie Analytique des Probabilités (1812) generalizzò il problema al caso in cui gli elementi siano acquisiti a gruppi di $m$ con $m\geq1$. Eulero (1707-1783) ricavò un’espressione per la probabilità che vengano acquisiti almeno $j$ elementi dopo $k$ estrazioni. Nel tempo sono state studiate ulteriori generalizzazioni del problema.

Figura 1. Funzione di probabilità per $N=200$.

Figura 2. Confronto tra funzioni di probabilità scalate in modo che abbiano tutte il massimo in $(1,1)$.

Figura 3. Un indice della asimmetria della funzione $p_N(x)$ è dato dal rapporto fra i segmenti $PM_2$ e $PM_1$: tale rapporto, per $N$ che tende ad infinito, tende a $\frac{1+ \ln 2 + W\left(-\frac1{2e}\right)}{1+\ln 2+ W_{-1}\left(-\frac1{2e}\right)}$. $Ln_{200}(x)$ è la funzione di Laplace per $N=200$ scalata in modo da avere il massimo in $(1,1)$.

Figura 4. Logaritmo naturale della funzione $p_{200}(x)$.

Figura 5. Grafico del numero medio di figurine da acquistare e del numero di figurine da acquistare per avere una determinata probabilità di completare l’album.

Figura 6. Tabella con alcune caratteristiche delle funzioni di probabilità per alcuni valori di $N$.

Figura 7. Funzioni di probabilità per $N=6$: $p(n)$ è la funzione calcolata con la matrice di Markov, $f(n)$ è l’approssimazione da me trovata, $L(n)$ è l’approssimazione di Laplace. 

Figura 8. Funzioni di probabilità per $N=12$.

Figura 9. Funzioni di probabilità per $N=25$.

Figura 10. Funzioni di probabilità per $N=50$.

Figura 11. Funzioni di probabilità per $N=100$.

Figura 12. Funzioni di probabilità per $N=200$.

Figura 13. Differenze tra le funzioni $f(n)$ e $L(n)$ e la funzione $p(n)$ per $N=200$.