La moneta da un p
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
Re: La moneta da un p
Più che di "sensazione" parlerei di "congettura": la risposta è giusta, ma servirebbe la soluzione...
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"
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"
Re: La moneta da un p
Provo a lavorarci ancora; nel frattempo mi accontento di aver congetturato giustopanurgo ha scritto:Più che di "sensazione" parlerei di "congettura": la risposta è giusta, ma servirebbe la soluzione...
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
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
-
- Supervisore del sito
- Messaggi: 1747
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: La moneta da un p
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}}$
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
Gianfranco
Re: La moneta da un p
La dimostrazione si avvicina!
Se io mi trovassi ad utilizzare la parola "sequenza" penserei subito all'OEIS...
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"
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"
Re: La moneta da un p
Sono disposto a svelare l'arcano, se siete stufi di aspettare...
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"
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"
Re: La moneta da un p
Per me va bene
_________________
$\text { }$ciao ciao
E' la somma che fa il totale (Totò)
$\text { }$ciao ciao
E' la somma che fa il totale (Totò)
-
- Supervisore del sito
- Messaggi: 1747
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: La moneta da un p
OK, va bene anche per me.
Scrivo qui la formula che dovrebbe risolvere il problema.
Il problema è:
$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.
Scrivo qui la formula che dovrebbe risolvere il problema.
Il problema è:
La probabilità è: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.
$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
Gianfranco
Re: La moneta da un p
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.
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.
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$.
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
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
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).
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}$
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.
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$.
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
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
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).
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}$
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"
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"