Newsgroup: it.hobby.enigmi
Titolo: (MA) Uccelli sul filo

Su un filo di lunghezza finita si posano N uccelli in posizione casuale
(uniforme).
Supponiamo che ogni uccello guardi verso quello che si trova a lui piů
vicino.
1) Qual č la prob. che un uccello preso a caso stia guardando un altro
uccello che a sua volta lo stia guardando?
2) Per ciascun uccello immaginiamo di colorare la porzione di filo fra esso
e l'uccello piů vicino.
Per N->infinito, complessivamente quale percentuale del filo risulta
colorata? (Se due uccelli consecutivi sono mutuamente i piů vicini,
considerare colorata una volta sola tale porzione di filo)
Ciao
Andrea

 considerare colorata una volta sola tale porzione di filo)
spoilero la prima, alla seconda ci devo pensare un po'
.
.
.
.
.
.
.
.
.
.
.
.
2/3
Chiamiamo "vicinissimo" il più vicino tra i due vicini di ogni
uccello.
Consideriamo un uccello X e le sue due coppie di vicini y più prossimi
a destra e sinistra
..___y_____y_____X_____y_____y___..
     |  A  |  B  |  C  |  D  |
Le distanze A,B,C,D sono indipendenti e ugualmente distribuite, quindi
non c'è ragione di credere che una di queste sia maggiore dell'altra.
Se proviamo ad ordinarle avremo 24 casi equiprobabili
A<B<C<D
A<B<D<C
A<C<B<D
..
I casi in cui X si ritrova ad essere il vicinissimo del suo
vicinissimo sono quelli in cui B è minore sia di C che di A, oppure C
è minore di B e D. Se li contiamo scopriamo che sono 16 casi.
Ma si fa prima a contare i casi contrari, ovvero quelli in cui X non è
il il vicinissimo del suo vicinissimo. Questo avviene se A<B<C oppure
D<C<B. Ci sono 4 casi del primo tipo, corrispondenti alle diverse
posizioni di D (A<B<C<D, A<B<D<C, A<D<B<C, D<A<B<C), e altri 4
simmetrici per D<C<B.
Quindi, in conclusione, in 2 casi su 3 un uccello scelto a caso è il
vicinissimo del suo vicinissimo.
--
Ciao, Silv:o)

 Ciao, Silv:o)
ciao
paolo

 considerare colorata una volta sola tale porzione di filo)
A questo ci sto pensando...
Maurizio

 quali il tuo ragionamento non è applicabile).
E da dove credi che sia partito? ;)
Comunque ho cercato in rete, cercando neighbor nearest problem ed ho trovato
argomentazioni probabilistiche ed analitiche che confermano i 2/3
--
Ciao, Silv:o)

 considerare colorata una volta sola tale porzione di filo)
Per il secondo quesito ho provato con due ragionamenti diversi, che mi danno
risultati ... diversi. Segno evidente che almeno uno dei due è sbagliato
(non escludo che siano errati entrambi)
:-)
Suppongo che ciascun uccello provveda (in sequenza) a colorare il segmento
verso cui guarda, se questo non è già colorato.
Primo ragionamento:
Gli uccelli procedono in ordine da sinistra a destra. Ciascun uccello colora
il suo segmanto se:
guarda verso destra (p=1/2)
oppure se
guarda verso sinistra (p=1/2) e l'uccello che lo precede guarda pure verso
sinistra (p=1/2)
complessivamente la probabilità che un uccello colori un segmento risulta
3/4, e 3/4 dovrebbe essere la percentuale di filo colorata.
Forse però questo ragionamento trascura il fatto che i segmenti bianchi
dovrebbero mediamente essere più lunghi di queli colorati.
Secondo ragionamento.
Sia S=N-1 il numero di segmenti, di lunghezza media 1/S (considerata
unitaria la lunghezza del filo)
Gli uccelli procedono in un ordine qualsiasi, per esempio a caso, o secondo
l'ordine alfabetico dei rispettivi codici fiscali (ammesso che gli uccelli
ne abbiano uno).
Un generico uccello si trova ad operare quando un tratto A di filo è stato
già colorato, mentre un tratto B=1-A è ancora bianco. Quindi ha una
probabilità pari a B di guardare verso un tratto bianco, e con probabilità B
colora il suo segmento lungo 1/S. Ciò equivale (mi pare) a dire che
mediamente colora un tratto lungo B/S. Ad operazione compiuta il tratto
bianco risulta B-B/S, ossia B*(S-1)/S. Ad ogni operazione quindi la
lunghezza del tratto bianco si riduce per un fattore (minore di uno)
(S-1)/S.
Per N=S+1 operazioni (N uccelli) il tratto bianco (inizialmente uguale ad1)
diventa quindi ((S-1)/S)^(S+1) ossia
((N-2)/(N-1))^N
Al tendere di N ad infinito questa espressione tende al valore 0.367879...
che mi sembra essere l'inverso del numero e.
La percentuale colorata sarebbe dunque 1-1/e=0.632121...
s.e.o.o.
ciao
paolo

 considerare colorata una volta sola tale porzione di filo)
.
.
.
.
.
.
.
.
.
secondo me e le mie simulazioni, 7/18
Vediamo un po' di lunghezze medie.
Gli intervalli generici sono mediamente lunghi 1/N
Gli intervalli tra un uccello e il suo vicinissimo valgono mediamente
1/2N. Si può dimostrare, è il minimo tra due distanze distribuite con
densità x ed ha densità doppia.
Di conseguenza la distanza media tra un uccello e il suo lontanissimo
vale 3/2N, ma non ce ne frega niente.
La distanza media tra due uccelli mutuamente vicinissimi vale 1/3N.
Questo non sono per ora riuscito a dimostrarlo, ma mio fido della
simulazione.
Abbiamo già visto che 2 volte su 3 un uccello è il vicinissimo del suo
vicinissimo.
Ricapitoliamo: ogni uccello dipinge un tratto mediamente lungo 1/2N
(totale vernice usata per un metro di filo: N*1/2N =1/2 metro), però
3/2 di loro dipingono un tratto lungo 1/3N già di competenza del loro
vicinissimo (totale vernice sovrapposta: N*2/3*1/3N=2/9 di metro). Il
tratto dipinto vale quindi 1/2-2/9=7/18
Ciao, Silv:o)

 vale quindi 1/2-2/9=7/18
purtroppo fa 5/18 :(((
devo trovare l'errore nel ragionamento, perché la simulazione finisce
sempre pochissimo sotto al 39 per cento.
Silv:o)

 di metro).
E no! se tolgo tutto questo tratto svernicio doppiamente i tratti
doppiamente verniciati.
Invece devo cancellare solo la metà di questa vernice! Uno dei due
deve pur fare il lavoro!
Quindi il tratto da cancellare vale 2/3*1/3*1/2 = 1/9 e i conti
tornano!
Ciao, Silv:o)

 dovrebbero mediamente essere più lunghi di queli colorati.
Infatti! Ma non mi sarei mai immaginato discrepanze così importanti
rispetto alla media a priori. Mediamente i due tratti adiacenti
ciascun uccello sono lunghi 1/2 e 3/2 il che mi perplime abbastanza. I
tratti colorati solo da un uccello risultano mediamente lunghi 5/6,
quelli colorati da entrambi addirittura *solo* 1/3, quelli non
colorati per niente sono lunghi in media 11/6. Mah! Ci sarà un modo
facile di dimostrare tutti questi numeri?
Ciao, Silv:o)

 dimostrare tutti questi numeri?
Facile forse no, ma si può fare con delle integrazioni multiple.
Fotunatamente il risultato non dipende dal numero degli uccelli (se
trascuriamo i bordi), sicché ci si può limitare a considerare 4 uccelli;
inoltre per simmetria possiamo limitarci a prendere le coordinate degli
uccelli in ordine:
0 < x1 < x2 < x3 < x4 < 1.
La cosa più complicata è quella di tradurre condizioni come 
x3 - x2 > x2 - x1, ecc.
nei limiti d'intergrazione appropriati, però con un po' di buona volontà
ci si riesce. Si trovano allora direttamente le frazioni di filo
colorate:
0 volte:  11/18
1 volta:   5/18
2 volte:   1/9
sicché la frazione totale di filo colorato è:
5/18 + 1/9 = 7/18,
proprio come hai trovato tu.
Inoltre si trova che è equiprobabile che un tratto di filo sia colorato
0, 1 o 2 volte, il che porta, combinato con i risultati dati sopra, alle
lunghezze medie da te riferite.
Maurizio

 [cut]
Perdonami, ma ho un dubbio.
Se estraggo n numeri casuali x tra 0 e 1,
poi li ordino, infine chiamo dx le (n-1) differenze,
mi pare di ricordare che esse abbiano distribuzione 
poissoniana, o qualcosa del genere, ma non uniforme.
Saluti
Alessandro

 poissoniana, o qualcosa del genere, ma non uniforme.
Hai ragione: avevo detto una sciocchezza. Il motivo per cui la cosa
funziona è quello che ha detto Silvio: basta sapere che le dx hanno la
stessa distribuzione, che sia uniforme non importa.
Lo stesso risultato si ritrova anche calcolando gli opportuni integrali,
come ho accennato nell'altro messaggio.
Maurizio