Difficoltà in una tesina

[ninì2]

Mia nipote, che studia informatica (II anno), è impegnata in una tesina sulle comunicazioni. In un ambito laterale di questa ricerca si presenta la necessità di risolvere un problema probabilistico che è il seguente:
Da un luogo di un piano illimitato parte un punto che si muove in linea retta per segmenti $\Delta l$ (=passo) di lunghezza data.
Dopo il primo passo, il secondo avviene secondo una nuova direzione casuale ( ma entro l'angolo giro) angolata di $\phi_2$ a misurarsi dalla direzione del precedente tratto, e così di seguito .
Necessità calcolare: a) la probabilità che la traiettoria, che viene a generarsi, incontri se stessa per la prima volta dopo un $n$ dato di passi e, b) quanti passi sarebbero mediamente necessari, indipendentemente dal numero $n$ prefissato di passi, acciocché l'incontro avvenga.
Premetto che mia nipote ha chiesto a me di cercare la soluzione, magari aiutandomi con ricerche presso la biblioteca dell'università, a me poichè, nella mia lontana gioventù, ebbi ad occuparmi di calcolo delle probabilità. Per completezza aggiungo che la mancata risoluzione di questo problema "laterale" nuocerebbe poco al lavoro di mia nipote perchè potrebbe essere sostituito da altro più facile seppure meno elegante e preciso, ma il mio amor poprio non ne sarebbe soddisfatto .

[Gatto891]

Un paio di commenti e lascio l'esercizio a qualcuno più volenteroso (o ci torno passati gli esami):

1) Direzione casuale, in questo ambito, significa che l'angolo $phi_i$ ha una distribuzione uniforme su $[0, 2pi]$;

2) Le risposte ad (a) e (b) a occhio non dipendono dal passo $Deltal$ scelto.

[ninì2]

"Gatto89":
1) Direzione casuale, in questo ambito, significa che l'angolo $phi_i$ ha una distribuzione uniforme su $[0, 2pi]$;

2) Le risposte ad (a) e (b) a occhio non dipendono dal passo $Deltal$ scelto.

Quanto al punto 2 avevo anch'io tal sospetto, almeno per il piano euclideo, non più se questo problema, sicuramente non nuovo e gia risolto (se avessi avuto voglia di cercarlo in bibliotreca lo avrei trovato), non fosse euclideo, per esempio, la superficie di una sfera che, oltre tutto, è una superficie finita ma illimitata. Questa precisazione la faccio perchè ricordo di un problema analogo: quello di un cieco che, calato in un deserto di area limitata entro cui è circoscritta una sub area, che rispetto all'altra ha un rapporto dato (+ altre precisazioni che non ricordo), abbia la necessità di cercare la sub-area sotto condizioni fra cui:

-sa di essere fuori dalla sub area
-ha la possibilità di riconoscere i confini sia del deserto che la sub artea da cercare
-non ha la possibilità di governare la sua traiettoria di percorso

[cenzo1]

Sono d'accordo con i commenti di Gatto89 e con la successiva precisazione di ninì (nel caso sferico il passo conta).
Mi limito al caso piano.
Il problema mi sembra alquanto difficile (per me).
Direi che l'incontro può avvenire a partire dal terzo passo ($n=3$), a meno di un evento quasi impossibile (il secondo passo che ricalca esattamente il primo e ci riporta nel punto di partenza).
Per $n=3$ sono riuscito ad ottenere la probabilità esatta $P=1/12$ (ragionando sui triangoli isosceli...)
Per $n>3$ è già troppo complicato... allora ho fatto una simulazione (100000 prove), da cui risulta un numero medio di passi (per il primo incrocio) circa uguale a $9$ e la seguente distribuzione di frequenza.

[ninì2]

Credo che la soluzione iniziata da cenzo sia quella giusta; il fatto è proprio che dopo il terzo passo l'analisi si complica. Non è detto che, studiando bene il processo iniziato da cenzo, si intravvedano delle scorciatoie, una di queste potrebbe essere, per esempio la scoperta di un eventuale esistenza di un algoritmo iterativo.
Sarei molto grato a Cenzo se dicesse qualcosa su come ha fatto la simulazione,
Grazie.

[ninì2]

"cenzo":).
Direi che l'incontro può avvenire a partire dal terzo passo ($n=3$), a meno di un evento quasi impossibile (il secondo passo che ricalca esattamente il primo e ci riporta nel punto di partenza).
Per $n=3$ sono riuscito ad ottenere la probabilità esatta $P=1/12$ (ragionando sui triangoli isosceli...)
Per $n>3$ è già troppo complicato...

Rileggendo Cenzo sul caso semplice dei primi tre passi, col quale Cenzo calcola la probabilita dell'intersezione pari a 1/12, dico, che rifacendo il calcolo sullo studiodei triangoli equilateri, ho calcolato p(3)= 1/18. Ma facendo bene i conti -nel senso di considerare che, per $\phi_2<60^o$, si vede che la probabilità che il terzo passo incontri la linea del primo è, in media un po' più alta (media fatta integrando $\phi_2$ tra 0 e 60 gradi), la probabilità sale da 1/18 a 2/27. Tuttavia, applicando il così detto metodo di Montecarlo mediante l'uso del foglio elettronico, la probabilità pratica delle frequenze è di 0.1854194 (+-)0.0025272 sulla base di una campionatura di 31000 prove; sembra che Cenzo ed io ci sbagliamo.

[cenzo1]

"ninì":sembra che Cenzo ed io ci sbagliamo.

Il tuo risultato teorico è $2/27\approx 0.074074$
Il tuo risultato da simulazione è $0.1854194$
C' è una forte differenza tra i due risultati, quindi sei daccordo che almeno uno dei due ha una falla da qualche parte.

Il mio risultato terorico è $1/12\approx 0.08333$
Il mio risultato da simulazione (come si vede anche dal grafico - un po' superiore all'$8%$) è $0.08288$
I due risultati sono molto prossimi. Ciò mi induce a ritenere molto improbabile che sia un puro caso, frutto di due errori indipendenti (uno teorico e uno di simulazione) che portano a valori così vicini. Concordi ?

[ninì2]

"cenzo":[quote="ninì"]sembra che Cenzo ed io ci sbagliamo.

Il tuo risultato teorico è $2/27\approx 0.074074$
Il tuo risultato da simulazione è $0.1854194$
C' è una forte differenza tra i due risultati, quindi sei daccordo che almeno uno dei due ha una falla da qualche parte.

Il mio risultato terorico è $1/12\approx 0.08333$
Il mio risultato da simulazione (come si vede anche dal grafico - un po' superiore all'$8%$) è $0.08288$
I due risultati sono molto prossimi. Ciò mi induce a ritenere molto improbabile che sia un puro caso, frutto di due errori indipendenti (uno teorico e uno di simulazione) che portano a valori così vicini. Concordi ?[/quote]
Dopo una verifica dei miei conteggi convengo col tuo risultato di $p_3=1/12$ .
Quanto alla mia prova di simulazione, credo proprio di doverla rivedere, visto che tradisce completamente il dato teorico.
A tempo perso proverò a calcolare $p_4$ visto che sono agli arresti domiciliari per un'ingessatura ad un piede a seguito di una caduta. Tempo ne ho .

[cenzo1]

"ninì":Dopo una verifica dei miei conteggi convengo col tuo risultato di $p_3=1/12$

Ottimo, allora adesso abbiamo gli stessi risultati teorici

"ninì":Quanto alla mia prova di simulazione, credo proprio di doverla rivedere, visto che tradisce completamente il dato teorico.
A tempo perso proverò a calcolare $p_4$ visto che sono agli arresti domiciliari per un'ingessatura ad un piede a seguito di una caduta. Tempo ne ho .

Per quanto riguarda la simulazione l'ho realizzata in Excel. Per il terzo passo ho cercato l'intersezione della corrispondente retta con la retta del primo passo. Ho quindi verificato se il punto intersezione appartiene ad entrambi i segmenti, controllando che la sua ascissa fosse compresa tra gli estremi del primo segmento e anche tra gli estremi del terzo segmento.
Per i passi successivi le cose sono le stesse, ma vanno ripetute più volte. Per il passo $k$ occorre trovare le intersezioni con tutti i passi da $1$ a $k-2$ e controllare se appartengono alla relativa coppia di segmenti. Pensa che per $k=30$ occorre determinare $28$ intersezioni... insomma il foglio di calcolo conviene srutturarlo in modo da trascinare le formule e risparmiare un po' di fatica.
Poi occorre determinare il primo passo a cui avviene l'intersezione. Ho utilizzato dei flag (0/1) che segnalano l'intersezione ad un certo passo.
Ho utilizzato la funzione cerca.vert per determinare il primo passo in cui c'è il flag 1.
Poi il tutto è stato ripetuto per 100000 prove mediante una semplice macro scritta in VBA.

Se durante questo "domicilio forzato" riesci a determinare $p_4$ teorico e ancora meglio quell'eventuale algoritmo ricorsivo di cui parlavi, tienici aggiornati perchè sarebbe molto interessante.

Ciao e buona guarigione

[ninì2]

"cenzo":Per quanto riguarda la simulazione l'ho realizzata in Excel. Per il terzo passo ho cercato l'intersezione della corrispondente retta con la retta del primo passo. Ho quindi verificato se il punto intersezione appartiene ad entrambi i segmenti, controllando che la sua ascissa fosse compresa tra gli estremi del primo segmento e anche tra gli estremi del terzo segmento.
Per i passi successivi le cose sono le stesse, ma vanno ripetute più volte. Per il passo $k$ occorre trovare le intersezioni con tutti i passi da $1$ a $k-2$ e controllare se appartengono alla relativa coppia di segmenti. Pensa che per $k=30$ occorre determinare $28$ intersezioni... insomma il foglio di calcolo conviene srutturarlo in modo da trascinare le formule e risparmiare un po' di fatica.
Poi occorre determinare il primo passo a cui avviene l'intersezione. Ho utilizzato dei flag (0/1) che segnalano l'intersezione ad un certo passo.
Ho utilizzato la funzione cerca.vert per determinare il primo passo in cui c'è il flag 1.
Poi il tutto è stato ripetuto per 100000 prove mediante una semplice macro scritta in VBA.

Con ritardo leggo la tua risposta e ringrazio per i lumi datimi in merito al programma excel usato nella tua simulazione. Nel frattempo ho cercato anch'io la via della simulazione: prima usando il vecchio linguaggio QBasic e, poi, ripensandoci, usando excel. Ho utilizzato il tuo stesso principio ma non proprio la stessa tecnica che, comunque riconosco che è inferiore alla tua ed i risultati non mi convincono. Ci ritornerò e ti terrò informato .