block note∳: La funzione del collezionista (2/2)

Abbiamo visto alcuni risvolti matematici della raccolta delle figurine. Che cosa cambia se si possono scambiare le figurine con altri collezionisti? Ovviamente ne dovremo, in media, comprare di meno per completare l’album. Vediamo in dettaglio.

Nel caso di un collezionista solitario, il numero medio di figurine da acquistare per completare un album di $N$ figurine è, come già visto: $$\langle F \rangle =\sum_{k=1}^N \frac Nk =N (\ln N + \gamma ) + \frac12 + O \left( \frac1N \right)\ .$$Nel caso di $c$ collezionisti, il numero medio di figurine richiesto per completare $c$ album di $N$ figurine non è esprimibile altrettanto facilmente, ma ne esiste comunque un’espressione esatta ed è:$$\langle F_c \rangle = N {\LARGE\int}_0^{+\infty}\!\left[1-\left( 1-e^{-t}\sum_{k=0}^{c-1}\frac{t^k}{k!}\right )^{\!N\ } \right ]dt\ .$$Fissato $N$, per $c$ che tende ad infinito $\langle F_c \rangle=N\cdot O(c)$, ovvero il numero medio di figurine da acquistare per ogni collezionista tende a $N$.

Esiste un’espressione approssimata facilmente calcolabile anche per $\langle F_c \rangle$? Due notizie: una buona ed una cattiva. Prima la buona. L’espressione esiste ed è:$$\langle F_c \rangle = N[\ln N+\gamma+(c-1)\ln\ln N-\ln(c-1)!\,] +o(N)\ .\tag{1}$$Quella cattiva forse qualcuno l’ha già notata: l’approssimazione è $o(N)$, ovvero una quantità che divisa per $N$ tende a $0$, ma di per sé non è detto che tenda a $0$, ed infatti, nel nostro caso, non tende affatto a $0$. Esaminando i numeri, “sperimentalmente” pare che quell’$o(N)$ per $c>1$ sia più precisamente un $O\left(\frac N{\ln N}\right)$, quindi non solo non tende a $0$, ma, quando è rapportato ad $N$, tende a $0$ molto lentamente (vedi figure $1$ e $2$). È peraltro una quantità negativa, ovvero l’approssimazione è sempre per difetto, ed aumenta in modulo all’aumentare di $c$.

In ogni caso: quanto fa risparmiare fare la raccolta delle figurine insieme ad altri (ognuno col suo album, ovviamente)? Potete vederlo nella figura $3$. Quante più sono le figurine dell’album, tanto più la collaborazione e lo scambio delle figurine abbassano percentualmente, oltre che in valore assoluto, il numero medio da acquistarne a testa per completare gli album. Ad esempio, se l’album ha $100$ figurine, avere altri tre amici con cui fare gli scambi ottiene quasi un dimezzamento del numero medio di figurine da acquistare.

Per ottenere altre informazioni, come ad esempio il numero di figurine da acquistare a testa per avere una certa probabilità di avere completato l’album, è necessario conoscere la distribuzione delle probabilità. L’approccio delle matrici di Markov, nel caso $c>1$, non è la scelta più agevole, sia per la complessità richiesta dal “progettare” la matrice, sia perché essa avrà una dimensione $D=\binom{N+c}c$, $D\simeq N^c/c!$ per $c\ll N$, e i tempi di calcolo vanno circa come $D^4\ln D$.

Ad esempio, qui a lato trovate la matrice di Markov $28\times28$ per il caso $N=6$, $c=2$. Per il caso $N=100$, $c=2$ la matrice sarebbe $5151\times5151$.

Ho pertanto utilizzato il metodo Monte Carlo, riempiendo miliardi di album virtuali di figurine estraendo decine di migliaia di miliardi di figurine virtuali (nessuna figurina virtuale è stata maltrattata nel procedimento). I risultati li vedete nelle figure $4$-$7$ dove ho messo in ascissa non il numero totale di figurine, ma il numero di figurine acquistate da ogni singolo collezionista. La forma della funzione di distribuzione è simile a quella vista per $c=1$. All’aumentare di $c$ diminuisce un po’ la asimmetria della distribuzione. Si può trovare una funzione approssimante per queste distribuzioni? Il “giochetto” di cercare una funzione approssimante parametrica imponendo dei vincoli stavolta non si può fare, sia perché il valore medio non è esprimibile in modo semplice e preciso, sia perché non conosco a priori altre caratteristiche della distribuzione come lo scarto quadratico medio o la mediana.

Abbiamo visto che, nel caso di un singolo collezionista, una distribuzione di probabilità è ricavabile da questo limite dimostrato da Laplace:$$\lim_{N\to\infty}\left[\sum_{n=1}^{N\ln N+yN}p_N(n)\right]=e^{-e^{-y}}\ ,$$ebbene: nel 1961 Erdős (1913-1996), e Rényi (1921-1970) hanno generalizzato il limite al caso di $c$ collezionisti e si ha: $$\lim_{N\to\infty}\left[\sum_{n=1}^{N\ln N+(c-1)N\ln\ln N +yN}p_{N,c}(n)\right]=e^{-e^{-y}/(c-1)!}$$che porta ad una funzione limite cumulativa $$E^{ ^C}_{N,c}(x)=e^{-\left[e^{-\frac{x-N\ln N-(c-1)N\ln\ln N}{N}}\right]/(c-1)!}$$e, derivando e normalizzando, si ottiene una funzione di probabilità $E_{N,c}(x)=p_{_{ER}}(x)$ di cui vi risparmio l’espressione esplicita, alquanto ingombrante.

Vediamo nella figura $8$ che cosa succede per $N=100$ e $c$ che va da $1$ a $6$: per $c=1$ ritroviamo il caso già visto di ottima approssimazione, ma… che succede? all’aumentare di $c$ la forma della funzione $p_{_{ER}}$ rimane praticamente la stessa mentre la funzione $p$ tende a “stendersi”, ed il divario tra funzione approssimante ed effettiva funzione di probabilità aumenta sempre di più, anzi per $c=6$ la funzione approssimante addirittura “torna indietro”. In realtà tutto questo non deve stupire, in quanto il valore atteso della funzione approssimante è proprio quello espresso nella $(1)$, con gli stessi problemi di lentissima convergenza e con il termine negativo $-\ln(c-1)!$ che, se fissiamo $N$ e facciamo aumentare $c$, prima o poi prevale su quello positivo $(c-1)\ln\ln N$.

Insomma, fare la raccolta delle figurine insieme ad altri amici è economicamente molto vantaggioso, ma matematicamente un po’ più complicato.

おわり

Figura 1. Rapporto fra modulo dell’errore $\Delta$ commesso utilizzando la formula in $(1)$ e $N$.

Figura 2. Rapporto fra modulo dell’errore $\Delta$ commesso utilizzando la formula in $(1)$ e $N$.

Figura 3. Rapporto fra numero medio di figurine da acquistare a testa fra $c$ collezionisti per completare $c$ album di $N$ figurine e numero medio richiesto al “collezionista solitario”.