Probabilità [elementare], raggiungere $n$ con una moneta
E' già capitato nel forum, quindi nel caso doveste trovarlo, vietato scopiazzare. 
Livello: tecnicamente, anche liceo se si è in gamba e si sono viste le basi di mat. discreta. Serve ben poco.
Un giocatore esegue infiniti lanci successivi di una moneta.
Ad ogni lancio, le probabilità che escano testa o croce sono entrambe uguali ad [tex]$1/2$[/tex].
Il giocatore parte dal punteggio zero e guadagna 2 punti ogni volta che esce croce ed 1 punto ogni volta che esce testa.
Per ogni [tex]$k \geq 1$[/tex], sia [tex]$x_k$[/tex] il punteggio ottenuto dal giocatore dopo [tex]$k$[/tex] lanci.
Dimostrare che, per ogni [tex]$n \geq 1$[/tex], la probabilità che esista un intero $k$ per cui $x_k = n$ è pari a
[tex]$\frac{2}{3}+\frac{(-1)^n}{3\cdot 2^n}$[/tex]
Buon lavoro!
Livello: tecnicamente, anche liceo se si è in gamba e si sono viste le basi di mat. discreta. Serve ben poco.
Un giocatore esegue infiniti lanci successivi di una moneta.
Ad ogni lancio, le probabilità che escano testa o croce sono entrambe uguali ad [tex]$1/2$[/tex].
Il giocatore parte dal punteggio zero e guadagna 2 punti ogni volta che esce croce ed 1 punto ogni volta che esce testa.
Per ogni [tex]$k \geq 1$[/tex], sia [tex]$x_k$[/tex] il punteggio ottenuto dal giocatore dopo [tex]$k$[/tex] lanci.
Dimostrare che, per ogni [tex]$n \geq 1$[/tex], la probabilità che esista un intero $k$ per cui $x_k = n$ è pari a
[tex]$\frac{2}{3}+\frac{(-1)^n}{3\cdot 2^n}$[/tex]
Buon lavoro!
Risposte
Questo problema, per informazione, è stato dato ad un esonero (1° anno) di un corso dell'Università di Pisa, cdl in Matematica.
Il corso era di Aritmetica, quindi di probabilistico non c'è poi così tanto.
Insomma, ragazzetti del primo anno, non battete la fiacca e pensateci
Il corso era di Aritmetica, quindi di probabilistico non c'è poi così tanto.
Insomma, ragazzetti del primo anno, non battete la fiacca e pensateci
io sono arrivato a ragionare qui: il punteggio deve essere per forza :
k≤ Xk≤2k
in cui k è il punteggio minimo e 2k è il punteggio massimo
inoltre posso dire che, siccome abbiamo la stessa probabilità che esca testa o croce si può tenere come punteggio medio:
Xk= 3\2 k.
per ora i miei ragionamenti mi portano qui (sono di quarta superiore)
ora posso aggiungere un' altra parte:
siccome x_k=n allora:
k≤n≤2k
quindi
{k≤n
{2k≥n --> k ≥n\2
quindi i valori di k per cui è possibile fare quel determinato punteggio sono:
n\2≤ k ≤ n
si puo generalizzare questo procedimento
n = 2C + T (C,T rispettivamente il numero di croci e teste uscite in k lanci)
siccome k = T + C allora
n = 2C + k - C = C + k
da cui si ricava che C = n - k
cioè il numero di volte che esca croce necessario per ottenere n su k lanci
per cui fissato k, la probabilita di fare n è:
p = (1/2)^k C(k, n-k)
C( , ) indica le combinazioni semplici
quindi la probabilita è
∑ (1/2)^k C(k, n-k) (sommatoria che va da n/2 a n, se n è dispari si parte dall'intero successivo) .... fino a qui tutti gli esempi che ho potuto fare mi danno i risultati in accordo con la formula da te scritta.
Per correttezza voglio dire che mi sono fatto aiutare, non è quasi per niente merito merito mio... comunque lo trovo un bel problemino, capace di scacciare via la noia di questi giorni.
intanto continuo a cercare la soluzione finale
k≤ Xk≤2k
in cui k è il punteggio minimo e 2k è il punteggio massimo
inoltre posso dire che, siccome abbiamo la stessa probabilità che esca testa o croce si può tenere come punteggio medio:
Xk= 3\2 k.
per ora i miei ragionamenti mi portano qui (sono di quarta superiore)
ora posso aggiungere un' altra parte:
siccome x_k=n allora:
k≤n≤2k
quindi
{k≤n
{2k≥n --> k ≥n\2
quindi i valori di k per cui è possibile fare quel determinato punteggio sono:
n\2≤ k ≤ n
si puo generalizzare questo procedimento
n = 2C + T (C,T rispettivamente il numero di croci e teste uscite in k lanci)
siccome k = T + C allora
n = 2C + k - C = C + k
da cui si ricava che C = n - k
cioè il numero di volte che esca croce necessario per ottenere n su k lanci
per cui fissato k, la probabilita di fare n è:
p = (1/2)^k C(k, n-k)
C( , ) indica le combinazioni semplici
quindi la probabilita è
∑ (1/2)^k C(k, n-k) (sommatoria che va da n/2 a n, se n è dispari si parte dall'intero successivo) .... fino a qui tutti gli esempi che ho potuto fare mi danno i risultati in accordo con la formula da te scritta.
Per correttezza voglio dire che mi sono fatto aiutare, non è quasi per niente merito merito mio... comunque lo trovo un bel problemino, capace di scacciare via la noia di questi giorni.
intanto continuo a cercare la soluzione finale
credo di esserci riuscito, e ripeto che non è tutto merito mio.
Per induzione:
si verifica che le due formule siano uguali per n = 1 e per n = 2
per n = 1 viene
(1/2)^1 C(1, 1-1) = 1/2 C(1,0) = 1/2
2/3 + 1/3(-1/2)^1 = 2/3 - 1/6 = 1/2
per n = 2 viene
∑[1,2] (1/2)^k C(k, 2-k) = 1/2 + 1/4 = 3/4
2/3 + 1/3(-1/2)^2 = 3/4
a questo punto si assume che valgano queste due uguaglianze:
∑[n/2, n] (1/2)^k C(k, n-k) = 2/3 + 1/3(-1/2)^n
∑[(n-1)/2, n-1] (1/2)^k C(k, n-1-k) = 2/3 + 1/3(-1/2)^(n-1)
se l'uguaglianza è vera allora vale anche:
∑[(n+1)/2, n+1] (1/2)^k C(k, n+1-k) = 2/3 + 1/3(-1/2)^(n+1)
infatti in questo modo siccome l'uguaglianza vale per i primi due valori di n allora posso estendere l'uguaglianza per tutti i valori di n successivi
∑[(n+1)/2, n+1] (1/2)^k C(k, n+1-k) =
faccio un cambio di indice k = k-1
∑[n/2, n] (1/2)^(k+1) C(k+1, n-k) =
poi sfrutto una proprieta del coefficiente binomiale (vedi fonti):
∑[n/2, n] (1/2)^(k+1) [ C(k, n-k) + C(k,n-1-k) ] =
1/2 ∑[n/2, n] (1/2)^k C(k, n-k) + 1/2 ∑[n/2, n] (1/2)^k C(k,n-1-k) =
1/2 (2/3 + 1/3(-1/2)^n) + 1/2 ∑[n/2, n] (1/2)^k C(k,n-1-k) =
nella sommatoria rimasta, deve essere che:
0 ≤ n-1-k ≤ k
per cui
{ k ≤ n-1
{ k ≥ (n-1)/2
quindi gli estremi validi della sommatoria sono (n-1)/2 e n-1, dunque
1/2 (2/3 + 1/3(-1/2)^n) + 1/2 ∑[(n-1)/2, n-1] (1/2)^k C(k,n-1-k) =
1/2 (2/3 + 1/3(-1/2)^n) + 1/2 (2/3 + 1/3(-1/2)^(n-1)) =
2/3 + 1/3(1/2(-1/2)^n + 1/2(-1/2)^(n-1)) =
2/3 + 1/3(1/2(-1/2)^n - 1/2*2(-1/2)^n) =
2/3 + 1/3(1/2(-1/2)^n - (-1/2)^n) =
2/3 + 1/3(-1/2(-1/2)^n) =
2/3 + 1/3(-1/2)^(n+1).
Per induzione:
si verifica che le due formule siano uguali per n = 1 e per n = 2
per n = 1 viene
(1/2)^1 C(1, 1-1) = 1/2 C(1,0) = 1/2
2/3 + 1/3(-1/2)^1 = 2/3 - 1/6 = 1/2
per n = 2 viene
∑[1,2] (1/2)^k C(k, 2-k) = 1/2 + 1/4 = 3/4
2/3 + 1/3(-1/2)^2 = 3/4
a questo punto si assume che valgano queste due uguaglianze:
∑[n/2, n] (1/2)^k C(k, n-k) = 2/3 + 1/3(-1/2)^n
∑[(n-1)/2, n-1] (1/2)^k C(k, n-1-k) = 2/3 + 1/3(-1/2)^(n-1)
se l'uguaglianza è vera allora vale anche:
∑[(n+1)/2, n+1] (1/2)^k C(k, n+1-k) = 2/3 + 1/3(-1/2)^(n+1)
infatti in questo modo siccome l'uguaglianza vale per i primi due valori di n allora posso estendere l'uguaglianza per tutti i valori di n successivi
∑[(n+1)/2, n+1] (1/2)^k C(k, n+1-k) =
faccio un cambio di indice k = k-1
∑[n/2, n] (1/2)^(k+1) C(k+1, n-k) =
poi sfrutto una proprieta del coefficiente binomiale (vedi fonti):
∑[n/2, n] (1/2)^(k+1) [ C(k, n-k) + C(k,n-1-k) ] =
1/2 ∑[n/2, n] (1/2)^k C(k, n-k) + 1/2 ∑[n/2, n] (1/2)^k C(k,n-1-k) =
1/2 (2/3 + 1/3(-1/2)^n) + 1/2 ∑[n/2, n] (1/2)^k C(k,n-1-k) =
nella sommatoria rimasta, deve essere che:
0 ≤ n-1-k ≤ k
per cui
{ k ≤ n-1
{ k ≥ (n-1)/2
quindi gli estremi validi della sommatoria sono (n-1)/2 e n-1, dunque
1/2 (2/3 + 1/3(-1/2)^n) + 1/2 ∑[(n-1)/2, n-1] (1/2)^k C(k,n-1-k) =
1/2 (2/3 + 1/3(-1/2)^n) + 1/2 (2/3 + 1/3(-1/2)^(n-1)) =
2/3 + 1/3(1/2(-1/2)^n + 1/2(-1/2)^(n-1)) =
2/3 + 1/3(1/2(-1/2)^n - 1/2*2(-1/2)^n) =
2/3 + 1/3(1/2(-1/2)^n - (-1/2)^n) =
2/3 + 1/3(-1/2(-1/2)^n) =
2/3 + 1/3(-1/2)^(n+1).
Visto che era in un compitino di aritmetica ...
Suppongo che giorgio.9292 = manuel.9393...
Comunque, non ho controllato tutti i conti, qualcosa penso sarebbe da aggiustare anche se credo che il nocciolo l'hai preso (come applicare l'induzione)
Però i calcoli sono molto molto più semplici, vediamo.
Come ha scritto Cmax, vale [tex]$p_n=\frac{1}{2}p_{n-1}+\frac{1}{2}p_{n-2}$[/tex]
Cioè puoi "decomporre" l'evento
{ottenere $n$ a questo tal punto}
come l'unione di altri due eventi:
{ottenere $n-1$ allo step precedente e poi ottenere testa} e
{ottenere $n-2$ allo step precedente e poi ottenere croce}
Se quindi hai l'ipotesi induttiva, vale subito
[tex]$\frac{1}{2}p_{n-1}+\frac{1}{2}p_{n-2}=\frac{1}{2}\cdot[\frac{2}{3}+\frac{(-1)^{n-1}}{3\cdot2^{n-1}}]+\frac{1}{2}\cdot[\frac{2}{3}+\frac{(-1)^{n-2}}{3\cdot2^{n-2}}]$[/tex]
Ora con pochi conti si arriva a vedere che quella quantità è proprio
[tex]$\frac{2}{3}+\frac{(-1)^n}{3\cdot 2^n}$[/tex]
@Cmax
Grazie per l'altra soluzione, che non avevo proprio pensato non avendo quasi conoscenza di eq alle differenze finite.
Comunque, non ho controllato tutti i conti, qualcosa penso sarebbe da aggiustare anche se credo che il nocciolo l'hai preso (come applicare l'induzione)
Però i calcoli sono molto molto più semplici, vediamo.
Come ha scritto Cmax, vale [tex]$p_n=\frac{1}{2}p_{n-1}+\frac{1}{2}p_{n-2}$[/tex]
Cioè puoi "decomporre" l'evento
{ottenere $n$ a questo tal punto}
come l'unione di altri due eventi:
{ottenere $n-1$ allo step precedente e poi ottenere testa} e
{ottenere $n-2$ allo step precedente e poi ottenere croce}
Se quindi hai l'ipotesi induttiva, vale subito
[tex]$\frac{1}{2}p_{n-1}+\frac{1}{2}p_{n-2}=\frac{1}{2}\cdot[\frac{2}{3}+\frac{(-1)^{n-1}}{3\cdot2^{n-1}}]+\frac{1}{2}\cdot[\frac{2}{3}+\frac{(-1)^{n-2}}{3\cdot2^{n-2}}]$[/tex]
Ora con pochi conti si arriva a vedere che quella quantità è proprio
[tex]$\frac{2}{3}+\frac{(-1)^n}{3\cdot 2^n}$[/tex]
@Cmax
Grazie per l'altra soluzione, che non avevo proprio pensato non avendo quasi conoscenza di eq alle differenze finite.
In effetti le equazioni alle differenze sono un argomento spesso trascurato (perlomeno nel cdl in fisica), ed è un peccato perché sono uno strumento di qualche utilità e presentano tali analogie con le equazioni differenziali a coefficienti costanti che chi ha studiato queste ultime acquisisce rapidamente padronanza almeno con le applicazioni di base delle prime. Anche per me furono una sorpresa, incontrata quasi per caso.
Per esempio, per loro tramite si può facilmente ricavare la formula di Binet per i numeri di Fibonacci.
EDIT. Consiglio di provarci da soli, in ogni caso riporto il procedimento in spoiler:
Per esempio, per loro tramite si può facilmente ricavare la formula di Binet per i numeri di Fibonacci.
EDIT. Consiglio di provarci da soli, in ogni caso riporto il procedimento in spoiler:
Propongo una soluzione leggermente euristica, per provare a rimanere nello spirito dell'esercizio.
Si vuole raggiungere quota "n" in "k" passi (di lunghezza aleatoria 1 o 2).
Dato che la probabilità di un qualsiasi cammino che raggiunge quota "n" in "k" passi sarà $1/2^k$, ci resta solo da calcolare il numero di cammini.
Per semplicità considero $n$ pari.
Prima valuto i casi estremi: se faccio solo passi unitari dovrò avere $k=n$, se faccio solo passi doppi dovrò avere $k=n/2$.
Ora dato che $n$ è pari ogni volta che faccio un passo unitario ne dovrò fare sicuramente un'altro unitario (nei k passi considerati).
Quindi ogni volta che sostituisco un passo doppio con uno unitario se parto dal caso $k=n/2$ ne dovrò aggiungere un altro unitario per completare il cammino, quindi se sostitiìuirò ogni passo doppio con uno unitario al massimo dovrò fare $k=n$ passi.
Da cui la probabilità cercata sarà:
$p(n)=\sum_{k=n/2: k\quad pari}^{n}1/2^k$
Non ho controllato il conto per la serie che penso si possa calcolare per differenza, però penso che possa funzionare.
Aspetto smentite...
Si vuole raggiungere quota "n" in "k" passi (di lunghezza aleatoria 1 o 2).
Dato che la probabilità di un qualsiasi cammino che raggiunge quota "n" in "k" passi sarà $1/2^k$, ci resta solo da calcolare il numero di cammini.
Per semplicità considero $n$ pari.
Prima valuto i casi estremi: se faccio solo passi unitari dovrò avere $k=n$, se faccio solo passi doppi dovrò avere $k=n/2$.
Ora dato che $n$ è pari ogni volta che faccio un passo unitario ne dovrò fare sicuramente un'altro unitario (nei k passi considerati).
Quindi ogni volta che sostituisco un passo doppio con uno unitario se parto dal caso $k=n/2$ ne dovrò aggiungere un altro unitario per completare il cammino, quindi se sostitiìuirò ogni passo doppio con uno unitario al massimo dovrò fare $k=n$ passi.
Da cui la probabilità cercata sarà:
$p(n)=\sum_{k=n/2: k\quad pari}^{n}1/2^k$
Non ho controllato il conto per la serie che penso si possa calcolare per differenza, però penso che possa funzionare.
Aspetto smentite...
Per la probabilità devi considerare che ogni volta che aggiungi un passo doppio, modifichi la molteplicità delle sequenze con cui è possibile conseguire il totale.
Quindi:
- se consideri [tex]n[/tex] passi di [tex]1[/tex], c'è solo una possibilità su [tex]2^n[/tex] possibili sequenze, cioè una probabilità [tex]\frac{1}{2^n}[/tex]
- per un solo passo doppio, esistono [tex]n-1[/tex] sequenze su un totale di [tex]\frac{1}{2^{n-1}}[/tex] che portano al risultato
- ormai il gioco è chiaro: per [tex]k[/tex] passi doppi, ci sono[tex]\binom{n-k}{k}[/tex] possibilità su un totale di [tex]\frac{1}{2^{n-k}}[/tex]
- il procedimento arriva fino a [tex]k=\lfloor n/2 \rfloor[/tex], cioè alla parte intera di [tex]n/2[/tex].
La probabilità ricercata è quindi [tex]\displaystyle p_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} \frac{1}{2^{n-k}}[/tex].
Al momento non mi viene in mente un modo immediato per calcolare la somma o per dimostrare che soddisfa la relazione di ricorrenza trovata (qui c'è un tedioso suggerimento), ma è facile verificare (anche con Excel, o con qualche programma di calcolo, in genere uso Maple) che il suo valore è uguale al risultato noto.
Quindi:
- se consideri [tex]n[/tex] passi di [tex]1[/tex], c'è solo una possibilità su [tex]2^n[/tex] possibili sequenze, cioè una probabilità [tex]\frac{1}{2^n}[/tex]
- per un solo passo doppio, esistono [tex]n-1[/tex] sequenze su un totale di [tex]\frac{1}{2^{n-1}}[/tex] che portano al risultato
- ormai il gioco è chiaro: per [tex]k[/tex] passi doppi, ci sono[tex]\binom{n-k}{k}[/tex] possibilità su un totale di [tex]\frac{1}{2^{n-k}}[/tex]
- il procedimento arriva fino a [tex]k=\lfloor n/2 \rfloor[/tex], cioè alla parte intera di [tex]n/2[/tex].
La probabilità ricercata è quindi [tex]\displaystyle p_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} \frac{1}{2^{n-k}}[/tex].
Al momento non mi viene in mente un modo immediato per calcolare la somma o per dimostrare che soddisfa la relazione di ricorrenza trovata (qui c'è un tedioso suggerimento), ma è facile verificare (anche con Excel, o con qualche programma di calcolo, in genere uso Maple) che il suo valore è uguale al risultato noto.
Ovviamente mi ero perso le molteplicità...grazie Cmax.
Di niente. Già che si è in argomento, per la somma si può procedere in questo modo. Ricordando la proprietà del coefficiente binomiale [tex]\displaystyle \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}[/tex], si può scrivere
[tex]\displaystyle p_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}\frac{1}{2^{n-k}} = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n -1 -k}{k} \frac{1}{2^{n-k}}+ \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-1-k}{k-1}\frac{1}{2^{n-k}}[/tex]
Osserviamo ora che
[tex]\displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n -1 -k}{k} \frac{1}{2^{n-k}} = \frac{1}{2}\sum_{k=0}^{\lfloor (n-1)/2 \rfloor} \binom{n-1-k}{k} \frac{1}{2^{n-1-k}} = \frac{1}{2}p_{n-1}[/tex]
in quando se [tex]n[/tex] è dispari, [tex]\lfloor n/2 \rfloor= \lfloor (n-1)/2\rfloor[/tex], mentre se [tex]n=2m[/tex] è pari, il termine omesso per [tex]k=m[/tex]
ha coefficiente [tex]\binom{m-1}{m}=0[/tex].
Per la seconda sommatoria, il primo termine, per [tex]k=0[/tex] causa un valore negativo nel coefficiente, quindi si può partire da [tex]k=1[/tex] e definire un indice [tex]k'=k-1[/tex], in modo che la somma diventi
[tex]\displaystyle \sum_{k'=0}^{\lfloor n/2 \rfloor -1 } \binom{n -2 -k'}{k'} \frac{1}{2^{n-1-k'}} = \frac{1}{2} \sum_{k'=0}^{\lfloor (n-2)/2 \rfloor} \binom{n -2 -k'}{k'} \frac{1}{2^{n-2-k'}} = \frac{1}{2}p_{n-2}[/tex]
La somma soddisfa allora la stessa relazione ricorsiva della probabilità trovata, anche se la dimostrazione andrebbe un po' rifinita.
[tex]\displaystyle p_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}\frac{1}{2^{n-k}} = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n -1 -k}{k} \frac{1}{2^{n-k}}+ \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-1-k}{k-1}\frac{1}{2^{n-k}}[/tex]
Osserviamo ora che
[tex]\displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n -1 -k}{k} \frac{1}{2^{n-k}} = \frac{1}{2}\sum_{k=0}^{\lfloor (n-1)/2 \rfloor} \binom{n-1-k}{k} \frac{1}{2^{n-1-k}} = \frac{1}{2}p_{n-1}[/tex]
in quando se [tex]n[/tex] è dispari, [tex]\lfloor n/2 \rfloor= \lfloor (n-1)/2\rfloor[/tex], mentre se [tex]n=2m[/tex] è pari, il termine omesso per [tex]k=m[/tex]
ha coefficiente [tex]\binom{m-1}{m}=0[/tex].
Per la seconda sommatoria, il primo termine, per [tex]k=0[/tex] causa un valore negativo nel coefficiente, quindi si può partire da [tex]k=1[/tex] e definire un indice [tex]k'=k-1[/tex], in modo che la somma diventi
[tex]\displaystyle \sum_{k'=0}^{\lfloor n/2 \rfloor -1 } \binom{n -2 -k'}{k'} \frac{1}{2^{n-1-k'}} = \frac{1}{2} \sum_{k'=0}^{\lfloor (n-2)/2 \rfloor} \binom{n -2 -k'}{k'} \frac{1}{2^{n-2-k'}} = \frac{1}{2}p_{n-2}[/tex]
La somma soddisfa allora la stessa relazione ricorsiva della probabilità trovata, anche se la dimostrazione andrebbe un po' rifinita.
Per completare il tutto:
http://www.wolframalpha.com/input/?i=Sum[Binomial[n-k%2Ck]1%2F2^%28n-k%29%2C{k%2C0%2Cn%2F2}]
http://www.wolframalpha.com/input/?i=Sum[Binomial[n-k%2Ck]1%2F2^%28n-k%29%2C{k%2C0%2Cn%2F2}]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo