La moneta da un p

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: La moneta da un p

Messaggio da panurgo »

Più che di "sensazione" parlerei di "congettura": la risposta è giusta, ma servirebbe la soluzione... :twisted:
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: La moneta da un p

Messaggio da franco »

panurgo ha scritto:Più che di "sensazione" parlerei di "congettura": la risposta è giusta, ma servirebbe la soluzione... :twisted:
Provo a lavorarci ancora; nel frattempo mi accontento di aver congetturato giusto :D :D
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: La moneta da un p

Messaggio da Gianfranco »

Mi sono concentrato su questo sotto-problema:
Se lancio una moneta 2, 4, 6, 8, ... 2n volte
quanti sono i casi possibili in cui il numero delle teste è uguale al numero delle croci SENZA che lo sia mai stato prima?
Ho ottenuto questa sequenza:
2, 2, 4, 10, 28, 84, 264, etc
che si ricava da questa formula:
$\frac{\left( 2 n\right) !}{\left( 2 n-1\right) \, {{n!}^{2}}}$

Se questa formula è esatta, dovrebbe essere facile trovarne una per il calcolo della probabilità totale facendo una sommatoria con infiniti termini.

Nota che se si lancia la moneta 2n volte:
a) le sequenze possibili di T e C sono $2^{2n}$
b) le sequenze che hanno un numero uguale di teste e croci sono $\frac{\left( 2 n\right) !} {{n!}^{2}}$
Pace e bene a tutti.
Gianfranco

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: La moneta da un p

Messaggio da panurgo »

La dimostrazione si avvicina! :D

Se io mi trovassi ad utilizzare la parola "sequenza" penserei subito all'OEIS...
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: La moneta da un p

Messaggio da panurgo »

Sono disposto a svelare l'arcano, se siete stufi di aspettare... :roll:
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: La moneta da un p

Messaggio da Pasquale »

Per me va bene :shock:
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: La moneta da un p

Messaggio da Gianfranco »

OK, va bene anche per me.
Scrivo qui la formula che dovrebbe risolvere il problema.

Il problema è:
La probabilità di ottenere testa lanciando una certa moneta è p: calcolare la probabilità che, ad un certo punto, il numero delle teste uscite sia uguale a quello delle croci.
La probabilità è:
$prob=\sum_{k=1}^{\infty }{\left. \frac{\left( 2 k\right) !}{\left( 2 k-1\right) \, {{k!}^{2}}}\right.} {{\left( 1-p\right) }^{k}}\, {{p}^{k}}$
La sommatoria si riferisce a 2, 4, 6, ...2k lanci
Salvo errori od omissioni.
Pace e bene a tutti.
Gianfranco

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: La moneta da un p

Messaggio da panurgo »

Consideriamo una sequenza generica di lanci che contenga un uguale numero di teste e di croci: tale sequenza può essere rappresentata mediante un cammino nel quale ogni testa corrisponda ad un passo verso l’alto e ogni croce corrisponda ad un passo verso il basso.
dyckpath01_480x160.png
dyckpath01_480x160.png (4.95 KiB) Visto 6039 volte
Evidentemente, se facciamo tanti passi verso l’alto quanti ne facciamo verso il basso, alla fine ci troveremo al livello di partenza. Inoltre, dato che assumiamo che la probabilità di fare un passo verso l’alto (basso) non dipenda dal livello al quale ci troviamo, la probabilità di un cammino dipende solo dagli stati iniziale e finale e non dall’ordine con cui noi andiamo in alto e in basso: tutti i cammini che iniziano e finiscono in due punti dati hanno la stessa probabilità, non ci resta che contarli.
Poiché non ammettiamo cammini che tornino alla riga di zero che una e una sola volta dovremo considerare tutti i cammini che, al primo passo, salgano alla riga del $+1$ (scendano al $-1$), che rimangano per $2n$ passi sopra la riga del $+1$ (sotto al $–1$) e che scendano (salgano) alla riga dello zero all’ultimo passo.
dyckpath02_480x480.png
dyckpath02_480x480.png (14.06 KiB) Visto 6039 volte
In figura è rappresentato il caso $n = 4$: dobbiamo contare tutti i cammini che sono in ciascuna dei due mezzi reticoli quadrati o meglio, contare i cammini di mezzo reticolo e moltiplicarli per $2$.
dyckpath03_480x120.png
dyckpath03_480x120.png (5.47 KiB) Visto 6039 volte
Ci sono: un cammino per $n = 0$, uno per $n = 1$, due per $n = 2$, cinque per $n = 3$ ecc.
Andiamo sull’OEIS e cerchiamo $1, 1, 2, 5$: la prima sequenza che ci viene mostrata è la sequenza dei numeri di Catalan ($C_n$). Vi consiglio di dare almeno un’occhiata alla bibliografia per vedere quanti sono gli oggetti che sono contati da $C_n$: il secondo della lista è il numero di cammini (Dyck path) che ci interessa.
Troviamo immediatamente la formula, $C_n=\frac1{n+1}{2n \choose n}$, e la Funzione generatrice, $\sum_{n=0}^\infty C_n x^n=\frac{1-\sqrt{1-4x}}{2x}$.
La dimostrazione che $C_n$ conta i nostri cammini è nel contempo semplice e bella, ragion per cui ve la propino.
Di tutti i cammini di un reticolo $n\times n$ consideriamo validi quelli che non scendono sotto alla linea che lo divide a metà. Per esempio, nella figura seguente, è mostato un cammino vietato
dyckpath04_480x480.png
dyckpath04_480x480.png (11.15 KiB) Visto 6039 volte
Il trucco consiste nel riflettere la parte del cammino successiva al primo passo vietato sulla linea immediatamente inferiore alla linea mediana: in questo modo al cammino sul reticolo $n\times n$ (in nero) viene associato un cammino su un reticolo $\left(n-1\right)\times\left(n+1\right)$ (in rosso); $\left(n-1\right)\times\left(n+1\right)$ perché abbiamo appena fatto un passo in giù in più dei passi in su quindi ci rimane un passo in su in più da fare e, dato che la riflessione scambia giù con su, ci troviamo con due passi in giù eccedenti.
Viceversa, se prendiamo un percorso sul reticolo $\left(n-1\right)\times\left(n+1\right)$ e riflettiamo la parte successiva al primo passo che viola la linea mediana del reticolo $n\times n$, otteniamo un cammino vietato sul reticolo $n\times n$ stesso
dyckpath05_480x480.png
dyckpath05_480x480.png (11.55 KiB) Visto 6039 volte
Siamo sicuri che ogni cammino sul reticolo $\left(n-1\right)\times\left(n+1\right)$ violi la linea mediana del reticolo $n\times n$ perché l’ultimo punto del reticolo giace due livelli al di sotto di essa quindi un cammino su questo reticolo deve attraversare la linea sotto quella mediana e il corrispondente cammino sul reticolo $n\times n$ deve toccarla.
Quella che abbiamo trovato è una biiezione, una corrispondenza biunivoca, tra i cammini del reticolo $\left(n-1\right)\times\left(n+1\right)$ e i cammini vietati del reticolo $n\times n$, per cui

$\displaystyle C_n={2n \choose n}-{2n \choose n-1}=\frac{\left(2n\right)!}{n!n!}- \frac{\left(2n\right)!}{\left(n-1\right)!\left(n+1\right)!}=\frac{\left(2n\right)!}{n!\left(n+1\right)!}\left[\left(n+1\right)-n\right]=\frac1{n+1}{2n \choose n}$

QED

Nell’esempio di prima, $C_n=\frac15{8\choose 4}=14$: se volete potete divertirvi a disegnarli, oppure accontentarvi di questa illustrazione (trovata sempre su OEIS).
CatalanSpaceInvaders.gif
CatalanSpaceInvaders.gif (8.84 KiB) Visto 6039 volte
Dopo aver contato i cammini siamo in grado di assegnare la probabilità di finire in $2n+2$ passi

$\displaystyle Pr\left(0\wedge n\middle|\top\right)=2C_n p^{n+1}\left(1-p\right)^{n+1}$

e di calcolare la probabilità totale

$\displaystyle Pr\left(0\middle|\top\right)=\sum_{n=0}^\infty{2C_n p^{n+1}\left(1-p\right)^{n+1}}$

approfittando della Funzione generatrice (trovata su OEIS)

$\displaystyle \sum_{n=0}^\infty{C_n x^n}=1+x+2x^2+5x^3+14x^4+\cdots=\frac{1-\sqrt{1-4x}}{2x}$

da cui ricaviamo

$\displaystyle 2x\sum_{n=0}^\infty{C_n x^n}=\sum_{n=0}^\infty{2C_n x^{n+1}}=1-\sqrt{1-4x}$

e, posto $x=p\left(1-p\right)$, rimaneggiamo il tutto per ottenere

$\displaystyle \sum_{n=0}^\infty{2C_n p^{n+1}\left(1-p\right)^{n+1}}=1-\sqrt{\left(1-2p\right)^2}=1-\left|1-2p\right|=\left\{\begin{array}{llCC}2p & p<\frac12 \\ 2\left(1-p\right) & p>\frac12\end{array}\right.$

La probabilità di terminare sulla linea dello zero è nulla se $p=0$ o $p=1$, cioè se esce sempre testa o sempre croce, ed è massima quando $p=1-p$, come deve essere.

A Gianfranco dico che la mia sommatoria comincia da zero perché i passi che vanno da $0$ a $\pm 1$ e da $\pm 1$ a $0$ sono fuori dal conteggio di $C_n$ e la mia probabilità è elevata a $n+1$.

Sempre come curiosità osserviamo che i cammini di Dyck corrispondono ad una mezza binomiale cosicchè al triangolo binomiale

$\begin{array}{cC}
&&&&&&&& 1 \\
&&&&&&& 1 && 1 \\
&&&&&& 1 && 2 && 1 \\
&&&&& 1 && 3 && 3 && 1 \\
&&&& 1 && 4 && 6 && 4 && 1 \\
&&& 1 && 5 && 10 && 10 && 5 && 1 \\
&&1 && 6 && 15 && 20 && 15 && 6 && 1 \\
&1 && 7 && 21 && 35 && 35 && 21 && 7 && 1 \\
1 && 8 && 28 && 56 && 70 && 56 && 28 && 8 && 1
\end{array}$

corrisponde il triangolo di Dyck

$\begin{array}{cC}
1 \\
& 1 \\
1 && 1 \\
& 2 && 1 \\
2 && 3 && 1 \\
& 5 && 4 && 1 \\
5 && 9 && 5 && 1 \\
& 14 && 14 && 6 && 1 \\
14 && 28 && 20 && 7 && 1
\end{array}$

:wink:
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Rispondi