Lunghezza media del più lungo tra $n$ segmenti
Rileggendo questo, mi chiedevo: se si scelgono $n-1$ punti nell'intervallo $[0,1]$ in modo uniforme, si formano naturalmente $n$ segmenti. Qual è la lunghezza media del più lungo di questi segmenti? Nel link sopra abbiamo dimostrato che se $n=3$ allora la risposta è $11/18$. Ma cosa succede se $n$ è maggiore di $3$?
Quanto è non banale questo problema?
Quanto è non banale questo problema?
Risposte
Eh sì ma bisogna calcolarlo per $n$ qualsiasi.
.
In questi giorni ho elaborato questo integrale mostruoso.
Con l'aiuto di un programma di calcolo simbolico (Python sympy) ho controllato e in effetti i primi 10 valori coincidono con quelli forniti da sellacollesella.
Intanto lo metto qui, poi vedo di fornire una spiegazione, assieme alla giustificazione della formula
\( \begin{aligned}\frac{1}{n}\sum_{k=1}^n\frac{1}{k}\end{aligned} \).
La formula qui sotto e' una frazione con un integrale multiplo sia al numeratore che al denominatore.
Gli estremi di integrazione e le variabili sono le stesse, sia sopra che sotto.
Quello che cambia e' l'integrando all'interno.
La formula in sostanza calcola un baricentro, e direi che e' lo stesso concetto applicato nel codice di sellacollesella.
Infatti nel codice si legge "integrate / integrate", un rapporto di integrali.
\[
\frac{
\int_{0}^{\frac{1}{n}} \int_{x_n}^{\frac{1-x_n}{n-1}} \int_{x_{n-1}}^{\frac{1-x_n-x_{n-1}}{n-2}}
...
\int_{x_{k+1}}^{{\frac{1}{k}} \left(1- \sum_{i=k+1}^n x_i \right)}
...
\int_{x_{3}}^{{\frac{1}{2}} \left(1- \sum_{i=3}^n x_i \right)}
\left(1-\sum_{i=2}^{n} x_i \right)
dx_2 \ \dots\ dx_k \ \dots\ dx_{n-2}\ dx_{n-1}\ dx_n
}
{
\int_{0}^{\frac{1}{n}} \int_{x_n}^{\frac{1-x_n}{n-1}} \int_{x_{n-1}}^{\frac{1-x_n-x_{n-1}}{n-2}}
...
\int_{x_{k+1}}^{{\frac{1}{k}} \left(1- \sum_{i=k+1}^n x_i \right)}
...
\int_{x_{3}}^{{\frac{1}{2}} \left(1- \sum_{i=3}^n x_i \right)}
\ 1\
dx_2 \ \dots\ dx_k \ \dots\ dx_{n-2}\ dx_{n-1}\ dx_n
}
\]
Con l'aiuto di un programma di calcolo simbolico (Python sympy) ho controllato e in effetti i primi 10 valori coincidono con quelli forniti da sellacollesella.
Intanto lo metto qui, poi vedo di fornire una spiegazione, assieme alla giustificazione della formula
\( \begin{aligned}\frac{1}{n}\sum_{k=1}^n\frac{1}{k}\end{aligned} \).
La formula qui sotto e' una frazione con un integrale multiplo sia al numeratore che al denominatore.
Gli estremi di integrazione e le variabili sono le stesse, sia sopra che sotto.
Quello che cambia e' l'integrando all'interno.
La formula in sostanza calcola un baricentro, e direi che e' lo stesso concetto applicato nel codice di sellacollesella.
Infatti nel codice si legge "integrate / integrate", un rapporto di integrali.
\[
\frac{
\int_{0}^{\frac{1}{n}} \int_{x_n}^{\frac{1-x_n}{n-1}} \int_{x_{n-1}}^{\frac{1-x_n-x_{n-1}}{n-2}}
...
\int_{x_{k+1}}^{{\frac{1}{k}} \left(1- \sum_{i=k+1}^n x_i \right)}
...
\int_{x_{3}}^{{\frac{1}{2}} \left(1- \sum_{i=3}^n x_i \right)}
\left(1-\sum_{i=2}^{n} x_i \right)
dx_2 \ \dots\ dx_k \ \dots\ dx_{n-2}\ dx_{n-1}\ dx_n
}
{
\int_{0}^{\frac{1}{n}} \int_{x_n}^{\frac{1-x_n}{n-1}} \int_{x_{n-1}}^{\frac{1-x_n-x_{n-1}}{n-2}}
...
\int_{x_{k+1}}^{{\frac{1}{k}} \left(1- \sum_{i=k+1}^n x_i \right)}
...
\int_{x_{3}}^{{\frac{1}{2}} \left(1- \sum_{i=3}^n x_i \right)}
\ 1\
dx_2 \ \dots\ dx_k \ \dots\ dx_{n-2}\ dx_{n-1}\ dx_n
}
\]
Ho fatto un piccolo test (simulato 1000000 di casi per diversi n) in Julia e sembra in effetti seguire quei numeri. Vista la struttura mi chiedo quindi se esiste un qualche tipo di dimostrazione semplice basata sull'induzione. La formula suggerisce infatti che abbiamo qualcosa come segue
\[ S_n = \frac{n - 1}{n} S_{n - 1} + \frac{1}{n^2}. \]
Sembra molto la formula per aggiornare una media da \(n - 1\) a \(n\) valori.
\[ S_n = \frac{n - 1}{n} S_{n - 1} + \frac{1}{n^2}. \]
Sembra molto la formula per aggiornare una media da \(n - 1\) a \(n\) valori.
.
Quindi $x_1$, $x_1 + x_2$, ... sono le lunghezze dei segmenti ordinati per grandezza? Non sono certo si possa affermare senza dimostrazione che \(\mu(x_1, x_2, \dots, x_n) = 1\).
EDIT: Tuttavia, rispensandoci, credo sia vero che se elimino $x_1$ ad ogni segmento (eliminando i punti che a quel punto diventano uguali) i restanti punti saranno di nuovo uniformemente distribuiti in $[0, 1 - nx_1]$.
EDIT: Tuttavia, rispensandoci, credo sia vero che se elimino $x_1$ ad ogni segmento (eliminando i punti che a quel punto diventano uguali) i restanti punti saranno di nuovo uniformemente distribuiti in $[0, 1 - nx_1]$.
.
Dimostrazione della formula $1/n \sum_{k=1}^n 1/k$ e altre formule che determinano la lunghezza media dei segmenti in ordine di lunghezza.
Gli $n-1$ punti $(p_1, p_2, ..., p_{n-1})$ sono collocati a caso tra gli estremi $p_0 = 0$ e $p_n = 1$.
Invece di considerare i punti, si considerano le lunghezze degli $n$ segmenti lunghi $x_k = p_k - p_{k-1}$.
Ogni insieme di segmenti esiste assieme alle $n!$ combinazioni che si ottengono scambiando di posto i segmenti in tutti i modi possibili.
Ognuno degli $n!$ segmenti contribuisce alla media con peso uguale, infatti la lunghezza del segmento piu' lungo rimane la stessa.
Ai fini del calcolo della media dall'insieme di $n!$ segmenti scegliamo l'insieme in cui i segmenti sono ordinati in modo decrescente. Questa scelta si rivela utile in seguito.
Abbiamo quindi $x_1 \ge x_2 \ge ... \ge x_{n-1} \ge x_n$ e inoltre $x_1 + x_2 + ... + x_{n-1} + x_n = 1$.
Ora si considerano le lunghezze dei segmenti come coordinate di uno spazio vettoriale di dimensione $n$ in questo modo, formando $n$ coordinate:
$C_1 = {x_1, 0, 0, ..., 0}$
$C_2 = {0, x_2, 0, ..., 0}$
$...$
$C_n = {0, 0, 0, ..., x_n}$
L'insieme di tutte le possibili posizioni forma un dominio nello spazio vettoriale.
Ci chiediamo quale sia l'inviluppo, la forma dell'insieme di tutte le possibili coordinate.
Iniziamo considerando le coordinate estreme per il segmento $x_1$.
Siccome $x_1$ e' il piu' lungo, sicuramente individua il vertice
$V_1 = {1, 0, 0, ..., 0}$
Per il segmento $x_2$, bisogna considerare che $x_1 \ge x_2$, quindi sara' lungo al massimo $1/2$, il suo vertice sara'
$V_2 = {1/2, 1/2, 0, ..., 0}$
Per il segmento $x_3$, bisogna considerare che $x_1 \ge x_2 \ge x_3$, quindi sara' lungo al massimo $1/3$ e la sua posizione estrema, il suo vertice sara'
$V_3 = {1/3, 1/3, 1/3, ..., 0}$
Si ottengono cosi' $n$ vertici
$V_1 = {1, 0, 0, ..., 0}$
$V_2 = {1/2, 1/2, 0, ..., 0}$
$V_3 = {1/3, 1/3, 1/3, ..., 0}$
$...$
$V_n = {1/n, 1/n, 1/n, ..., 1/n}$
D'altra parte dalla relazione $x_1 + x_2 + ... + x_{n-1} + x_n = 1$ si conclude che le coordinate formano un
simplesso di dimensione $n-1$ in uno spazio $n$ dimensionale.
Un simplesso e' un "tetraedro irregolare" di dimensione arbitraria.
Ad esempio un triangolo e' un simplesso di dimensione $2$, un poligono di $3$ punti in uno spazio tridimensionale, che nel nostro caso giace sul piano $x_1 + x_2 + x_3 = 1$.
Un tetraedro irregolare e' un simplesso di dimensione $3$ in uno spazio a $4$ dimensioni, e cosi' via.
Il calcolo del baricentro del simplesso e' particolarmente facile e ci consente di determinare la lunghezza media dei vari segmenti, cosi' come il baricentro e' il punto medio del simplesso.
Il baricentro si calcola sommando le coordinate degli $n$ vertici e dividendo per $n$.
$B = 1/n (V_1 + V_2 + ... + V_n ) = 1/n (\sum_{k = 1}^n 1/k, \sum_{k = 2}^n 1/k, ... \sum_{k = n-1}^n 1/k, 1/n )$.
Scrivendo in modo piu' chiaro, la coordinata $1$ del baricentro e': $1/n \sum_{k = 1}^n 1/k$
La coordinata $2$ del baricentro e': $1/n \sum_{k = 2}^n 1/k$
La coordinata $n-1$ del baricentro e': $1/n \sum_{k = n-1}^n 1/k$
La coordinata $n$ del baricentro e': $1/n \sum_{k = n}^n 1/k = 1/n^2$
La coordinata $1$ e' la lunghezza media del segmento piu' lungo.
La coordinata $2$ e' la lunghezza media del secondo segmento in ordine di lunghezza, ovvero, tolto il segmento piu' lungo, e' la lunghezza media di quello piu' lungo tra gli altri.
La coordinata $3$ e' la lunghezza media del terzo segmento in ordine di lunghezza.
La coordinata $n$ e' la lunghezza media del segmento piu' corto.
Gli $n-1$ punti $(p_1, p_2, ..., p_{n-1})$ sono collocati a caso tra gli estremi $p_0 = 0$ e $p_n = 1$.
Invece di considerare i punti, si considerano le lunghezze degli $n$ segmenti lunghi $x_k = p_k - p_{k-1}$.
Ogni insieme di segmenti esiste assieme alle $n!$ combinazioni che si ottengono scambiando di posto i segmenti in tutti i modi possibili.
Ognuno degli $n!$ segmenti contribuisce alla media con peso uguale, infatti la lunghezza del segmento piu' lungo rimane la stessa.
Ai fini del calcolo della media dall'insieme di $n!$ segmenti scegliamo l'insieme in cui i segmenti sono ordinati in modo decrescente. Questa scelta si rivela utile in seguito.
Abbiamo quindi $x_1 \ge x_2 \ge ... \ge x_{n-1} \ge x_n$ e inoltre $x_1 + x_2 + ... + x_{n-1} + x_n = 1$.
Ora si considerano le lunghezze dei segmenti come coordinate di uno spazio vettoriale di dimensione $n$ in questo modo, formando $n$ coordinate:
$C_1 = {x_1, 0, 0, ..., 0}$
$C_2 = {0, x_2, 0, ..., 0}$
$...$
$C_n = {0, 0, 0, ..., x_n}$
L'insieme di tutte le possibili posizioni forma un dominio nello spazio vettoriale.
Ci chiediamo quale sia l'inviluppo, la forma dell'insieme di tutte le possibili coordinate.
Iniziamo considerando le coordinate estreme per il segmento $x_1$.
Siccome $x_1$ e' il piu' lungo, sicuramente individua il vertice
$V_1 = {1, 0, 0, ..., 0}$
Per il segmento $x_2$, bisogna considerare che $x_1 \ge x_2$, quindi sara' lungo al massimo $1/2$, il suo vertice sara'
$V_2 = {1/2, 1/2, 0, ..., 0}$
Per il segmento $x_3$, bisogna considerare che $x_1 \ge x_2 \ge x_3$, quindi sara' lungo al massimo $1/3$ e la sua posizione estrema, il suo vertice sara'
$V_3 = {1/3, 1/3, 1/3, ..., 0}$
Si ottengono cosi' $n$ vertici
$V_1 = {1, 0, 0, ..., 0}$
$V_2 = {1/2, 1/2, 0, ..., 0}$
$V_3 = {1/3, 1/3, 1/3, ..., 0}$
$...$
$V_n = {1/n, 1/n, 1/n, ..., 1/n}$
D'altra parte dalla relazione $x_1 + x_2 + ... + x_{n-1} + x_n = 1$ si conclude che le coordinate formano un
simplesso di dimensione $n-1$ in uno spazio $n$ dimensionale.
Un simplesso e' un "tetraedro irregolare" di dimensione arbitraria.
Ad esempio un triangolo e' un simplesso di dimensione $2$, un poligono di $3$ punti in uno spazio tridimensionale, che nel nostro caso giace sul piano $x_1 + x_2 + x_3 = 1$.
Un tetraedro irregolare e' un simplesso di dimensione $3$ in uno spazio a $4$ dimensioni, e cosi' via.
Il calcolo del baricentro del simplesso e' particolarmente facile e ci consente di determinare la lunghezza media dei vari segmenti, cosi' come il baricentro e' il punto medio del simplesso.
Il baricentro si calcola sommando le coordinate degli $n$ vertici e dividendo per $n$.
$B = 1/n (V_1 + V_2 + ... + V_n ) = 1/n (\sum_{k = 1}^n 1/k, \sum_{k = 2}^n 1/k, ... \sum_{k = n-1}^n 1/k, 1/n )$.
Scrivendo in modo piu' chiaro, la coordinata $1$ del baricentro e': $1/n \sum_{k = 1}^n 1/k$
La coordinata $2$ del baricentro e': $1/n \sum_{k = 2}^n 1/k$
La coordinata $n-1$ del baricentro e': $1/n \sum_{k = n-1}^n 1/k$
La coordinata $n$ del baricentro e': $1/n \sum_{k = n}^n 1/k = 1/n^2$
La coordinata $1$ e' la lunghezza media del segmento piu' lungo.
La coordinata $2$ e' la lunghezza media del secondo segmento in ordine di lunghezza, ovvero, tolto il segmento piu' lungo, e' la lunghezza media di quello piu' lungo tra gli altri.
La coordinata $3$ e' la lunghezza media del terzo segmento in ordine di lunghezza.
La coordinata $n$ e' la lunghezza media del segmento piu' corto.
Mi piace, ma credo che rimanga la domanda principale che ci eravamo posti in precedenza. È vero che ogni combinazione di lunghezze di segmenti $x_1$, $x_2$, ..., $x_n$ nel tuo simplesso ha la stessa probabilità di occorrere? Sono un po' arrugginito con questo genere di problemi, ma se non fosse così allora non credo tu possa calcolare in quel modo il baricentro. Mi sbaglio?
EDIT: Ripensandoci il tuo discorso iniziale è in effetti una specie di dimostrazione e posso ora vedere come ad ogni configurazione di lunghezze corrispondano lo stesso numero di configurazioni di punti.
EDIT: Ripensandoci il tuo discorso iniziale è in effetti una specie di dimostrazione e posso ora vedere come ad ogni configurazione di lunghezze corrispondano lo stesso numero di configurazioni di punti.
Grazie! Devo capire bene i vostri argomenti, ma intanto ho una domanda: se la lunghezza media del segmento più lungo corrisponde a fare un baricentro, a cosa corrisponde la lunghezza media del segmento più corto?
.
"Martino":
Grazie! Devo capire bene i vostri argomenti, ma intanto ho una domanda: se la lunghezza media del segmento più lungo corrisponde a fare un baricentro, a cosa corrisponde la lunghezza media del segmento più corto?
Siamo in uno spazio a $n$ dimensioni.
Ogni punto in un spazio a $n$ dimensioni ha ovviamente $n$ coordinate.
Per essere chiari, nello spazio tridimensionale ogni punto ha 3 coordinate: $x, y, z$.
La prima coordinata, ad es. $x$ nello spazio tridimensionale e' la media del segmento piu' lungo.
La seconda coordinata, ad es. $y$ e' la media della lunghezza del secondo segmento piu' lungo.
Ecc....
L'ultima coordinata e' la media del segmento piu' corto.
Sempre nel caso tridimensionale, il baricentro e' in $B = (11/18, 5/18, 1/9)$
$11/18$ e' media del segmento piu' lungo, $5/18$ e' la media del segmento intermedio, $1/9$ e' la media di quello piu' corto.
"sellacollesella":
EDIT: rileggendo la risposta di Quinzio, mi pare che diciamo le stesse cose, ma con coordinate invertite.
Si certo, dipende da come vengono ordinati i segmenti, se dal piu' grande al piu' piccolo o viceversa.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo