Newsgroup: it.hobby.enigmi
Titolo: Lanci di monete

Visto il bel problema di probabilità di anbra1 vi propongo questa
curiosità dal libro di Martin Gardner che sto leggendo in questi
giorni.
Consideriamo il lancio di un monetà e prendiamo nota delle uscite,
avremo una serie del tipo TTCTCCTTC....
Qual è il tempo di attesa perchè si veda uscire la stringa CTCT? e la
stringa TCTT?
Qual è la probabilità che la stringa CTCT si presenti prima della
TCTT?
Notato nulla di "strano"?
Ciao,
GaS

 wrote




.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Entrambe le sequenze di 4 caratteri hanno probabilità di uscita 1/16, quindi 
il tempo di attesa è 16 lanci.
Verrebbe da dire che, come conseguenza, la probabilità che esca prima una o 
l'altra è la stessa. Invece, e penso sia questa la cosa "strana" che intende 
Gabriele, analizzando le due sequenze si vede che hanno una sottosequenza in 
comune: TCT.
Quando questa sequenza compare, prima e dopo sono state lanciate altre 
monete. I casi sono 4:
1. TtctT
2. TtctC
3. CtctT
4. CtctC
Nel caso 2 non compare alcuna sequenza che ci interessa.
Nel caso 1 compare la sequenza TCTT.
Nel caso 4 compare CTCT.
Nel caso 3 compaiono entrambe ma prima la CTCT.
Quindi, 2 volte su 3 compare prima la sequenza CTCT.
Volendo proprio fare i pignoli, bisognerebbe considerare anche il caso il 
cui le due sequenze compaiono all'inizio, in questo caso può apparire con 
uguale probabilità o l'una o l'altra. Quindi in definitiva appare prima la 
CTCT con probabilità 1/16 * 1/2 + 15/16 * 2/3 = 0.65625.
Salvo errori, omissioni e ripensamenti...
Ciao
Giorgio

 ha scritto nel messaggio 
news:85bcce0f-52da-42e3...@l16g2000yqo.googlegroups.com...





Ciao,
GaS
---------------
Salvo errori, la probabilità di ottenere CTCT dopo n lanci è:
     n               P(n)      Prob. cumulata
  ------          ---------    ---------------------
    4              1/16                1/16
    5               2/32               4/32
    6               3/64               11/64
    7              6/128              28/128
    8            12/256              68/256
    9            22/512            158/512
 10            41/1024           357/1024
  11           78/2048           792/2048
Con 1-2-3-6-12-22-41-78...
a(n) = a(n-1)+a(n-2)+a(n-3)+a(n-4)-a(n-5)
mentre quella di ottenere TCTT dopo n lanci è:
     n               P(n)      Prob. cumulata
  ------          ---------    ---------------------
    4              1/16                1/16
    5               2/32               4/32
    6               4/64               12/64
    7              7/128              31/128
    8            13/256              75/256
    9            24/512            174/512
 10            45/1024           393/1024
  11           84/2048           870/2048
Con 1-2-4-7-13-24-45-84.....
a(n) = 2a(n-1)-a(n-3)+a(n-4)
Si nota che fino a n=18         p(TCTT) >= p(CTCT)
poi c'è l'inversione e diventa sempre minore.
Nino


Ecco appunto... :-)
Mi sono messo a fare qualche simulazione al computer e sembra che la seconda 
affermazione sia confermata.
Per quanto riguarda invece la prima, le cose non sono così semplici come le 
avevo ipotizzate io. Ho cercato i tempi d'attesa delle varie sequenze e ho 
trovato i seguenti risultati (escludendo sempre dal conto i primi tre lanci 
per portarsi nella situazione in cui dal quarto lancio si possa concludere 
qualcosa).
TTTT    ~27
TTTC    ~13
TTCT    ~15
TTCC    ~13
TCTT    ~15
TCTC    ~17
TCCT    ~15
TCCC    ~13
discorso analogo scambiando T con C.
Anche se all'inizio questi risultati possono sembrare strani, la 
giustificazione sta nel fatto che in alcune sequenze, se non viene l'esito 
atteso al quarto lancio (o prima), bisogna cominciare completamente da capo 
(es. TTTT), mentre in altri casi si è ancora in tempo con il successivo o i 
successivi lanci a completare la sequenza (es. nel caso TTTC, se al posto di 
C esce T, siamo ancora all'interno di una sequenza [T]TTT che può 
completarsi con un successivo C).
La cosa è interessante... :-)
Ciao
Giorgio


Ora mi sovviene che la cosa "strana" da notare potrebbe essere che la 
sequenza CTCT, pur avendo un'attesa media maggiore della sequenza TCTT, esca 
prima con probabilità > 1/2.
Ci si può convincere che le due cose non sono strettamente dipendenti 
considerando il caso della sequenza TTTT, con attesa molto alta e la 
sequenza TTTC con attesa molto bassa. La probabilità di ognuna di uscire 
prima dell'altra è 1/2. Infatti, nel momento in cui si è presentata la 
sequenza TTT, con uguale probabilità l'ultimo lancio determina l'uscita 
dell'una o dell'altra.
A questo punto rilancio con un altro caso (non difficile): qual è la 
probabilità che la sequenza CTTT esca prima della sequenza TTTT?
Ciao
Giorgio

 probabilità che la sequenza CTTT esca prima della sequenza TTTT?
Direi che la sequenza TTTT può uscire prima esclusivamente se sono le
prime 4 uscite in assoluto, e quindi con probabilità 1/16.
A questo punto però una domanda sorge spontanea: io ho sempre
calcolato il tempo di attesa come il reciproco della probabilità (come
fatto anche da Giorgio nel primo post), dov'è l'errore? Qual'è la
definizione esatta (matematica) di tempo di attesa?
Ciao,
GaS

 probabilità che la sequenza CTTT esca prima della sequenza TTTT?
Direi che la sequenza TTTT può uscire prima esclusivamente se sono le


 probabilità che la sequenza CTTT esca prima della sequenza TTTT?
Direi che la sequenza TTTT può uscire prima esclusivamente se sono le


 ha scritto nel messaggio 
news:49a94fb5$0$835$4faf...@reader5.news.tin.it...

Confermo i dati di Giorgio relativamente ai tempi di attesa.
Che sono:
TTTT  e CCCC = 30
CCTT ; TTCC ; CTTT ; TCCC ; CCCT ; TTTC  = 16
CTTC ; TCCT ; CTCC ; TCTT ; CCTC ; TTCT  = 18
CTCT e TCTC  = 20
Io li ho ottenuti partendo dalle sequenze che ho postato in precedenza e 
cioè:
 n      TTTT ...   CCTT....    CTTC....  CTCT 
Attesa
 A        B             C                D              E          TTTT 
CCTT    CTTC    CTCT
----    ---------    -----------     -----------   ---------      -----------------------------------------
 4         1              1                1              1 
(B) (C) (D) (E)*A/2^A
 5         1              2                2              2          0,03125 
.....        ......     0,0625
 6         2              4                4              3          0,03125 
.....        ......    0,04687
 7         4              8                7              6          0,03125 
......        ......    0,04687
 8         8             15             13            12         0,03125 
......        .......   0,04687
 9        15            28             24            22         0,02929 
......      ........   0,04297
10       29            52             45            41        0,02832 
.......      ........   0,04004
....      ......           ......           .......          ........ 
.............    ........     ........    .............
600 4,2E169  7,3E157   3,8E161  6,4E163  6,0E-09  .....        ...... 
9,2E-15
somma =                                                             30 
16         18           20
Ciao
Nino


Che casino!

Ripeto solo il calcolo  (correggendo anche gli errori)
per TTTT e CCCC (il resto č uguale):
n           TTTT  (B)            Attesa
A         n.sequenze         B*A/(2^A)
----       ----------------       --------------
 4               1                     0,25
 5               1                     0,15625
 6               2                     0,1825
 7               4                     0,21875
 8               8                     0,25
 9             15                    0,26367
10            29                   0,28320
11            56                   0,30078
....           ......                    .............
            tetranacci
600        4,2E169           6,0E-09
somma                                 30
Scusate
Nino 

 definizione esatta (matematica) di tempo di attesa?
Mi unisco nell'attesa di lumi.
Ciao!
Giorgio 

 simulazione?
Il metodo migliore è quello di usare le funzioni generatrici. E' tutto
spiegato nel cap. 8.4 del libro "Concrete Mathematics" di Graham, Knuth
e Patashnik, che non a caso s'intitola "Flipping coins". (Il libro è
tradotto in italiano col titolo "Matematica discreta").
Provo a spiegare succintamente il metodo per trovare il tempo di attesa
per CTCT. Indichiamo con N la somma di tutte le sequenze di lanci in cui
CTCT non è ancora apparsa:
N = 1 + T + C + TT + TC + ....
(1 è la sequenza nulla, perché trattiamo formalmente ogni sequenza come
se fosse un prodotto).
Indichiamo con S la somma di tutte le sequenze vincenti, cioè quelle che
terminano con CTCT e nelle quali tale CTCT non sia uscita prima:
S = CTCT + TCTCT + CCTCT + ...
Allora ci si può convincere che:
1 + N(C + T) = N + S
e inoltre:
NCTCT = S + SCT.
Da queste si ricava: 
S = CTCT/(1 - C - T + CT - CTC - CTT + CTCT).
Sostituendo nel secondo membro C e T con (1/2)z si ottiene la funzione
generatrice:
G(z) = z^4/[4(4 + z^2)(1-z) + z^4].
Il tempo di attesa non è altro che la derivata di G in z=1, che si
calcola facilmente essere 20. Invece G(1) indica semplicemente la
probabilità che prima o poi esca CTCT e questa ovviamente è 1.
In modo analogo, nel caso di TCTT si trova un tempo d'attesa di 18.
Anche il problema di quale sequenza esca prima si può affrontare nello
stesso modo. Indichiamo con S1 la somma delle sequenze vincenti per
CTCT, con S2 la somma delle sequenze vincenti per TCTT e con N la somma
delle sequenze in cui non è uscito nessuno dei due. Si ha:
1 + N(C + T) = N + S1 + S2,
NCTCT = S1 + S1CT,
NTCTT = S2 + S1T + S1CTT + S2CTT.
Visto che stavolta c'interessano semplicemente i valori delle funzioni
generatrici di S1 e s2 per z=1 (chiamiamoli p1 e p2), possiamo
sostituire direttamente C e T con 1/2, col che il sistema diventa:
p1 + p2 = 1,
5 p1 = 9 p2,
da cui la soluzione di Martin Gardner:
p1 = 9/14,  p2 = 5/14.
Maurizio
-- 
Per rispondermi via e-mail togli l'ovvio.


Mi pare di aver visto un "trucco" di Conway per fare questi calcoli da
qualche
parte.

 definizione esatta (matematica) di tempo di attesa?
Non avevo visto questa richiesta, provo a rispondere.
La definizione è quella di valor medio di n, numero di lanci per
ottenere il risultato voluto. Se p(n) è la probabilità di ottenere il
risultato in n lanci, allora tale valor medio è dato da:
<n> = Sum[n*p(n)]
Il risultato 1/p è un caso particolare, che si ottiene ad esempio quando
p(n) = p*(1-p)^(n-1).
La funzione generatrice che ho usato nell'altro post è definita così:
G(z) = Sum[p(n)*z^n];
quindi la sua derivata è:
G'(z) = Sum[p(n)*n*z^(n-1)].
Da qui si vede chiaramente che <n> = G'(1).


 di tempo di attesa?
La definizione di tempo [medio] di attesa è proprio quella più ovvia: la 
media dei tempi di attesa per tutti i casi, ponderata dal peso delle varie 
probabilità nel caso di eventi non equiprobabili.
Il caso di prove ripetute indipendenti è noto ed ha una distribuzione dei 
tempi di attesa binomiale. Sarebbe per esempio il caso in cui si voglia 
calcolre il tempo di prima uscita di "CTCT" lanciando quattro monete in 
sequenza e ripetendo l'esperimento. Allora avrebbe un senso dire che la 
sequenza "CTCT" ha probabilità 1/16. Il tempo medio di attesa è legato alla 
somma di una serie di potenze e vale 1/p.
Altro caso è quello porposto dal problema.
Analizziamo il caso semplicissimo di sequenze "TT" e "TC", e chiediamoci 
quele sia il tempo medio di atesa della prima occorrenza di una o dell'altra 
lanciando una moneta alla volta, come nella formulazione del probleima 
iniziale. E' evidente che TC mediamente ha tempo di attesa minore, perchè 
entrambe le sequenze hanno bisogno della prima T, ma poi dovesse andar male 
per la prima sequenza si tratta di cominciare da capo mentre per la seconda 
si resta sempre a metà dell'opera.
In pratica per TT servono mediamente X lanci composti da 2 per aspettare la 
prima T, più un altro lancio che nel caso migliore è l'ultimo, nel caso 
sfortunato altri X perchè si ricomincia da capo.
X = 2 + 1 + 1/2X da cui X=6
Per TC servono 2 lanci per vedere la prima T, più 2 lanci per vedere la 
prima C, 4 in totale
--
Ciao, Silv:o) 

 Notato nulla di "strano"?
Per le prime due domande, ho un metodo standard basato sulle catene di 
markow (rpobabilità di assorbimento).
Gli stati della catena sono numerati in base ai caratteri utili che ci sono 
in coda alla sequnza
0:
1: T
2: TC
3: TCT
4: TCTC
Dallo stato iniziale, possiamo passare con prob. 1/2 nello stato 1 se esce 
T, oppure restare in 0 se esce una inutile C e così via, a formare una 
matrice M delle transizioni (non metto lo stato "assorbente" 4 perchè 
inutile)
1/2, 1/2,   0,   0
  0, 1/2, 1/2,   0
1/2,   0,   0, 1/2
  0, 1/2,   0,   0
ora, chiamiamo Tn il tempo medio di attesa della sequenza finale a partire 
dallo stato n
Si vede facilmente che
T0 = 1/2(1+T0) + 1/2(1+T1) = 1 + 1/2T0 + 1/2T1
perchè la metà delle volte mi porterò in T1 e quindi dovrò aspettare un 
lancio in più (quello appena fatto) di quanto in media aspetto quando sto in 
1, l'altra metà delle volte dovrò ho solo perso un giro e dovrò aspettare 
ancora T0 lanci. La forma più comoda è la seconda, quella "1 + 1/2T0 + 
1/2T1" con l'uno del il giro perso già evidenziato.
Analogamante si costruiscono le altre, metto solo la seconda
T1 = 1 + 1/2T1 + 1/2T2
Il sistema di 4 equazioni è semplice da risolvere, col calcolo matriciale 
sarebbe:
T = 1 + M*T
e T a conti fatti risulta essere [20, 18, 16, 10], ovvero 20 mosse in media 
dallo stato 0.
Gli stessi calcoli per l'altra sequenza "TCTT" danno [18, 16, 14, 8].
I due punti in meno di media sono presto giustificati:
I primi tre stati sono del tutto analoghi nei due casi (sempre alternanze 
TC), mentre il quarto stato "TCT" è differente perchè nel caso "TCTT" se non 
si vince si fa un solo passo indietro, tenendo per buoni due simboli invece 
che uno solo e risparmiano i 2 lanci mediamente necessari per passare da uno 
stato all'altro.
Per la seconda domanda, la probabilità che la sequenza "CTCT" esca prima di 
"TCTT" è un problema di assorbimento in uno stato prima dell'altro. Magari 
l'avrò anche studiato eoni fa, ma non me lo ricordo. A occhio siccome 
l'inizio di "TCTT" è contenuto nel finale di "CTCT" all'incirca una volta su 
due che esce la sequenza "TCTT" questa era stata preceduta da una C che fa 
pendere decisamente il piatto della bilanciia da una parte.
Ma per i calcoli dovrei andare a scartabellare tra i libri, e dopo aver 
visto l'approccio basato sulle funzioni generatrici mi è passata la voglia.
-- 
Ciao, Silv:o) 

 probabilità che prima o poi esca CTCT e questa ovviamente è 1.
Il resto più o meno l'ho capito, o meglio, ho capito come usarlo.
--
Ciao, Silv:o)

 operazioni inverse non mi sono molto chiare.
Puoi usare l'identità:
(1 - X)^(-1) = 1 + X + X^2 + X^3 + ...
Chiaramente il calcolo esplicito risulta piuttosto laborioso, con questo
metodo, ma in linea di principio è perfettamente corretto. 
Fortunatamente per costruire la funzione generatrice non occorre trovare
la somma S in carne ed ossa: la probabilità di ogni sequenza di T e C si
ottiene sostituendo a T e C le loro probabilità p e q (entrambe uguali a
1/2, per una moneta normale); se poi al posto di T e C sostituiamo pz e
qz, otteniamo che tale probabilità viene moltiplicata per z^n, dove n è
il numero totale di T e C nella sequenza. 
La somma di tutte queste quantità ci dà proprio la funzione generatrice:
G(z) = Sum[P(n)*z^n]
dove con P(n) ho indicato la probabilità che il risultato si ottenga in
n passi. Infatti P(n) è uguale alla somma delle probabilità di ottenere
le singole sequenze di n teste e croci.
Spero di essere stato d'aiuto.


 prima C, 4 in totale
Tutto chiaro, grazie mille!
Ciao,
GaS

 Spero di essere stato d'aiuto.
Ti ringrazio tantissimo per la spiegazione che, purtroppo, non riesco
a seguire (naturalmente per miei limiti)
Grazie davvero, proverò a studiarla meglio,
Ciao,
GaS

 qualche parte.
Si, è spiegato nel libro che sto leggendo ma, per quanto mi riguarda,
più che un trucco matematico sembra un trucco di magia  :-)
Vediamo che si è inventato Conway riprendendo da Gardner stesso
(viaggio nel tempo e altre stranezze matematiche).
La chiave è il calcolo di 4 numeri binari. Indichiamo con A l'insieme
di 4 lanci TCTT e con B la squenza CTCT.
Scriviamo A sopra A, B sopra B, A sopra B e B sopra A come segue
A=TCTT
A=TCTT
B=CTCT
B=CTCT
A=TCTT
B=CTCT
B=CTCT
A=TCTT
Sopra l'insieme di ogni coppia si costruisce un numero binario nella
maniera che segue:
consideriamo la prima coppia, AA. Osserviamo il gruppo superiore e
chiediamoci se le quattro lettere, cominciando dalla prima, coincidono
esattamente alle prime quattro lettere del numero inferiore.
Ovviamente è così e quindi scriviamo 1 sopra la prima lettera. Poi,
guardiamo la seconda lettera del gruppo superiore e chiediamoci se le
tre lettere, cominciando da questa, coincidono esattamente alle prime
tre lettere del numero inferiore. La risposta è negativa e quindi
scriviamo uno 0 sopra la seconda lettera. Poi, guardiamo la terza
lettera del gruppo superiore e chiediamoci se le due lettere,
cominciando da questa, coincidono esattamente alle prime due lettere
del numero inferiore. La risposta è negativa e quindi scriviamo uno 0
sopra la terza lettera. E così via...
Facendo questo lavoro per ogni coppia e trasformando i numeri binari
in decimale avremo:
  1001=9
A=TCTT
A=TCTT
  1010=10
B=CTCT
B=CTCT
  0000=0
A=TCTT
B=CTCT
  0101=5
B=CTCT
A=TCTT
Il rapporto tra le vittorie di B e qulle di A sono date da (AA-AB)/(BB-
BA)=(9-0)/(10-5)=9/5
Si ricava quindi che B vince 9 volte su 14 come già trovato.
E il valore atteso per A? Semplice, basta raddoppiare AA: 9*2=18.
Ugualmente per il valore atteso di B pari a BB*2=20.
Il metodo funziona anche per n-ple di lunghezze differenti col vincolo
che la n-pla più corta non sia compresa in quella più lunga.
Solo Conway poteva "inventare" una diavoleria simile...
Perchè funziona? Non ne ho la più pallida idea ma sembra che una
dimostrazione esista e si possa trovare nel Journal of Combinatorial
Theory del 30 marzo 1981 in un articolo di Guibas e Odlyzko.
Spero di non avervi tediato,
ciao,
GaS

 Spero di non avervi tediato,
E già! magia pura. La lettura del tuo post mi ha precipitato in un dejavu, 
altro che tediarci.
Se qualcuno avesse ancora i vecchi numeri di mclink con la stupenda rubrica 
"intelligiochi" magari potrebbe confermare il flash che ho avuto. Mi pare 
che il mitico curatore Dani Ferrari riportasse con lo stesso tuo ammirato 
stupore il trucco del grandissimo matematico inglese.
-- 
Ciao, Silv:o)