Siano $x_1, x_2,\ldots, x_k$ variabili aleatorie indipendenti che possono assumere con uguale probabilità i valori dell’insieme $\{1, 2, 3, …, N\}$. Qual è la probabilità $p(N,k)$ che esista un poligono di $k$ lati di lunghezza $x_1$, $x_2$,$\ldots$ $x_k$?
Vi sono $N^k$ tuple ordinate $(x_1,x_2,\ldots,x_k)$ con $x_1,x_2,\ldots, x_k \in \{1, 2, 3, \ldots, N\}$, e quindi la probabilità sarà $p(N)=\dfrac{P(N,k)}{N^k}$ dove $P(N,k)$ è il numero di tuple $(x_1,x_2,\ldots, x_k)$ che soddisfano le disuguaglianze triangolari $x_1<x_2+\ldots+x_k$, $\ x_2<x_3+\ldots+x_k+x_1$ $,\ldots,$ $x_k<x_1+x_2+\ldots + x_{k-1}$. Di fatto, se $x_1,x_2,\ldots, x_{k-1}< x_k$ l’unica disuguaglianza non banale è $x_k<x_1+x_2+\ldots+x_{k-1}$.
Vi sono $N^k$ tuple ordinate $(x_1,x_2,\ldots,x_k)$ con $x_1,x_2,\ldots, x_k \in \{1, 2, 3, \ldots, N\}$, e quindi la probabilità sarà $p(N)=\dfrac{P(N,k)}{N^k}$ dove $P(N,k)$ è il numero di tuple $(x_1,x_2,\ldots, x_k)$ che soddisfano le disuguaglianze triangolari $x_1<x_2+\ldots+x_k$, $\ x_2<x_3+\ldots+x_k+x_1$ $,\ldots,$ $x_k<x_1+x_2+\ldots + x_{k-1}$. Di fatto, se $x_1,x_2,\ldots, x_{k-1}< x_k$ l’unica disuguaglianza non banale è $x_k<x_1+x_2+\ldots+x_{k-1}$.
La chiave per risolvere il problema in modo ottimale è, anche nel caso generale:
Consideriamo ad esempio le $6$-tuple con elemento massimo $n$: quali di queste tuple non corrispondono ad un esagono? Quelle dove la somma degli altri $k-1=5$ elementi è minore o uguale a $n$, ovvero vale $1$, $2$, $\ldots,$ $n-1$ o $n$.
Supponiamo, ad esempio, di avere $10$ palline una di seguito all’altra.
Posizioniamo ora $k-2=4$ elementi separatori fra di loro, senza che vi possa essere più di un elemento separatore fra due palline adiacenti. Di fatto vi è una corrispondenza biunivoca fra ogni posizionamento dei separatori e le $5$-tuple ordinate – nel caso raffigurato qui sopra la $5$-tupla è $(2,1,4,1,2)$ – i cui elementi danno come somma $10$. In quanti modi possiamo porre questi separatori? in $\displaystyle{\binom{10-1}{5-1}}$ modi. Dunque in generale il numero di tuple di $k-1$ elementi con somma pari a $m$ è $\displaystyle{\binom{m-1}{k-2}}$.
Poiché partendo da una tupla di $k-1$ elementi possiamo ottenere una tupla di $k$ elementi posizionando l’elemento di valore $n$ in $k$ posizioni, il numero di $k$-tuple con elemento massimo $n$ che non soddisfano tutte le disuguaglianze triangolari è allora $d(n,k)=k\displaystyle{\sum_{m=1}^n \binom{m-1}{k-2}}$ e, utilizzando l’identità già vista nella puntata precedente, ovvero $\displaystyle{\binom{a}{b}=\binom{a+1}{b+1}-\binom{a}{b+1}}$, otteniamo:$$d(n,k)=\sum_{m=1}^n k\binom{m-1}{k-2}=k\sum_{m=1}^n\left[\binom{m}{k-1}-\binom{m-1}{k-1}\right]=\\=k\left[\binom{n}{k-1}-\binom{n-1}{k-1}+ \binom{n-1}{k-1}-\binom{n-2}{k-1}+\ldots+\binom1{k-1}-\binom0{k-1}\right]=\\=k\binom{n}{k-1}, $$sempre ricordando che se $0\leq a<b$ allora $\displaystyle{\binom{a}b=0}$. Questo non è un “trucco matematico”, in quanto l’annullamento del coefficiente binomiale avviene in corrispondenza di combinazioni impossibili.
Utilizzando nuovamente l’identità riguardante i coefficienti binomiali, troviamo che il numero complessivo di $k$-tuple che non soddisfano tutte le disuguaglianze triangolari, è dato da $$D(N,k) = \sum_{n=1}^N d(n,k)=\sum_{n=1}^N k\binom{n}{k-1} = k\sum_{n=1}^N \left[ \binom{n+1}k-\binom{n}k\right]=\\=k\left[\binom{N+1}k-\binom{N}k + \binom{N}k-\binom{N-1}k+ \ldots+ \binom2k-\binom1k\right]=k\binom{N+1}k\ .$$
Utilizzando nuovamente l’identità riguardante i coefficienti binomiali, troviamo che il numero complessivo di $k$-tuple che non soddisfano tutte le disuguaglianze triangolari, è dato da $$D(N,k) = \sum_{n=1}^N d(n,k)=\sum_{n=1}^N k\binom{n}{k-1} = k\sum_{n=1}^N \left[ \binom{n+1}k-\binom{n}k\right]=\\=k\left[\binom{N+1}k-\binom{N}k + \binom{N}k-\binom{N-1}k+ \ldots+ \binom2k-\binom1k\right]=k\binom{N+1}k\ .$$
Si avrà allora $$P(N,k)=N^k-D(N,k)=N^k-k\binom{N+1}k=N^k - \dfrac{(N+1)N\ldots (N-k+2)}{(k-1)!}$$
La probabilità che una $k$-tupla con elementi in $\{1,2,\ldots,N\}$ corrisponda alle lunghezze dei lati di un poligono di $k$ lati è dunque $$p(N,k)=\dfrac{P(N)}{N^k}=1-\dfrac1{(k-1)!}\left(1+\dfrac1N\right)\left(1-\dfrac1N\right)\ldots\left(1-\dfrac{k-2}N\right)$$ e si ha $\displaystyle{ \lim_{N\to\infty}p(N,k) = 1-\dfrac1{(k-1)!}}$ che quindi è anche la probabilità che una $k$-tupla di variabili aleatorie con distribuzione uniforme in $(0,1)$ corrisponda alle lunghezze dei lati di un poligono di $k$ lati, per le ragioni viste nella puntata precedente.
Post
0 commenti:
Posta un commento