Lunghezza del segmento più corto

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Pigkappa
Messaggi: 1206
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Lunghezza del segmento più corto

Messaggio da Pigkappa » 23 ott 2015, 19:25

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?

Avatar utente
karlosson_sul_tetto
Messaggi: 1430
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Lunghezza del segmento più corto

Messaggio da karlosson_sul_tetto » 25 ott 2015, 15:56

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 :lol: )

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}$.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Pigkappa
Messaggi: 1206
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Re: Lunghezza del segmento più corto

Messaggio da Pigkappa » 25 ott 2015, 21:22

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

Pigkappa
Messaggi: 1206
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Re: Lunghezza del segmento più corto

Messaggio da Pigkappa » 25 ott 2015, 22:39

karlosson_sul_tetto ha scritto: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]

Avatar utente
Lasker
Messaggi: 329
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: Lunghezza del segmento più corto

Messaggio da Lasker » 25 ott 2015, 23:56

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.
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!

Avatar utente
Troleito br00tal
Messaggi: 677
Iscritto il: 16 mag 2012, 22:25

Re: Lunghezza del segmento più corto

Messaggio da Troleito br00tal » 26 ott 2015, 01:29

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
Messaggi: 1206
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Re: Lunghezza del segmento più corto

Messaggio da Pigkappa » 26 ott 2015, 10:02

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 :D

EvaristeG
Site Admin
Messaggi: 4502
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Lunghezza del segmento più corto

Messaggio da EvaristeG » 26 ott 2015, 14:32

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
Messaggi: 55
Iscritto il: 11 giu 2013, 15:28
Località: Benevento — Pisa

Re: Lunghezza del segmento più corto

Messaggio da GimmyTomas » 27 ott 2015, 02:05

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
Messaggi: 1426
Iscritto il: 10 dic 2008, 21:30

Re: Lunghezza del segmento più corto

Messaggio da dario2994 » 27 ott 2015, 16:25

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 :wink:

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.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Ido Bovski
Messaggi: 232
Iscritto il: 07 mag 2012, 11:51

Re: Lunghezza del segmento più corto

Messaggio da Ido Bovski » 28 ott 2015, 22:41

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)$

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti