Cap la cap — succesul e mai roz decât pare

Aruncăm în mod repetat o monedă corectă și ne oprim imediat ce obținem două fețe consecutive HH. Care este numărul așteptat de aruncări?

O estimare intuitivă ar putea porni de la probabilitatea $ p = 1/4 $ de a obține secvența HH în două aruncări, conducând la un timp mediu de așteptare de 4 aruncări¹. Totuși, acest calcul presupune implicit că examinăm blocuri independente de câte două aruncări. El ignoră natura glisantă a ferestrei de observație și revenirea asimetrică în cazul eșecului, caracteristice problemelor de identificare a secvențelor.

Pentru a modela riguros acest proces, folosim o aplicație simplă a Principiului optimalității al lui Bellman. Este un caz deosebit de simplu: există o singură acțiune posibilă — aruncarea monedei — iar costul imediat al fiecărei acțiuni este constant și egal cu o aruncare. Singura sursă de incertitudine este rezultatul aruncării, care determină starea următoare a procesului.

Astfel, putem exprima recursiv costul așteptat rămas, transformând o problemă cu orizont infinit într-un sistem finit de ecuații. Pentru o prezentare mai generală a Principiului optimalității al lui Bellman Bellman (1952), inclusiv a condițiilor în care acesta este aplicabil, vezi postarea Urmând calea onestă.

Principiul optimalității al lui Bellman Link spre

În cadrul Programării Dinamice, funcția de valoare $ V(s) $ reprezintă numărul așteptat de aruncări suplimentare necesare pentru a atinge secvența țintă, pornind din starea $ s $. Definim spațiul stărilor pe baza seriei curente de fețe consecutive:

• $ S_0 $: Starea de bază (nu a fost obținut niciun Heads anterior SAU ultima aruncare a fost Tails).
• $ S_1 $: Starea de progres parțial (ultima aruncare a fost Heads).
• $ S_2 $: Starea terminală (HH a fost obținut, $ V(S_2) = 0 $).

Conform ecuației de așteptare Bellman, funcția de valoare $ V(S) $ — care reprezintă numărul așteptat de aruncări rămase din starea $ S $ — satisface:

V(S) = 1 + \mathbb{E}\big[ V(S') \mid S \to S' \big] \tag{1}

Primul termen $ 1 $ reprezintă costul efectuării următoarei aruncări. Așteptarea condiționată se dezvoltă direct pe baza tranzițiilor din spațiul stărilor. Pentru starea de bază $ S_0 $, această așteptare devine:

\mathbb{E}\big[V(S') \mid S_0 \to S' \big] = V(S_0)\cdot p(S_0 \mid S_0) + V(S_1) \cdot p(S_1 \mid S_0) \tag{2}

Înlocuind așteptările condiționate în ecuația Bellman, obținem următorul sistem:

\begin{cases}
V(S_1) = 1 + \frac{1}{2} V(S_0) + \frac{1}{2}\underbrace{V(S_2)}_{0}, \\\
V(S_0) = 1 + \frac{1}{2} V(S_0) + \frac{1}{2} V(S_1)
\end{cases} \tag{3}

Rezolvarea acestui sistem cu 2 stări conduce la valorile concrete $ V(S_0)=6 $ și $ V(S_1)=4 $. Totuși, pe măsură ce spațiul stărilor se extinde la $ n $ repere succesive sau puncte de control al riscului, rezolvarea manuală a sistemelor liniare devine imposibil de gestionat. Pentru a evalua procese arbitrare cu $ n $ stări distincte și probabilități de succes variabile $ p_k $, trebuie să extindem această relație de recurență într-o soluție analitică de formă închisă.

Deducerea formulei generale Link spre

Fie $ V_k $ numărul așteptat de pași suplimentari necesari pentru a ajunge în starea țintă $ S_n $, pornind din starea $ S_k $.

În fiecare stare $ S_k $, pentru $ k {0, 1, , n-1} $, procesul are două tranziții posibile:

• Avansează în starea $ S_{k+1} $ cu probabilitatea $ p_k $.
• Revine în starea inițială $ S_0 $ cu probabilitatea $ 1-p_k $.

Presupunând că $ 0 < p_k $, ecuația Bellman pentru starea $ S_k $ este:

V_k = 1 + p_k V_{k+1} + (1-p_k)V_0  

Termenul $ 1 $ reprezintă pasul tocmai efectuat, în timp ce ceilalți termeni exprimă numărul așteptat de pași suplimentari după tranziție. Condiția la limită este $ V_n = 0 $, deoarece nu mai sunt necesari pași suplimentari odată ce starea țintă a fost atinsă. Putem deduce valoarea $ V_0 $ prin substituții succesive ale ecuațiilor Bellman.

1. Pornind din starea $ S_0 $:

V_0 = 1 + p_0 V_1 + (1-p_0)V_0

Rearanjând termenii, obținem:

V_1 = V_0 - \frac{1}{p_0}

2. Pornind din starea $ S_1 $:

V_1 = 1 + p_1 V_2 + (1-p_1)V_0

Înlocuind expresia pentru $ V_1 $:

V_0 - \frac{1}{p_0} = 1 + p_1 V_2 + (1-p_1)V_0

Rearanjând termenii:

V_0 = \frac{1}{p_1} + \frac{1}{p_0 p_1} + V_2

3. Continuarea substituțiilor:

Fiecare substituție succesivă introduce încă un factor invers al probabilității de tranziție. După $ n $ substituții, obținem:

V_0 = \frac{1}{p_0} + \frac{1}{p_0p_1} + \cdots + \frac{1}{p_0p_1\cdots p_{n-1}} + V_n

Folosind condiția la limită $ V_n = 0 $, rezultă formula generală:

V_0 = \sum_{k=0}^{n-1} \prod_{j=0}^{k} \frac{1}{p_j}

Prin urmare, numărul așteptat de pași necesari pentru atingerea stării țintă este suma inverselor probabilităților de realizare cu succes a fiecărei secvențe succesive de tranziții.

Acest rezultat se aplică proceselor cu revenire la zero, în care fiecare tranziție nereușită readuce procesul în starea inițială $ S_0 $, în timp ce fiecare tranziție reușită îl avansează cu exact o stare.

Deducerea distribuției exacte Link spre

Fie $ N $ variabila aleatoare care reprezintă numărul total de aruncări necesare pentru a obține pentru prima dată două fețe consecutive (HH). Fie $ a_k $ numărul secvențelor valide de lungime $ k $ care se termină cu HH pentru prima dată.

Pentru $ k \geq 2 $:

• $ k = 2 $: HH $ \implies a_2 = 1 $.
• $ k = 3 $: THH $ \implies a_3 = 1 $.
• Pentru $ k \geq 4 $, o secvență validă de lungime $ k $, care se termină cu HH pentru prima dată, trebuie să îndeplinească una dintre următoarele condiții:
  1. Începe cu T, urmat de o secvență validă de lungime $ k-1 $ $ \implies a_{k-1} $.
  2. Începe cu HT², urmat de o secvență validă de lungime $ k-2 $ $ \implies a_{k-2} $.

Prin urmare, numărul rezultatelor favorabile respectă o relație de recurență similară cu cea a numerelor Fibonacci:

a_k = a_{k-1} + a_{k-2}, \quad \text{pentru } k \geq 4, \quad \text{cu } a_2 = 1, a_3 = 1.

Deoarece fiecare secvență de lungime $ k $ are $ 2^k $ rezultate echiprobabile, funcția de masă a probabilității este:

P(N = k) = \frac{a_k}{2^k} = \frac{F_{k-1}}{2^k}, \quad \text{pentru } k \geq 2

unde $ F_m $ reprezintă termenul de rang $ m $ din șirul lui Fibonacci ($ F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, \dots $).

În , putem folosi aproximarea:

RV(2:1000,sapply(2:1000, function(k) numbers::fibonacci(k-1)/2^k),fractions=F,remove=F)⏎ 
════════════════════════════════════════════════════════════════════════════════════════
Variabilă aleatoare cu |999⟩ evenimente, (µ = 6 | σ = 4.69), entropia 2.49
──
ᴿᵢ      2      3      4      5      6      7      8      9     10     11     12     13     14     15     16     17     18     19     20     21     22     23     24     25     26     27     28     29     30     31     32
ᵖᵢ 0.2500 0.1250 0.1250 0.0938 0.0781 0.0625 0.0508 0.0410 0.0332 0.0269 0.0217 0.0176 0.0142 0.0115 0.0093 0.0075 0.0061 0.0049 0.0040 0.0032 0.0026 0.0021 0.0017 0.0014 0.0011 0.0009 0.0007 0.0006 0.0005 0.0004 0.0003
ℹ Se afișează primele 31 valori importante* cu extremele [2:78], VaR(99.5%) = 26.

Paradoxul resetării Link spre

În Fundamentals: Ten Keys to Reality, laureatul Premiului Nobel pentru fizică Frank Wilczek Wilczek (2021) propune un algoritm extraordinar de simplu pentru reproducerea operelor complete ale lui Shakespeare:

• Alege aleatoriu un caracter ASCII – o literă, o cifră, un spațiu sau un semn de punctuație.
• Înregistrează-l.
• Repetă.

Acesta este de asemenea cunoscut ca Monkey Shakespeare³: o maimuță generează aleatoriu caractere dintr-un alfabet, încercând să reproducă o secvență prestabilită de $ n $ caractere. Presupunem un alfabet cu $ m $ simboluri echiprobabile și un mecanism de resetare strictă: fiecare caracter greșit șterge întregul progres acumulat, readucând procesul în starea inițială $ S_0 $.

La fiecare poziție, probabilitatea de a genera caracterul cerut este $ p_k = 1/m $. Înlocuind această valoare în soluția generală obținută prin metoda Bellman, rezultă:

V_0 = \sum_{k=0}^{n-1} m^{k+1} = m \left( \frac{m^n - 1}{m - 1} \right) = \frac{m}{m-1}m^n - \frac{m}{m-1}

Rezultă o proprietate matematică surprinzătoare. Pentru un alfabet de 27 de caractere ($ m = 27 $), factorul multiplicativ tinde către: $ \frac{m}{m-1} = \frac{27}{26} \approx 1.03846$

Paradoxul: Intuitiv, un mecanism de resetare strictă pare extrem de ineficient. Un singur caracter greșit șterge întregul progres acumulat, obligând procesul să o ia de la capăt. Ne-am putea aștepta ca aceste eșecuri repetate să introducă un timp suplimentar considerabil de așteptare.

Totuși, soluția în formă închisă ne arată altceva. Raportat la scara de referință $ m^n $, timpul mediu de așteptare tinde către un factor de numai $ 1.03846 $⁴. Cu alte cuvinte, mecanismul de resetare adaugă un cost suplimentar de doar 3.85%, chiar dacă secvența-țintă crește de la 20 la 200 de caractere.

Mai precis, costul suplimentar relativ este:

\frac{V_0}{m^n} - 1 = \frac{1-m^{1-n}}{m-1}

Pe măsură ce $ n $, termenul $ m^{1-n} $ tinde către zero, iar costul suplimentar converge către:

\lim_{n\to\infty}\left(\frac{V_0}{m^n}-1\right) = \frac{1}{m-1} = \frac{1}{26} \approx 3.85\%

Rezultatul este contraintuitiv: deși fiecare eșec distruge întregul progres acumulat, costul așteptat al acestor resetări rămâne remarcabil de mic în raport cu scara de referință, care crește exponențial.

Totuși, valoarea așteptată nu spune întreaga poveste. Dacă impunem o probabilitate de succes de 99.5%, trebuie să examinăm coada superioară a distribuției timpului de așteptare. Pentru valori mari ale lui $ n $, timpul de așteptare este aproximativ distribuit exponențial. Prin urmare, cuantila de 99.5% este⁵:

Q_{99.5\%} \approx -\ln(0.005)·V_0 \approx 5.2983·V_0

Combinând acest rezultat cu timpul mediu de așteptare, obținem:

Q_{99.5\%} \approx 5.5021·27^n

Cu alte cuvinte, în timp ce timpul mediu de așteptare depășește cu doar aproximativ 3.85% valoarea de referință, atingerea unei probabilități de succes de 99.5% necesită un timp de aproximativ 5.5 ori mai mare decât aceasta.

O comparație Link spre

Putem aplica același raționament mai multor experimente aleatoare. Prezentăm mai jos atât timpul mediu de așteptare, cât și cuantila de 99,5% (SCR).

Concluzie Link spre

Probabilitatea de a reproduce întreaga secvență din prima încercare nu este doar o măsură a dificultății inițiale. Inversul acestei probabilități oferă un reper natural pentru numărul mediu de încercări necesare, dar nu surprinde întotdeauna timpul efectiv de așteptare, care depinde de structura experimentului și de modul în care eșecurile afectează progresul.

Paradoxal, abaterea dintre acest reper și timpul mediu efectiv poate fi foarte diferită de la un experiment la altul. În cazul HH, estimarea bazată pe reușita din prima încercare subevaluează timpul mediu cu 50%: în loc de 4 aruncări, avem nevoie în medie de 6. Totuși, dacă am continua secvența până la HHHHHHHH, aceeași abordare ar supraestima mult mai puțin timpul efectiv. Iar când numărul de rezultate posibile crește, abaterea devine și mai mică: pentru un alfabet de 27 de caractere, ea rămâne sub 3,85%, indiferent de lungimea secvenței.

Ceea ce pare imposibil de realizat din prima nu este atât de departe de a fi realizat, în cele din urmă.⁷ Chiar și când ținta este o operă întreagă, eșecul primei încercări adaugă surprinzător de puțin la timpul mediu de așteptare global. Nu primul pas trebuie să fie perfect⁸; important este să înțelegem cât ne costă, în ansamblu, să o luăm de la capăt până reușim.

În plus, media nu este suficientă pentru a caracteriza riscul. Cuantila de 99,5% arată cât de mult poate depăși timpul de așteptare valoarea medie și oferă o perspectivă diferită, esențială pentru dimensionarea capitalului și evaluarea riscului extrem.

Acest mod de gândire definește esența matematicii actuariale, în special prin teoria credibilității. Nu trebuie să știi totul. Trebuie să știi ce să întrebi, de la ce condiții inițiale să pornești, ce să verifici și cui să încredințezi problema.

Autorul declară că nu există interese financiare sau relații personale care ar fi putut influența conținutul și concluziile acestui articol.

@online{Cornaciu2026HH,
  author   = {Cornaciu, Valentin},
  orcid    = {0000-0001-9239-7145},
  title    = {Cap la cap},
  year     = {2026},
  date     = {2026-11-10},
  url      = {http://rcor.ro/ro/posts/2026-10-31-two-heads-in-a-row/},
  abstract = {Articolul analizează problema aruncării repetate a unei monede corecte 
  până la apariția a două capete consecutive. Folosind principiul optimalității al 
  lui Bellman, deduce timpul mediu de așteptare printr-un model bazat pe tranziții 
  între stări și explorează întreaga distribuție a timpului de așteptare. Analiza
  conectează programarea dinamică, relațiile de recurență și șirul lui Fibonacci, 
  ilustrând modul în care același proces poate fi înțeles atât din perspectiva valorii
  așteptate, cât și din cea a distribuției. De asemenea, examinează mecanismul de 
  resetare din experimentul Monkey Shakespeare, arătând că eșecurile repetate pot adăuga
  doar un cost relativ redus timpului mediu de așteptare. Distincția dintre performanța 
  medie și riscul de coadă evidențiază importanța alegerii măsurii potrivite pentru 
  evaluarea proceselor stocastice.}
}