Lunghezza del segmento più corto

[Pigkappa]

Spostato in MNE -- EvG

Scelgo casualmente due punti su un segmento di lunghezza 1 (estraendoli da distribuzioni uniformi su [0,1]). In questo modo, il segmento e' diviso in tre parti. Qual e' il valor medio della lunghezza della parte più corta?

[karlosson_sul_tetto]

Cerco di risolvere un problema più generale: dati n punti casuali su [0,a], qual è la lunghezza media del segmento più piccolo tra i $n+1$ che si formano?

Testo nascosto:

Noto che ad una qualsiasi distribuzione di n punti, corrisponde una $n+1$-upla di reali la cui somma fa 1, corrispondente alla lunghezza dei segmenti che i punti formano. Dato che c'è una bigezione tra le configurazione dei punti e le $n+1$-uple ordinate, mi basta considerare il valore medio del numero più piccolo appartenente alla $n+1$-upla. Per comodità, posso permutarla in modo che i suoi termini siano (debolmente) decrescenti: ci sono $(n+1)!$ modi di disporre i segmenti, corrispondenti a $(n+1)!$ modi di disporre n punti che diano gli stessi segmenti nello stesso ordine. La disposizione dei punti è equiprobabile, quindi posso "raggrupparli" in casi più semplici in cui i segmenti sono decrescenti in lunghezza.
Inoltre, non ci dovrebbero essere problemi riguardo a segmenti uguali che conterebbero più volte scambiati durante una permutazione, perché ad ognuno di essi comunque corrisponde un'ordinamento di punti particolare. (Questa premessa è scritta abbastanza male e non sono neanche sicuro della sua correttezza probabilistica )

Chiamando f(a,n) la lunghezza media del segmento più piccolo risultante dalla divisione di uno lungo $a$ in $n$ punti, voglio dimostrare:
$f(a,n)=\frac{a}{2^n(n+1)}$

Passo Base: 1 punto di coordinata $x$, il segmento $[0,a]$ è diviso in due lunghi $x$ e $a-x$. Per la pre-supposta di prima, $x\geq \frac{a}{2}$. Il segmento più piccolo è quello compreso tra $x$ e $a$, quindi la domanda è "qual è la lunghezza media di un segmento che può variare a 0 a $\frac{a}{2}$?"; la risposta è $\frac{a}{4}$, perché per ogni segmento $y$ esiste il corrispettivo lungo $\frac{a}{2}-y$, la cui media fa $\frac{a}{4}$.

Passo Induttivo: $n \rightarrow n+1$ punti. Per il wlog di prima, gli $n+2$ segmenti sono ordinati in ordine decrescente, quindi il primo punto è posto a $\geq \frac{a}{n+2}$ (per pigeonhole, esiste un segmento lungo almeno $\frac{1}{n+2}$ del totale), lasciando uno spazio $b$ compreso tra 0 e $a\frac{n+1}{n+2}$ per gli altri n punti. Per ipotesi induttiva, $f(b,n)=\frac{b}{2^n(n+1)}$. Ora la lunghezza media di $b$, per lo stesso ragionamento del passo base, è $\frac{a(n+1)}{2(n+2)}$, quindi $f(a,n+1)=f(b,n)=\frac{b}{2^n(n+1)}=\frac{\frac{a(n+1)}{2(n+2)}}{2^n(n+1)}=\frac{a}{2^{n+1}(n+2)}$

La risposta al problema con $a=1$ e $n=2$ dovrebbe essere $\frac{1}{12}$.

[Pigkappa]

Leggo in dettaglio tra poco ma intanto... Rilanciamo! Qual è la lunghezza media del più lungo?

[Pigkappa]

la risposta è $\frac{a}{4}$, perché per ogni segmento $y$ esiste il corrispettivo lungo $\frac{a}{2}-y$, la cui media fa $\frac{a}{4}$.

Ok che esiste, ma sono equiprobabili..?

Provando a fare il problema con Mathematica mi sembra che la risposta converga a $ 1/9 $ piuttosto che [math]1/12

[Lasker]

Più in generale la risposta alla generalizzazione di karlosson_sul_tetto dovrebbe venire (se ricordo bene)

Testo nascosto:

$$\frac{a}{(n+1)^2}$$

Quindi credo abbia ragione Pigkappa! In caso se volete provo a rifarlo appena trovo un po' di tempo.

[Troleito br00tal]

Ma c'è una soluzione elementare? L'unica che mi sembra di aver trovato usa cose decisamente poco olimpiche (non lo chiedo per rompere, giusto per sapere se tentare di trovarne una).

[Pigkappa]

Per la verita', non lo so! A un esame di un concorso era stato detto di calcolare la lunghezza media del massimo, per cui penso ci sia una soluzione abbastanza facile di quello, che pero' potrebbe non usare tecniche strettamente olimpiche (io sinceramente la soluzione non l'ho trovata). Poi io mi sono chiesto come si fa il minimo, ma non so quanto sia difficile quello.

Se riuscite a farne uno (o entrambi) postate la soluzione per favore

[EvaristeG]

Facciamo così. Io vi dico come si fa da MNE e sposto lì il thread (non capisco proprio perché sia qui).
Lasciamo aperte tre domande:
1- dove scazza la soluzione di karlosson?
2- come si fa in maniera elementare?
3- che succede con $n$ punti?

Testo nascosto:

Consideriamo la coppia $(x,y)\in [0,1]^2$ che individua i due punti scelti a caso. Essendo "a caso", in questo caso, determinato da distribuzione uniforme, la probabilità che $(x,y)\in A$ equivale all'area di $A$. Ora, consideriamo la variabile casuale
$$z=\min\{x,\ y,\ 1-x,\ 1-y,\ |x-y|\}$$
noi vogliamo la sua speranza. Abbiamo che
$$\mathbb{P}(\{z>a\})=\textrm{area}(A)$$
con
$$A=\{(x,y)\in [0,1]\ :\ a<x<1-a,\ a<y<1-a,\ |x-y|>a\}\;.$$
E' ovvio che $\textrm{area}(A)=(1-3a)^2$ se $0\leq a\leq 1/3$ e $0$ altrimenti.
Dunque
$$F_z(a)=\mathbb{P}(\{z<a\})=(1-(1-3a)^2)\chi_{[0,1/3]}(a)$$
dove $\chi$ è la funzione caratteristica dell'intervallo indicato.
Quindi la densità di probabilità di $z$ è $f_z(a)=F_z'(a)=6(1-3a)\chi_{[0,1/3]}(a)$ e dunque
$$\mathbb{E}[z]=\int_0^{1/3}6a-18a^2 da=3[d^2-2d^3]_0^{1/3}=\dfrac{1}{9}\;.$$

[GimmyTomas]

Tento di dare una soluzione con idee elementari, che però richiede di calcolare l'area sotto un paio di parabole... È chiaro che il calcolo di quest'area in generale non è elementare (perché non si tratta nemmeno di segmenti parabolici, in modo da usare la formula di Archimede); poi non so, magari, nel caso specifico delle parabole, c'è una dimostrazione elementare di quanto vale l'area sotto di esse [edit: in realtà, ripensandoci, penso si possa tranquillamente fare con la formula di Archimede, sottraendo rette oblique ], in modo da rendere l'intera soluzione completamente elementare.

Chiamo $a$, $b$ i due numeri in $[0,1]$ individuati dai punti scelti a caso.
Piazziamo prima $a$ e poi $b$.
Innanzitutto, possiamo porre wlog $a\leq 1/2$, perché se così non fosse potremmo guardare il segmento al contrario.

Ora, analizziamo il caso in cui $b\leq a$ (la probabilità che ciò avvenga è $a$). In tal caso, il segmento più corto sarà sicuramente uno con estremo $b$: ci si riconduce dunque al problema del segmento più corto con un solo punto, che si vede facilmente che ha come soluzione un quarto della lunghezza del segmento. Dunque la lunghezza media (pesata dalla probabilità) è $a^2/4$.

Ora guardiamo cosa succede se $b>a$ (la probabilità che ciò avvenga è $1-a$). Distinguiamo due casi: $a\geq 1/3$ e $a<1/3$.
Se $a\geq 1/3$, notiamo che ancora una volta il segmento più corto avrà sicuramente come estremo $b$ e ci si riconduce ancora al caso con un punto. Stavolta la lunghezza media pesata è $(1-a)^2/4$.
Se invece $a<1/3$, poniamo, similmente a prima, wlog $b<(1+a)/2$. Se $b<2a$ (probabilità che avvenga: $\frac{a}{(1-a)/2}$, allora il segmento più corto è quello tra $a$ e $b$; se $b>2a$ (probabilità che avvenga: $\frac{1-3a}{(1-a)/2}$, invece, il segmento più corto è quello tra $0$ e $a$. Nel primo caso, la lunghezza media pesata è $(a/2)\cdot\frac{a}{(1-a)/2}$; nel secondo è $a\cdot \frac{(1-3a)/2}{(1-a)/2}$.

Ricapitolando:
- se $a\geq 1/3$, la lunghezza media è $a^2/4+(1-a)^2/4$;
- se $a< 1/3$, la lunghezza media è $a^2/4+(1-a)\left((a/2)\cdot\frac{a}{(1-a)/2}+a\cdot \frac{(1-3a)/2}{(1-a)/2}\right)=a^2/4+a(1-2a)$.

Ora dobbiamo mediare questi valori rispetto ad $a$. Questo si fa con la media integrale, cioè considerando l'area sottesa da queste due parabole con l'asse delle ascisse (rispettivamente negli intervalli $[1/3;1/2]$ e $[0; 1/3)$) e trovando l'altezza che dovrebbe avere un rettangolo di base uguale per avere quella stessa area.
Dunque il valore cercato è $$\frac{\displaystyle \int_0^{\frac{1}{3}}\left(\frac{a^2}{4}+a(1-2a)\right)da+\int_{\frac{1}{3}}^{\frac{1}{2}}\left(\frac{a^2}{4}+\frac{(1-a)^2}{4}\right)da}{1/2}=\frac{1}{9}.$$

[dario2994]

Vi lascio uno sketch di una dimostrazione contosa (e ben poco olimpica) del caso generale, assumo che l'intervallo in questione sia $(0,1)$.
Inoltre tutte le variabili saranno implicitamente vincolate ad essere positive.
Siano $X_1,\dots, X_n$ le variabili aleatorie in questione, allora vale questa lunga catena di uguaglianze (tutte giustificate o per simmetria o con cambio di variabili, lascio al lettore la scoperta delle simmetrie e dei cambi di variabili):
\[
\text{E}\left[\min_{i\not=j} |X_i-X_j|\right]=\int_{(0,1)^n} \min_{i\not=j}(|x_i-x_j|) d\bar{x} = n!\int_{0<x_1<\cdots<x_n<1} \min_i(x_{i+1}-x_i) d\bar{x} =
\]
\[
=n!\int_{y_1+\cdots+y_n\le 1} \min(y_1, \dots, y_n, 1-y_1-\cdots-y_n) d\bar{y}=
\]
\[
=n!(n+1)\int_0^{\frac1{n+1}}\int_{y_1+\cdots+y_{n-1}\le 1-2u\ \wedge\ y_i\ge u} u\ d\bar{y}\ du
=n!(n+1)\int_0^{\frac1{n+1}}\int_{z_1+\cdots+z_{n-1}\le 1-(n+1)u} u\ d\bar{z}\ du =
\]
\[
=n!(n+1)\cdot\text{m}\left(\{z_1+\cdots+z_{n-1}\le 1\}\right)\int_0^{\frac1{n+1}}u(1-(n+1)u)^{n-1}du
=n!(n+1)\frac1{(n-1)!}\frac1{n(n+1)^3}=\frac1{(n+1)^2}
\]

Se, dopo averci ragionato, qualche passaggio rimane oscuro non esitate a lamentarvene

Ho trovato il risultato abbastanza controintuitivo... mi sarei aspettato qualcosa di lineare ed invece è uscito qualcosa di quadratico. Sarebbe interessante (ma forse davvero troppo contoso) calcolare la varianza di $\min_{i\not=j}|X_i-X_j|$.

EDIT: In effetti la varianza si può calcolare esattamente come ho calcolato il valore atteso e vale (a meno di errori di conto)
\[
\text{Var}\left(\min_{i\not=j}|X_i-X_j|\right)=\frac{n}{(n+1)^4(n+2)}
\]
e se ci si pensa un attimo questo mostra che $(n+1)^2\min_{i\not=j}|X_i-X_j|$ non converge in legge alla costante $1$ come invece avremmo potuto sperare.

[Ido Bovski]

Sempre nel caso generale, qual è il valore atteso della lunghezza del $k$-esimo segmento più lungo?

Testo nascosto:

$\frac{1}{n+1}\left(\frac{1}{n+1}+\cdots+\frac{1}{k}\right)$