mercoledì 21 luglio 2021

Il gioco dei pacchi ūüéĀ

In una nuova trasmissione televisiva viene fatto questo gioco: vi sono 20 concorrenti, ognuno con un pacco contenente un assegno con una cifra in euro. Viene estratto un concorrente: questi far√† aprire un pacco a sua scelta e poi dovr√† prendere una decisione: scegliere il pacco appena aperto oppure andare avanti e farne aprire un altro, e cos√¨ via. Un pacco scartato non potr√† pi√Ļ essere scelto. Se nessuno dei pacchi degli altri concorrenti verr√† scelto, il concorrente sceglier√† forzatamente il proprio pacco (dal valore inizialmente sconosciuto come tutti gli altri). Il concorrente si porter√† a casa l’ammontare corrispondente al pacco scelto. Qual √® la strategia che massimizza la probabilit√† di scegliere il pacco dal maggior valore? √ą da sottolineare che non si ha alcuna informazione sui valori degli assegni, l’unica cosa che si pu√≤ fare √® confrontare i contenuti dei pacchi fra loro.
La situazione √® equivalente ad avere 20 pacchi disposti uno dopo l’altro ed aprirli sequenzialmente fino al pacco scelto.
Se scegliamo un pacco che non è il maggiore fra quelli comparsi fino a quel momento, sicuramente non scegliamo il pacco dal valore maggiore. La strategia migliore è aprire un certo numero $k$ di pacchi e poi scegliere il primo con valore superiore al massimo dei valori dei primi $k$ pacchi aperti. Ad ogni $k$ corrisponde una determinata probabilità di successo, e dobbiamo trovare il valore di $k$ che massimizza tale probabilità.
Prima di risolvere il caso generale e scrivere delle belle formulone, facciamo un esempio concreto, per meglio chiarire le idee (sono abituato a fare cos√¨, sia con me stesso che con i miei studenti, e ho riscontrato che √® una modalit√† molto efficace). Supponiamo di prendere $k=5$, cio√® facciamo aprire $5$ pacchi e poi apriremo i pacchi fino a quando non troveremo un valore superiore a quello dei primi $5$ pacchi o, eventualmente, apriremo e sceglieremo forzatamente l’ultimo pacco. Indico con $\texttt{#}1$ il pacco di maggior valore. La probabilit√† che il pacco $\texttt{#}1$ sia in una determinata posizione √® $\dfrac1{20}$.
Se il pacco $\texttt{#}1$ √® tra i primi $k=5$ aperti non sar√† scelto. Se il pacco $\texttt{#}1$ √® il sesto, sar√† sicuramente scelto, quindi la probabilit√† che il pacco $\texttt{#}1$ sia sesto e venga scelto √® $\dfrac1{20}$. Se il pacco $\texttt{#}1$ √® il settimo, la probabilit√† che sia scelto va moltiplicata per $1-\dfrac16$, dove $\dfrac16$ √® la probabilit√† che, fra i sei pacchi precedenti, quello di valore maggiore sia in sesta posizione (nel qual caso sarebbe stato scelto). La probabilit√† che il pacco $\texttt{#}1$ sia settimo e venga scelto √® dunque $\dfrac1{20}\cdot\dfrac56$. Analogamente, se il pacco $\texttt{#}1$ √® l’ottavo, la probabilit√† che venga scelto va moltiplicata per $\left(1-\dfrac16\right)\left(1-\dfrac17\right)=\dfrac57$, ovvero la probabilit√† che il maggiore fra i primi sei pacchi non sia in sesta posizione e che il maggiore fra i primi sette pacchi non sia in settima posizione. La probabilit√† che il pacco $\texttt{#}1$ sia ottavo e venga scelto √® dunque $\dfrac1{20}\cdot\dfrac57$. Andando avanti, le probabilit√† sono $\dfrac1{20}\cdot\dfrac58,\dfrac1{20} \cdot\dfrac59, \ldots,\dfrac1{20} \cdot\dfrac5{19}$. La probabilit√† complessiva di scegliere il pacco $\texttt{#}1$ dopo aver scartato $5$ pacchi e scelto il primo dal valore maggiore di quelli dei primi $k=5$ √® dunque, raccogliendo: $p=\dfrac5{20}\left(\dfrac15+\dfrac16+\ldots+\dfrac1{19}\right)$.
Generalizzando, se ho $n$ pacchi e attuo la strategia di aprirne $k$ e poi scegliere il primo che presenti un valore superiore a quelli gi√† visti, la probabilit√† di scegliere il pacco $\texttt{#}1$ e quindi vincere la maggiore posta in gioco sar√†: $$p(n,k)= \dfrac1n+ \dfrac{k}n \left(\dfrac1{k+1} +\dfrac1{k+2} +\ldots+ \dfrac1{n-1} \right)\ .\tag{1}$$
Fissato $n$, la probabilit√† $p(n,k)$ parte da $p(n,0)=\dfrac1n$ e, a parte i casi $n=1$ (dove si ha $p(1,0)=1$) e $n=2$ (dove si ha $p(2,0)=p(2,1)=\frac12$), cresce per raggiungere un valore massimo e poi decrescere fino a $p(n,n-1)=\dfrac1n$, come si vede in figura $1$. Il valore di $k$ che massimizza la probabilit√†, valore che indicheremo con $k_M$, sar√† il pi√Ļ piccolo fra quelli per cui $p(n,k)>p(n,k+1)$. Il $k$ che cerchiamo deve essere il minimo fra quelli che soddisfano la disuguaglianza
$$\dfrac1n+\dfrac{k}n\left(\dfrac1{k+1}+\ldots+\dfrac1{n-1} \right)>\dfrac1n+\dfrac{k+1}n\left(\dfrac1{k+2}+\ldots+\dfrac1{n-1} \right)$$che possiamo riscrivere come$$k\left(\dfrac1{k+1}+\ldots+\dfrac1{n-1} \right)>(k+1)\left(\dfrac1{k+1}+\dfrac1{k+2}+\ldots+\dfrac1{n-1}-\dfrac1{k+1} \right)$$che diventa $$\dfrac1{k+1}+\dfrac1{k+2}+\ldots+\dfrac1{n-1}<1\ ,$$e poich√© cerchiamo il minimo valore di $k$ che soddisfi questa disuguaglianza, il valore cercato √® quello per cui$$\dfrac1{k+1}+\ldots+\dfrac1{n-1}<1<\dfrac1{k}+\ldots+\dfrac1{n-1}\ .\tag{2}$$√ą da notare che, nelle disuguaglianze sopra riportate, non varr√† mai l’uguaglianza (a parte il caso banale in cui la sommatoria sia solo del termine $\frac11$) in quanto, come √® stato dimostrato da J√≥zsef K√ľrsch√°k (1864-1933) nel 1918, la sommatoria di reciproci di numeri interi consecutivi non d√† mai come risultato un numero intero.
Il valore $k_M$ gode anche di questa propriet√† che si pu√≤ verificare facilmente utilizzando l’uguaglianza $(1)$ e le disuguaglianze in $(2)$: √® il massimo valore assunto da $k$ per cui la probabilit√† che il pacco $\texttt{#}1$ sia gi√† stato visto √® inferiore a quella che il pacco $\texttt{#}1$ sia in uno dei pacchi successivi e venga scelto.
Per trovare il valore preciso di $k_M$ dovremmo calcolare le sommatorie e vedere in corrispondenza di quale $k$ superano $1$. In realt√†, anche senza calcolare le sommatorie possiamo comunque porre un limite superiore ed inferiore a $k$ tramite le seguenti disuguaglianze che legano le somme dei reciproci di numeri naturali positivi consecutivi all’integrale della funzione $f(x)=\dfrac1x$:$$\int_a^{b+1}\dfrac{dx}x+\dfrac12\left(\dfrac1a-\dfrac1{b+1}\right)<\dfrac1a+\dfrac1{a+1}+\ldots+\dfrac1b<\int_{a-\frac12}^{b+\frac12}\dfrac{dx}x\ .$$Otteniamo allora$$\int_{k+1}^n \dfrac{dx}x+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)<1<\int_{k-\frac12}^{n-\frac12}\dfrac{dx}x$$da cui$$\ln\left(\dfrac{n}{k+1}\right)+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)<1<\ln\left(\dfrac{n-1/2}{k-1/2}\right)\ .\tag{3}$$Dalla seconda disuguaglianza si ricava facilmente $k<\dfrac{n-1/2}{e}+\dfrac12$ mentre l’elaborazione della prima disuguaglianza √® un po’ pi√Ļ complessa:$$\ln\left(\dfrac{n}{k+1}\right)+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)<1 \iff \ln\left(\dfrac{k+1}{n}\right)>-1+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)\iff$$ $$\iff \dfrac{k+1}n>\dfrac1e\cdot \exp\left[\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)\right]>\dfrac1e\left[1+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)\right]>$$ $$>\dfrac1e\left[1+\dfrac12\left(\dfrac1{\frac{n-1/2}e+\frac32}-\dfrac1n\right)\right]=\dfrac1e\left(1-\dfrac1{2n}\right)+\dfrac1{2n+3e-1}\ ,$$dove abbiamo utilizzato la disuguaglianza $\exp x>1+x$ se $x\neq0$ e la disuguaglianza precedentemente ottenuta per $k$. Si ha dunque$$k>\dfrac{n-1/2}e+\dfrac{n}{2n+3e-1}-1=\dfrac{n-1/2}e+\dfrac{\left(n+\frac{3e}2-\frac12\right)-\left(\frac{3e}2-\frac12\right)}{2n+3e-1}-1$$e infine$$k> \dfrac{n-1/2}e-\dfrac12- \dfrac{3e-1}{2(2n+3e-1)}\ ,\tag{4}$$e si deve quindi complessivamente avere$$\dfrac{n-1/2}e-\dfrac12-\dfrac{3e-1}{2(2n+3e-1)}=k_{inf}(n)<k_M<k_{sup}(n)=\dfrac{n-1/2}{e}+\dfrac12\ .\tag{5}$$L’intervallo in cui deve stare $k_M$ √® di ampiezza $$I(n)=k_{sup}(n) - k_{inf}(n)  =1+\dfrac{3e-1}{4n}+O\left(  \dfrac1{n^2}\right)\simeq 1+\dfrac{1{,}79}{n}-\dfrac{6{,}40}{n^2},$$di poco superiore a $1$ per valori grandi di $n$ e quindi, nella maggior parte dei casi, c’√® un solo intero che stia dentro a quell’intervallo. Per $n$ che va da $1$ a $10.000$ nell’intervallo $(k_{inf},k_{sup})$ vi sono due interi solo per $n=2$ (dove per√≤ entrambi gli interi, $k=0$ e $k=1$ massimizzano la probabilit√† di vincita), e per $n=5$, $13$, $21$, $40$, $59$, $78$, $97$, $184$, $290$, $483$, $676$, $1.554$, $2.818$ e $5.539$. A parte il caso $n=97$, $k_M$ √® sempre il maggiore dei due interi. Indagando da $n=1$ a $n=100.000.000$, si ha in effetti $k_M=\left\lfloor k_{sup}(n)\right\rfloor$ tranne che per $n=2$, $n=97$, $n=24.586$ e $n=14.122.865$ dove $k_M=\left\lceil k_{inf}(n)\right\rceil = \left\lfloor k_{sup}(n)\right\rfloor-1$.
Prendiamo il caso $n=97$: il limite superiore per $k_M$, ovvero $(n-1/2)/e+1/2$, deve essere di pochissimo superiore all’intero pi√Ļ vicino, visto che il limite inferiore √® separato da poco pi√Ļ di $1$ dal limite superiore ed √® inferiore all’intero pi√Ļ vicino $k_M$: si ha in effetti $(97-1/2)/e+1/2=36{,}00036607\ldots$ e questo suggerisce che la frazione $\dfrac{36-1/2}{97-1/2}=\dfrac{71}{193}$ sia un’ottima approssimazione di $1/e$ e in effetti $\dfrac{71}{193}$ corrisponde alla frazione continua di $1/e$ troncata al $9$° termine: infatti $1/e=[0;2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,\ldots]$ mentre $\dfrac{71}{193}=[0;2,1,2,1,1,4,1,1]$. Proviamo a fare lo stesso ragionamento con $n=24.586$: si ha $(24586-1/2)/e+1/2=9045{,}0000009204\ldots$ e questo suggerisce che anche la frazione $\dfrac{9045-1/2}{24586-1/2}=\dfrac{18089}{49171}$ sia un’ottima approssimazione di $1/e$, ed in effetti $\dfrac{18089}{49171}=[0; 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1,1]$ corrisponde alla frazione continua di $1/e$ troncata al $15$° termine. Ma vuoi vedere che…? Passiamo a $n=14.122.865$: $(14122865­-1/2)/e+1/2=5195512{,}000000001177\ldots$ e la frazione approssimante di $1/e$ √® stavolta $\dfrac{5195512-1/2}{14122865-1/2}=\dfrac{10391023}{28245729}$ che corrisponde a $[0; 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1,1]$, ovvero la frazione continua di $1/e$ troncata al $21$° termine.
Andando a ritroso, la frazione continua di $1/e$ troncata al $3$° termine, cio√® $\dfrac{1}{3}$, pu√≤ essere scritta come $\dfrac{1-1/2}{2-1/2}$ ed in effetti per $n=2$ vi sono due interi compresi fra il limite inferiore e superiore e $k=0$ massimizza la probabilit√† ma non coincide con $\left\lfloor(2-1/2)/e+1/2\right\rfloor$ (√® comunque un caso particolare perch√© anche $k=1$ massimizza le probabilit√†).
Tutto questo suggerisce di andare a guardare alla frazione continua di $1/e$ troncata al $27$° termine, che √® $\dfrac{10622799089}{28875761731}$ che possiamo scrivere come $\dfrac{5311399545-1/2}{14437880866-1/2}$. Che succede dunque per $n=14.437.880.866$ ? effettivamente anche in questo caso $k_M=\left\lfloor k_{sup}(n)\right\rfloor-1\ $. Questo suggerisce che $k_M=\left\lfloor k_{sup}(n)\right\rfloor$ tranne che per $n=(d_{6k+3}+1)/2$, $k \in \mathbb N$ dove $d_{6k+3}$ √® il denominatore della frazione continua di $1/e$ troncata al termine $6k+3$. Non sono in grado di provare questa congettura ma la ritengo molto probabile. O forse farei meglio a dire che ho trovato una dimostrazione ma lo spazio di questo post non √® sufficiente a contenerla ūüėČ.
Riprendendo in considerazione la prima disuguaglianza della $(3)$ si ha: $$\ln\left(\dfrac{n}{k+1}\right)+\dfrac12\left(\dfrac1{k+1}-\dfrac1n\right)<1 \iff \ln n-\dfrac1{2n}-1<\ln(k+1)-\dfrac1{2(k+1)}\iff$$ $$\iff \dfrac n{e^{1+\frac1{2n}}}<(k+1)e^{-\frac1{2(k+1)}}\iff \dfrac{e^{1+\frac 1{2n}}}{2n}>\dfrac 1{2(k+1)}e^{\frac 1{2(k+1)}}\ .\tag{5}$$Facciamo ora uso della funzione $W$ di Lambert, definita in $\mathbb R$ nell’intervallo $[-1/e,+\infty)$ da $x=W(x) e^{W(x)} \land W(x)\geq-1$: se nell’ultima disequazione della $(6)$ ci fosse il segno di uguaglianza si avrebbe $\dfrac 1{2(k+1)} = W \left(\dfrac{e^{1+\frac 1{2n}}}{2n}\right)$ ma poich√© la funzione $W$ di Lambert √® strettamente crescente, il verso della disuguaglianza rimane lo stesso e si ha $$\dfrac 1{2(k+1)}<W\left(\dfrac{e^{1+\frac 1{2n}}}{2n}\right) \iff k  > k\,'_{inf}(n)=f_W(n) = \left[ 2W \left( \dfrac{e^{1 +\frac 1{2n}}}{2n}\right)\right]^{-1}-1$$e questo pone un limite pi√Ļ stringente di quello della disequazione $(4)$ come si pu√≤ vedere dalla figura $2$, anche se la differenza fra $k_{sup}(n)$ e $k\,'_{inf}(n)$ rimane comunque sempre superiore a $1$. Si ha infatti $$I'(n)=k_{sup}(n) - k\,'_{inf}(n) = 1+\dfrac{e^2-1}{8\,e\,n}+O\left( \dfrac1{n^2}\right) \simeq 1+\dfrac{0{,}29}{n}-\dfrac{0{,}44}{n^2},$$ e sono quindi ancora possibili, e in effetti ci sono, casi in cui la restrizione $k\,'_{inf}(n)<k_M<k_{sup}(n)$ non determini univocamente $k_M$.
Indagando da $n=1$ a $n=100.000.000$ si ha $k_M=\left\lceil f_W(n) \right\rceil$ tranne che per $n=73.757$, cosa che, con ragionamenti simili a quelli visti prima, riconduce alla frazione gi√† vista $\dfrac{18089}{49171}$, e per $n=42.368.594$, che riconduce alla frazione, anch’essa gi√† vista, $\dfrac{10391023}{28245729}$. In entrambi i casi $k_M=\left\lceil k\,'_{inf}(n)\right\rceil+1$. Facendo i conti, siamo portati a pensare che l’uguaglianza $k_M=\left\lceil f_W(n) \right\rceil$ valga per ogni $n$ tranne che per $n=(3\cdot d_{6k+3}+1)/2$, $k \in \mathbb N, k\geq2$, dove $k_M=\left\lceil f_W(n) \right\rceil+1$. Il valore $n$ successivo da controllare sarebbe $43.313.642.597$ e in effetti si ha lo stesso comportamento.
Sempre indagando fra $n=1$ e $n=100.000.000$, il minimo valore assunto da $k_M-k\,'_{inf}$ è circa $1{,}96\times10^{-8}$ per $n=14.122.865$ mentre il minimo valore assunto da $k_{sup}-k_M$ è circa $3{,}53\times10^{-9}$ per $n=42.368.594$. Altri valori collegati alle frazioni continue troncate di $1/e$ sono riportati in figura $4$.
Sviluppando intorno a $\infty$ la funzione $f_W(n)$ si ottiene $f_W(n)=\dfrac{n-1/2}e-\dfrac12-\dfrac{e^2-1}{8\,e\,n}+O\left(\dfrac1{n^2}\right)$ e lo sviluppo troncato togliendo gli infinitesimi di ordine superiore al primo d√† gli stessi risultati nel valutare $\left\lceil f_W(n)\right\rceil$, questo almeno l’ho verificato per $n$ da $1$ a $100.000.000$ e nei valori critici collegati alle frazioni continue troncate di $1/e$ dove $f_W(n)$ pi√Ļ si avvicina inferiormente ad un valore intero (vedi figura $4$).
Ritornando alle frazioni continue troncate di $1/e$, tali frazioni, ovvero $\dfrac01$, $\dfrac{1}{2}$, $\dfrac{1}{3}$, $\dfrac{3}{8}$, $\dfrac{4}{11}$, $\dfrac{7}{19}$, $\dfrac{32}{87}$, $\dfrac{39}{106}$, $\dfrac{71}{193}$, $\dfrac{465}{1264},\ldots$, godono della proprietà di avere il numeratore che corrisponde al $k_M$ relativo al denominatore.
Il comportamento di $k_M$ è rappresentato nelle figure $5$, $6$, $7$ e $8$.
Veniamo ora alla probabilit√† di vincita usando il metodo ottimale. L’andamento √® raffigurato nelle figure $9$, $10$, $11$ e $12$. Cerco uno sviluppo asintotico. Si ha $$H_n=\sum_{m=1}^n\frac1m=\ln n+\gamma+\frac1{2n}-\frac1{12n^2}+O\left(\frac1{n^4}\right)\ $$dove $\gamma$ √® la costante di Eulero-Mascheroni. Applicando lo sviluppo alla $(1)$, ponendo $k=(n-1/2)/e\ $ e sviluppando in serie si ottiene$$p(n,k_M)=\dfrac1e+\dfrac{1-1/e}{2n}+O\left(\dfrac1{n^2}\right)\ .$$Si ha dunque $\displaystyle{\lim_{n\to\infty}p(n,k_M)=1/e}$. Come si vede delle figure $13$ e $14$, il termine $O\left(\dfrac1{n^2}\right)$ √® oscillante fra $-\dfrac{0{,}1}{n^2}$ e $\dfrac{0{,}25}{n^2}$ per $n>6$. Indagando fra $n=7$ e $n=100.000.000$ i valori estremi di $n^2\left[p(n,k_M)-\left(\dfrac1e+\dfrac{1-1/e}{2n}\right)\right]$ sono $-0{,}0979334322999872\ldots$  per  $n=42.368.594$ (ve lo ricordate?) e $0{,}24681514\ldots$ per $n=14$. Si trovano minimi relativi (rispetto ai numeri precedenti) in corrispondenza dei valori “critici” di $n$: per $n=97$ si ha il valore $-0{,}0975406968057175\ldots$, per $n=24.586$ si ha $-0{,}0979312612917916\ldots$, per $n=73.757$ si ha $-0{,}0979321480954257\ldots$, per $n=14.122.865$ si ha $-0{,}0979334284463647\ldots$, inoltre per $n=14.437.880.866$ (un altro numero “critico”) si ha un nuovo minimo pari a $-0{,}0979334327990594\ldots$. Parrebbe che ad ogni numero “critico” si raggiunga un nuovo minimo relativo e che questi minimi convergano verso un limite… che corrisponda ad un numero particolare?
Quali sono le probabilit√†, usando la strategia ottimale, di scegliere il pacco di rango $m$, che indicher√≤ $\texttt{#}m$? 
Consideriamo intanto il caso $n-k_M+1\leq m \leq n$, ovvero il caso in cui il pacco $\texttt{#}m$ √®, come rango, tra gli ultimi $k_M$. In questo caso l’unica possibilit√† che il pacco venga scelto √® che sia l’ultimo e venga scelto “forzatamente”. Infatti, se il pacco non √® l’ultimo, fra i primi $k_M$ pacchi che vengono scartati ve ne √® sicuramente almeno uno di rango maggiore e quindi il pacco $\texttt{#}m$ non potr√† essere scelto in posizione diversa dalla ultima in quanto di rango minore del massimo dei ranghi tra i primi $k_M$ pacchi scartati. Affinch√© venga scelto come ultimo, il pacco $\texttt{#}1$ deve essere fra i primi $k_M$ pacchi scartati (probabilit√† $\frac{k_M}n$) e il pacco $\texttt{#}m$ in ultima posizione (probabilit√† $\frac 1{n-1})$, quindi possiamo dire che
$$n-k_M+1\leq m \leq n\ \Rightarrow\ p(n,k_M,\texttt{#}m)=\dfrac{k_M}{n(n-1)}$$
quindi complessivamente c’√® una probabilit√† $\dfrac{k_M^2}{n(n-1)}$ di scegliere uno degli ultimi (come rango) $k_M$ pacchi, probabilit√† che tende a $1/e^2$ per $n$ che tende a infinito.
Per $n>1$ e $k>0$ la $(1)$ può essere riscritta come $$p(n,k,\texttt{#}1)=\sum_{j=k+1}^{n}\dfrac k{n(j-1)}\ .\tag{6}$$Se poniamo $x=k/n$ e $t=j/n$, si ha$$\lim_{n\to\infty} p(n,x\,n,\texttt{#}1)=\lim_{n\to\infty}\dfrac k n \sum_{j=k+1}^{n}\dfrac {1/n}{j/n-1/n}=x \int_{\frac1x}^1 \dfrac{dt}t=-x\ln x\ .\tag{7}$$
La funzione $-x\ln x$ ha un massimo in $x=1/e$ dove assume valore $1/e$ come ci aspettiamo, visto che per $n$ che tende a infinito $k_M/n$ tende a $1/e$ e $p(n,k_M,\texttt{#}1)$ tende a $1/e$.
Ognuno dei termini della sommatoria nella $(6)$ rappresenta la probabilit√† di trovare e scegliere il pacco $\texttt{#}1$ nella posizione $j$. Se invece vogliamo considerare la probabilit√† di trovare il pacco $\texttt{#}2$, dobbiamo moltiplicare ognuno di quei termini per la probabilit√† che il pacco $\texttt{#}1$ si trovi dopo il pacco $\texttt{#}2$, probabilit√† che vale $\dfrac{n-j}{n-1}$. L’ultimo termine della sommatoria verr√† moltiplicato in realt√† per $0$, ma dobbiamo aggiungere la probabilit√† che il pacco $\texttt{#}2$ venga scelto “forzatamente” in posizione $n$, che √® pari alla probabilit√† che il pacco $\texttt{#}1$ sia fra i primi $k$ pacchi e che il pacco $\texttt{#}2$ sia l’ultimo. Questa probabilit√† √® $\dfrac k{n}\cdot\dfrac1{n-1}$. Otteniamo dunque $$\displaystyle{p(n,k,\texttt{#}2)=\sum_{j=k+1}^{n} \dfrac{k(n-j)}{n(j-1)(n-1)}+\dfrac k{n(n-1)}}\ .\tag{8}$$Ora poniamo $k=k_M$ e facciamo tendere $n$ ad infinito, similmente a quanto fatto nella $(7)$ e si ha $$\lim_{n\to\infty} p(n,k_M,\texttt{#}2)=\lim_{n\to\infty} \dfrac {k_M} n \sum_{j=k_M+1}^{n}\dfrac {(1/n)(1-j/n)}{(j/n-1/n)(1-1/n)}=\dfrac1 e \int_{\frac1e}^1 \dfrac{1-t}{t}dt\ .\tag{9}$$Non mi sono cimentato nel calcolare la formula generale per $p(n,k_M,\texttt{#}m)$ per $n$ finito, ma √® facile convincersi, ripetendo i ragionamenti che hanno portato alla $(8)$ e passando al limite, che, se consideriamo il caso $n$ che tende a infinito, la $(9)$ √® un caso particolare della seguente identit√†: $$p_\infty(\texttt{#}m)=\lim_{n\to\infty}p(n,k_M,\texttt{#}m)=\dfrac1e \int_{\frac1e}^1 \dfrac{(1-t)^{m-1}}{t}dt \ .$$I valori $p_\infty(\texttt{#}m)$ sono rapidamente decrescenti: $p_\infty(\texttt{#}1)=\dfrac1e\simeq0{,}368$, $p_\infty(\texttt{#}2)=\dfrac1{e^2}\simeq0{,}135$, $p_\infty(\texttt{#}3)=\dfrac{-e^2+4e-1}{2e^3}\simeq0{,}0618$, $p_\infty(\texttt{#}4)\simeq0{,}0309$, $p_\infty(\texttt{#}5)\simeq0{,}0162\ $, $p_\infty(\texttt{#}6)\simeq0{,}00876$… Si ha inoltre $$\sum_{m=1}^\infty p_\infty(\texttt{#}m)=\sum_{m=1}^\infty \int_{\frac1e}^1 \dfrac{(1-t)^{m-1}}{e\,t}dt=\int_{\frac 1e}^1 \frac1{e\,t} \sum_{m=0}^\infty (1-t)^m dt=\int_{\frac1e}^1 \frac{dt}{e\,t^2}=1-\dfrac1e\ .$$Non sorprenda che sia $\displaystyle{\sum_{m=1}^\infty p_\infty(\texttt{#}m)\neq 1}$, in quanto in questo caso non ci sono le condizioni affinch√© si abbia $$\sum_{m=1}^\infty \lim_{n\to\infty} p(n,k_M,\texttt{#}m)= \lim_{n\to\infty}\sum_{m=1}^n p(n,k_M,\texttt{#}m)\ .$$In figura $15$ √® riportato l’andamento di $p(n,k_M,\texttt{#}m)$ per alcuni valori di $n$ e per $n\to\infty$.

Ritornando al problema iniziale, per $n=20$ si ha $k_M=7$ e con la strategia indicata si ha il $38{,}4\%$ di probabilit√† di portare a casa il primo premio, ed il $16{,}3\%$ di probabilit√† di portare a casa il secondo premio. In totale pi√Ļ del $50\%$ di probabilit√† di portarsi a casa o il primo premio o il “premio di consolazione”: non √® male per un gioco “al buio”, purch√© per√≤ si usi la migliore strategia.




Questo problema matematico, menzionato in genere come “problema della segretaria” o “problema del matrimonio” comparve per la prima volta in forma scritta nel febbraio 1960 nella mitica rubrica di Martin Gardner (1914-2010) su Scientific American, presentato come il “gioco del googol” (googol √® il nome del numero $10^{100}$). √ą anche noto come “problema della dote del sultano” dove si immagina che a un pretendente venga chiesto di scegliere, fra le figlie di un sultano, quella con la dote maggiore. Un problema simile era gi√† stato proposto dal matematico Arthur Cayley (1821-1895) dove per√≤ l’ammontare dei diversi premi √® noto al giocatore. Pare che Johannes Kepler (1571-1630) abbia affrontato nella vita reale un “gioco” simile a questo dopo la morte della prima moglie nel 1611, cercando di scegliere la “migliore” sposa possibile fra 11 candidate. La cosa gli richiese due anni di “investigazioni” e, dopo avere esaminato le 11 possibili spose, alla fine scelse la 5¬™. Se avesse conosciuto questo gioco e la sua soluzione, che prevede $k_M=4$ per $n=11$, forse avrebbe risparmiato molto tempo e fatica.
Maggiori dettagli sulla storia di questo problema nell’articolo di Ferguson citato in bibliografia.

__________________________

Bibliografia

John P. Gilbert and Frederick Mosteller, Recognizing the Maximum of a Sequence, Journal of the American Statistical Association Vol. 61, No. 313 (Mar., 1966), pp. 35-73 https://bit.ly/GilbMostMaxSeq
Thomas S. Ferguson, Who Solved the Secretary Problem?, Statistical Science. 4 (3): 282-289 https://bit.ly/FergusonSecretary
Wikipedia – Secretary problem https://bit.ly/WikiSecretaryProb



Figura 1. Andamento di $p(n,k)$ per diversi valori di $n$. Per $n\to\infty$ il grafico tende a quello della curva di equazione $y=-x\ln x$.

Figura 2. I punti corrispondono alle coppie $(n,k_M)$. Le coppie corrispondenti a denominatore e numeratore dello sviluppo troncato della frazione continua di $1/e$ sono rappresentate da punti cerchiati.

Figura 3. Come la precedente ma in un intervallo pi√Ļ ampio per $n$.

Figura 4. Andamento di $k\,'_{inf}$ e $k_{sup}$ per alcuni valori “critici” di $n$ legati allo sviluppo di $1/e$ in frazione continua. I numeri evidenziati in blu corrispondono a $k_M$.

Figura 5. Andamento del rapporto $\dfrac{k_M}{n-1/2}$ per $n$ fra $1$ e $200$.

Figura 6. Andamento del rapporto $\dfrac{k_M}{n-1/2}$ per $n$ fra $1$ e $200$, zoom attorno a $y=1/e$.

Figura 7. Andamento di $k_M-\dfrac{n-1/2}e$ per $n$ fra $1$ e $200$.
Si noti il picco negativo per $n=97$.

Figura 8. Andamento di $k_M-\dfrac{n-1/2}e$ per $n$ fra $24.500$ e $24.700$.
Si noti il picco negativo per $n=24.586$.


Figura 9. Andamento di $p(n,k_M)$ per $n$ da $1$ a $100$.

Figura 10. Andamento di $p(n,k_M)$ per $n$ da $1$ a $200$.

Figura 11. Andamento di $p(n,k_M)$ per $n$ da $1$ a $1000$.

Figura 12. Andamento di $p(n,k_M)$ per $n$ da $1$ a $20$ confrontato con quello dello sviluppo asintotico troncato.

Figura 13. Andamento della quantità $n^2\left[p(n,k_M)-\left(\dfrac1e+\dfrac{1-1/e}{2n}\right)\right]$
per $n$ fra $1$ e $200$. Si noti il picco negativo per $n=97$.

Figura 14. Andamento della quantità $n^2\left[p(n,k_M)-\left(\dfrac1e+\dfrac{1-1/e}{2n}\right)\right]$
per $n$ fra $24.500$ e $24.700$. Si noti il picco negativo per $n=24.586$.

Figura 15. Andamento di $p(n,k_M,\texttt{#}m)$ per alcuni valori di $n$ e per $n\to\infty$.

_____________________________________

Un particolare ringraziamento all’amico L. B. per la preziosa consulenza
su un argomento di cui è uno dei massimi esperti.


0 commenti:

Posta un commento