Accoppiare i palloncini

[Overflow94]

Abbiamo $ n $ vasi ognuno etichettato con il corrispettivo indice da $ 1 $ a $ n $, e $ n $ palloncini ognuno etichettato con il corrispettivo indice da $ 1 $ a $ n $. Prendiamo uno dopo l'altro i palloncini e mettiamoli nei vasi in modo completamente casuale, ovvero: prendiamo il palloncino $ 1 $ e mettiamolo con probabilità $ 1/n $ in uno degli $ n $ vasi liberi, prendiamo il palloncini $ 2 $ e mettiamolo con probabilità $ 1/(n-1) $ in uno degli $ n-1 $ vasi liberi e così via...

Sia $ X_n $ la variabile casuale che dice quanti palloncini hanno "matchato" il proprio vaso, ovvero il numero di palloncini che sono stati messi nel vaso etichettato con lo stesso indice.

1) Quanto è il valore atteso $ E[X_n]$ ?
2) Quanto vale la probabilità $ Pr(X_n=0)$ ?
3) Quanto vale $ lim_(n->oo) Pr(X_n=0) $ ?

[ondine1]

Ci provo!

Indico con $p(k,n)$ la proabilità che ci siano $k$ match quando ci sono $n$ palloncini totali.
Se viene dato un numero $n$ iniziale di palloncini allora ogni particolare configurazione avrà probabilità $1/(n!)$ di essere sorteggiata, quindi se serco la probabilità di $k$ match sarà in generale:
$p(k)= 1/(n!)( (n), (k) ) M(0,n-k) $
dove con $M(0,n)$ indico in quanti modi possono risultare 0 match con n palloncini in totale.
scrivendo esplicitamente il binomiale si ha che:
$p(k,n)= 1/(n!) (n!)/((k!)(n-k!)) M(0,n-k)= 1/(k!) p(0,n-k)$
da cui si può ricavare la fondamentale relazione:
$p(k-1,n)= k p(k,n+1)$.
A questo si accompagna la relazione: $p(0,0)-= 1$ che permette di risolvere univocamente il problema.
1) Il valore atteso è:
$E[X_n]=sum_(k=0)^ n kp(k,n)= sum_(k=1)^ n kp(k,n)=sum_(k=1)^ n p(k-1,n-1)=sum_(t=0)^ (n-1) p(t,n-1)=1$ dato che l'ultima sommatoria è semplicemente la somma di tutte le probabilità che è 1.
2) si ha che:
$P(0,n)=1-sum_(k=1)^n p(k,n)= 1-sum_(k=1)^ n 1/(k!) p(0,n-k)$
Non so se il problema chieda di esprimere $p(0,n)$ analiticamente (se è possibile farlo) in ogni caso non ci sono riuscito purtroppo .
3)
Vedendo il punto 2 si nota che mano a mano che gli n crescono, all'avvicinarsi al limite $L$ (che suppongo esista) allora i valori con n piccolo, lontani dal limite, verrano mano a mano soppressi ( hanno valori vicini a n! al denominatore). Quindi partendo da:
$P(0,n)=1-sum_(k=1)^ n (p(0,n-k))/(k!)$
si può scrivere che
$L=1-sum_(k=1)^ n L/(k!) + epsilon (n)$
dove con $epsilon$ si indica l'errore che si sta commettendo trascurando i valori delle probabilità diversi dal valore limite, inoltre si ha $lim_(n ->+oo) epsilon (n)=0$
perciò
$L=(1)/(1+sum_(k=1)^(+oo) 1/(k!))= (1)/(1+(e-1))= 1/e$

[Overflow94]

@ondine: hai risposto correttamente al punto 1 e 3, per il punto 2 volevo mettere in luce alcune cose... di seguito riporto le soluzioni che conosco al problema e degli approfondimenti

Il punto 2 e 3 sono spiegati nel esempio 1.3 a pag. 10 del libro "Multivariate Probability" di John H. McColl, quando lo lessi qualche anno fa mi triggherò molto per il risultato "paradossale" che ottiene.

Prima di spiegare la soluzione dell'autore al punto 2, riporto la mia soluzione al punto 1.

Consideriamo il gruppo simmetrico $ S_n $ che agisce su $ A = {1, 2, ..., n} $ tramite l'azione $ sigma * i= sigma_i(i) $.

La probabilità di avere $ k $ match equivale alla probabilità che prendendo a caso un elemento $ sigma $ di $ S_n $ questo abbia $ k $ punti fissi. Per il lemma di Burnside il numero medio di punti fissi è uguale alle orbite di $ A $ sotto l'azione di $ S_n $, e quindi è uguale a $ 1 $.


Ero interessato a trovare una versione "probabilistica/combinatoria" di questo risultato come la tua @ondine e viceversa sono ancora interessato a trovare una versione "algebrica" della soluzione al punto 2 e 3 proposte dall'autore.

Vienamo alla soluzione del libro.

Cominciamo considerando che $ P(E_1 uu E_2)= P(E_1)+P(E_2)-P(E_1nn E_2) $ . Applicandola ripetutamente otteniamo:

$ P(E_1 uu E_2 uu E_3)= P(E_1uuE_2)+P(E_3)-P((E_1uuE_2)nn E_3)= $
$ =P(E_1uuE_2)+P(E_3)-P((E_1nnE_3) uu (E_2nnE_3))= $
$ =P(E_1uuE_2)+P(E_3)-P(E_1nnE_3) -P (E_2nnE_3)+ P(E_1 nn E_2 nn E_3)= $
$ =P(E_1) + P(E_2)+P(E_3)-P(E_1nnE_2) -P(E_1nnE_3) -P (E_2nnE_3)+ P(E_1 nn E_2 nn E_3)= $
$ = sum_(i=1)^3P(E_i) -sum_(i=1)^2sum_(j=i+1)^3P(E_i nnE_j)+ P(E_1 nn E_2 nn E_3) $

Il risultato che l'autore utilizza per risolvere il problema si basa sulla generalizzazione di questa formula e si può dimostrare facilmente per induzione:

$ P(E_1 uu E_2 uu ...uuE_n)=sum_(i=1)^n P(E_i) -sum_(i=1)^(n-1)sum_(j=i+1)^nP(E_i nn E_j) + sum_(i=1)^(n-2)sum_(j=i+1)^(n-1) sum_(k=j+1)^nP(E_i nn E_j nn E_k) - ... + (-1)^(n-1)P(E_1 nn E_2 nn ... nn E_n) $

Si applica al nostro problema considerando l'evento $ E_i $ "l'i-esimo palloncino è correttamente matchato":

$ P(X_n=0)=1-P(E_i uu E_2 uu ... uu E_n) $

$ P(E_i)=((n-1)!)/(n!)=1/n $
$ P(E_i nn E_j)=((n-2)!)/(n!) $
La probabilità dell'intesezione di $ m $ eventi è $ ((n-m)!)/(n!) $

Sostituendo nella formula generale e considerando che ogni sommatoria che coinvolge le intersezioni di $ k $ eventi ha $ ( (n), (k) ) $ termini si ottiene:

$ P(E_1 uu E_2 uu ... uu E_n)= $
$=n((n-1)!)/(n!)-( (n), (2) )((n-2)!)/(n!)+...+(-1)^(n-1)1/(n!)=$
$ = 1 - 1/(2!) + 1/(3!)- ... + (-1)^(n-1)1/(n!) $

Quindi $ P(X_n = 0) = 1/(2!) - 1/(3!)+ ... + (-1)^n1/(n!) $ .

Ciò non solo tende a $ 1/e $ ma la cosa più sorprendente secondo me, e che vorrei comprendere meglio, è che i pari sono più difficili da accoppiare, nel senso che valgono $ P(X_(2k)=0) > P(X_(2k-1)=0) $ e $ P(X_(2k)=0) > P(X_(2k+1)=0) $ .

[ondine1]

@Overflow94 intanto ti ringrazio per aver proposto questo problema interessante e a mio avviso per niente banale! Belle anche le soluzioni della tua risposta!

Una precisazione, nel punto 3) ho dimostrato che se la successione $P(0,n)$ avesse un limite, allora esso sarebbe $L=1/e$. Però a priori potrebbe anche non essere convergente. Si dimostra che quella successione è di Cauchy e quindi convergente con limite $L$.
Tornando alla soluzione del punto 2 (che risponderebbe direttamente all domanda 3 senza bisogno di mostrare che la successione è di Cauchy) l'ultima cosa che rimane da fare è dimostrare che la successione trovata $a_n-=p(0,n)$definita per ricorrenza
$a_n=1-sum_(k=1)^n1/(k!) a_(n-k)$
$a_0=1$
implica che il termine n-esimo sia $a_n=sum_(k=0)^n (-1)^k/(k!)$