Sequenze palindrome
Massimo Brighi
e croce lanciando in aria una moneta.
Termina una sequenza quando, avendo lanciato
almeno due volte, la sequenza ottenuta è
palindroma.
Qual è la lunghezza media delle sue sequenze?
Ciao
Massimo
Adriano
2 tiri: TT CC
3 tiri: TTT TCT CCC CTC
4 tiri: TTTT TCCT CTTC CCCC
in pratica dopo n tiri i risultati palindromi sono in numero:
2^((n+1) div 2) su 2^n risultati possibili.
La probabilita' richiesta si ottiene dalla sommatoria di n * P(n),
dove P(n) e' la probabilita' di un risultato palindromo dopo n
lanci.
Quindi, facendo un po' di calcoli e qualche ragionamento si
ottiene che il termine della sommatoria diventa (spero!):
(4*n+1) / 2^n, che tende a 9.
Ciao,
Adriano
On Sun, 23 Jul 2000 18:03:13 +0200, Massimo Brighi
<NOSPAM...@iperbole.bologna.it> wrote:
>Un tipo crea delle sequenze di testa
>e croce lanciando in aria una moneta.
>Termina una sequenza quando, avendo lanciato
>almeno due volte, la sequenza ottenuta č
>palindroma.
>Qual č la lunghezza media delle sue sequenze?
>
>Ciao
>Massimo
>
Silvio Sergio
> Le possibili uscite palindrome sono:
>
> 2 tiri: TT CC
> 3 tiri: TTT TCT CCC CTC
Se ho ben interpretato, TTT e CCC non vanno bene perche` gia` TT e CC sono
palindrome. Le stringhe non devono avere prefissi palindromi, altrimenti ci
si fermerebbe prima.
Silv:o)
Massimo Brighi
Adriano wrote:
> Le possibili uscite palindrome sono:
>
> 2 tiri: TT CC
> 3 tiri: TTT TCT CCC CTC
> 4 tiri: TTTT TCCT CTTC CCCC
No, attento, non puoi avere TTT o CCC perchč dopo
TT o CC gia' ti devi fermare perche sono sequenze
palindrome.
Ciao
Massimo
Adriano
Potrebbe essere cosi':
indicando sempre con P(n) la probabilita' che alla sequanza di lanci
lunga n ci sia un risultato palindromo, la sommatoria dovrebbe essere:
2*P(2) + 3*P(3)*(1-P(2)) + 4*P(4)*(1-P(3))*(1-P(2)) + ... +
+ n * P(n) * (1-P(n-1)) * (1-P(n-2)) * ... * (1-P(2))
Onestamente non sono riuscito a risolvere analiticamente la
sommatoria; numericamente mi risulta
N = 2,69734...
Ciao
Adriano
On Mon, 24 Jul 2000 09:41:24 +0200, Adriano <craz...@nopay.it> wrote:
>Le possibili uscite palindrome sono:
>
>2 tiri: TT CC
>3 tiri: TTT TCT CCC CTC
>4 tiri: TTTT TCCT CTTC CCCC
>
Silvio Sergio
> Effettivamente avevo liquidato tutto troppo facilmente.
>
> Potrebbe essere cosi':
> indicando sempre con P(n) la probabilita' che alla sequanza di lanci
> lunga n ci sia un risultato palindromo, la sommatoria dovrebbe essere:
>
> 2*P(2) + 3*P(3)*(1-P(2)) + 4*P(4)*(1-P(3))*(1-P(2)) + ... +
> + n * P(n) * (1-P(n-1)) * (1-P(n-2)) * ... * (1-P(2))
>
> Onestamente non sono riuscito a risolvere analiticamente la
> sommatoria; numericamente mi risulta
E` molto piu` facile di quanto sembri! Prova a scrivere le sequnze
palindrome che non hanno prefissi palindromi, ti accorgerai che sono
sequenze moooooolto particolari.
Ciao, Silv:o)
Adriano
interpretato male il testo!
Secondo il mio ragionamento una persona tirava 2 volte la moneta,
se il risultato era palindromo si fermava, altrimenti ricominciava
tirando 3 volte, e cosi' via... In pratica supponevo effettuasse
sessioni di 2, 3, 4, ... tiri, e si chiedesse quale era la sessione
media a cui fermarsi.
In effetti il problema originale e' molto piu' semplice.
Sighciao
Adriano
On Tue, 25 Jul 2000 11:42:30 +0200, "Silvio Sergio" <mg9...@mclink.it>
wrote:
Andrea Artesiani
Massimo Brighi <NOSPAM...@iperbole.bologna.it> scritto nell'articolo
<397B1740...@iperbole.bologna.it>...
> Un tipo crea delle sequenze di testa
> e croce lanciando in aria una moneta.
> Termina una sequenza quando, avendo lanciato
> almeno due volte, la sequenza ottenuta è
> palindroma.
> Qual è la lunghezza media delle sue sequenze?
>
> Ciao
> Massimo
>
>
>
Direi che la media è 3.
Ci sono due sole sequenze palindrome di lunghezza "i"
per ogni i da 2 a infinito.
i=2 TT CC
i=3 TCT CTC
i=4 TCCT CTTC
...
la media è quindi:
inf
sum i*2*(1/2)^i =3
i=2
Ciao
Andrea
Massimo Brighi
Andrea Artesiani wrote:
Esatto.
Ciao
Massimo
Silvio Sergio
> > Qual è la lunghezza media delle sue sequenze?
> Direi che la media è 3.
Infatti si tratta di lanciare la moneta una volta, e poi aspettare fino a
che non si ripresenta la stessa faccia, ottenendo una sequenza x[y]x
palindroma. Dato che una determinata faccia ha probabilita` p=1/2,
mediamente esce dopo 1/p=2 tiri. Aggiungiamo quello iniziale ed il gioco e`
fatto.
Silv:o)