Urmând calea onestă

Vom aborda problema potrivirii unice cu ale sale variante — o metaforă clasică pentru decizie, informație și raționalitate limitată.

Deși preocupări apropiate apar încă din secolul XVIII, când Abraham de Moivre tratează probleme de probabilitate în The Doctrine of Chances De Moivre (1718), el nu formulează în mod direct problema potrivirii în această manieră. În literatura algoritmică, operații structurale similare apar mai târziu: Quicksort Hoare (1961) rezolvă, printr-o strategie de tipul divide et impera, subprobleme ce rezonează cu logica potrivirii perechilor; ulterior, aceeași idee este folosită (și adaptată) pentru a aborda problema denumită în literatura de specialitate nuts and bolts Alon et al. (1994).

Problema potrivirii unice — în cele mai simple instanțe reprezentată de cazul cu 4 uși și 4 chei — oferă un cadru minimal pentru analiza proceselor decizionale în condiții de informație incompletă. Chiar și în această simplificare extremă persistă întrebări teoretice relevante: ce înseamnă, formal și operațional, că un algoritm este „mai eficient”? și în ce sens un algoritm „mai inteligent” poate eșua în termeni de cost total sau de efort resimțit de agent?

Această istorie ilustrează două observații metodologice importante. În primul rând, conexiuni conceptuale între domenii — aici, între teoria probabilităților clasice și analiza algoritmică — pot oferi perspective noi asupra unei probleme aparent simple. În al doilea rând, optimizarea după un singur criteriu (de exemplu, timpul de execuție) nu garantează optimalitate în termeni decizionali multidimensionali (de exemplu, cost cognitiv, număr de comparații experimentale, sau robustețe la erori de percepție).

Formularea academică:

Date fiind n uși și n chei, iar fiecare cheie deschide o singură ușă, trebuie să determinăm numărul minim de încercări necesar pentru a deschide toate ușile.

Notă: Această formulare se concentrează pe deschiderea efectivă a ușilor, nu pe aflarea bijecției exacte dintre chei și uși.

În articolul de față vom compara mai multe strategii de rezolvare – de la încercarea sistematică la alegerea aleatorie controlată – pentru a arăta că, indiferent de metodă, există o limită structurală a eficienței. Această limită nu ține de noroc, ci de simetria informației.

Soluția clasică Link spre

Începem cu prima ușă și încercăm cheile până găsim cea potrivită; apoi trecem la următoarea ușă și repetăm, eliminând cheia folosită. În cel mai rău caz, algoritmul garantează că se efectuează cel mult $ \frac{n(n+1)}{2} $ încercări.

Această metodă pare trivială și garantată, dar nu obligatoriu optimă; sigur există alte strategii care garantează că se efectuează maxim $ \frac{n(n+1)}{2} $ încercări.

Problema devine: cum putem demonstra că nu se poate găsi o strategie mai bună? Adică una care, la un anumit nivel de semnificație, ar necesita un număr mai mic de încercări pentru a deschide toate ușile.

Principiul folosit Link spre

Pentru a arăta că nu există o metodă mai optimă decât cea clasică, vom folosi Principiul de optimalitate al lui Bellman (Bellman’s principle of optimality).

Definim V(k) = numărul optim de încercări rămase atunci când tocmai am deschis k uși și urmează să încercăm să deschidem o nouă ușă dintre cele n - k rămase. Sigur, $ V(0) $ e maxim, iar $ V(n)=0$.

Astfel $ V(0) $ devine soluția globală pentru a rezolva problema:

 V(0) = \sum_{t=0}^{n} \min_{a_t \in \Gamma(x_t)} 
  c(x_t, a_t)\tag{1}

Fie starea inițială $ x_0 $ și mulțimea de acțiuni posibile $ \Gamma(x_0) $. Alegem o acțiune optimă $ a_0 \in \Gamma(x_0) $, iar starea următoare se obține prin funcția de tranziție: $ x_1 = T(x_0, a_0) $

Funcția de valoare asociată este:

V(x_0) = \min_{a_0 \in \Gamma(x_0)} 
  c(x_0, a_0) + \mathbb{E}\big[\, V(x_1) \mid x_0 \overset{a_0}{\to} x_1 \,\big]\tag{Bellman}

unde avem constrângerile,

• $ \mathbb{E}[ V(x_1) \mid x_0 \overset{a_0}{\to} x_1] $ reprezintă valoarea așteptată a stării următoare, condiționat de $ a_0 \in \Gamma(x_0) $

• $ c(x_0, a_0) $ reprezintă costul marginal asociat alegerii acțiunii $ a_0 $ în starea $ x_0 $ – constant cu 1 pentru că vrem să numărăm încercările. Atenție, nu reprezintă costul total de la trecerea $ x_0 \overset{a_0}{\to} x_1 $

• Când alegem costul marginal $ c(x_0,a_0) = 1 $ pentru fiecare încercare, funcția de valoare asociată $ V(x_0)$ măsoară numărul maxim de încercări garantat pentru a deschide toate ușile pornind din starea $ x_0$.

• Dacă am pune prețul corect marginal mediu, per încercare, care ar susține trecerea completă $ x_0 \overset{a_0}{\to} x_1$, anume $ c(k<n-1, a_k) = \frac{n-k+1}{2} \cdot \frac{1}{n-k}$; $ c(n-1, a_{n-1}) =1$ funcția de valoare ar găsi numărul așteptat de încercări.

• Aici alegem o acțiune inițială, notată prin $ a_0 $, știind că alegerea noastră determină starea sistemului în momentul următor, $ x_1 = T(x_0, a_0) $ cât și probabilitatea de tranziție.

Dacă procesul Markov indus de acțiunea fixă $ a_0 $ are nucleul de tranziție discret $ p_{a_0}(x’ \mid x_0) $ pe spațiul de stări $ \mathcal{S} $, atunci

 \mathbb{E}\big[\, V(x_1) \mid x_0 \overset{a_0}{\to} x_1 \,\big]
= V(x_0)\, p_{a_0}(x_0 \mid x_0) + V(x_1)\, p_{a_0}(x_1 \mid x_0)\tag{2} 

La fiecare pas (încercare):

• facem o încercare (cost fix 1);
• cu probabilitatea $ \dfrac{1}{n-k} $ reușim → trecem la starea următoare $ V(k+1)$;
• cu probabilitatea $ 1 - \dfrac{1}{n-k}$ nu reușim → rămânem în aceeași stare $ V(k)$.

Din aceste observații rezultă ecuația Bellman pentru $ V(k) $:

V(k) = 1 + \frac{1}{n-k} V(k+1) + \left(1 - \frac{1}{n-k}\right) V(k)

Verificarea aplicabilității Link spre

Pentru a aplica corect Principiul de optimalitate al lui Bellman, trebuie să fie îndeplinite următoarele ipoteze:

1. Structură secvențială — problema poate fi împărțită în etape succesive

   
   x_0 \to x_1 \to \dots \to x_T 
   

   fiecare etapă având o decizie $ a_t $ care influențează starea viitoare.

2. Sistem fără memorie — contează doar unde ești acum și ce faci, nu cum ai ajuns acolo.

   
   P(x_{t+1} \mid x_t, a_t, x_{t-1}, \dots) = P(x_{t+1} \mid x_t, a_t)
   

3. Aditivitatea funcției de cost/recompensă — obiectivul total este suma costurilor pe etape.

4. Independența deciziilor viitoare — pentru o stare $ x_t$, deciziile ulterioare pot fi optimizate independent de trecut, presupunând comportament optim de la acel punct înainte:

   
   V(x_t) = \min_{a_t \in \Gamma(x_t)} \left[ c(x_t, a_t) + \mathbb{E}\big( V(x_{t+1}) \mid x_t, a_t \big) \right]
   

5. Relație recursivă bine definită — problema trebuie să permită formularea unei ecuații de tip Bellman care exprimă valoarea optimă într-un pas în funcție de valorile viitoare.

6. Consistență în dinamică — deciziile considerate optime azi rămân optime și pe măsură ce timpul avansează și noile date apar.

7. Determinare completă a stării — variabila de stare $ x_t $ conține toată informația relevantă pentru luarea deciziei optime; dacă starea e incompletă, principiul nu mai este valabil.

Scop practic: înainte de aplicare, se verifică dacă modelul decizional respectă aceste condiții — în special condiția de lipsă de memorie și aditivitatea funcției de cost.

Dacă sunt îndeplinite, atunci principiul garantează că soluția optimă globală poate fi obținută prin soluții optime locale. ⚠️ Limitare crucială: Principiul Bellman nu se aplică pentru măsuri neaditive (ex.: percentile, varianță, SCR).

Pentru a depăși aceste limite avem nevoie de:

Soluția actuarială Link spre

Dacă ne concentrăm asupra modului optim de a deschide prima ușă (încercăm chei până deschide efectiv o ușă), după efectuarea acestei alegeri, problema devine ulterior independentă pentru etapa următoare. Această proprietate garantează că putem suma unic variabilele aleatoare corespunzătoare fiecărei etape. Prin urmare, notând RV(1:n) variabila aleatoare definită pe suportul echiprobabil 1:n, putem determina:

1 + RV(1:2) + RV(1:3) + RV(1:4)⏎ 
════════════════════════════════
Variabilă aleatoare cu |7⟩ evenimente, (µ = 7 | σ = 1.47), entropia 1.78
──
ᴿᵢ    4    5    6    7    8    9   10
ᵖᵢ 1/24  1/8 5/24  1/4 5/24  1/8 1/24

Pentru $ n=12$ avem $ 12! $ variante posibile și deci un număr imens de permutări, totuși:

1+RV(1:2)+RV(1:3)+RV(1:4)+RV(1:5)+RV(1:6)+RV(1:7)+RV(1:8)+RV(1:9)+RV(1:10)+RV(1:11)+RV(1:12)⏎ 
═════════════════════════════════════════════════════════════════════════════════════════════
Variabilă aleatoare cu |65⟩ evenimente, (µ = 45 | σ = 7.29), entropia 3.4
──
ᴿᵢ           41           42           43           44           45           46           47           48           49
ᵖᵢ   3088/66297   3463/69999    958/18551   3491/65886 33969/635639   3491/65886    958/18551   3463/69999   3088/66297

ℹ Se afișează primele 9 valori importante cu extremele [13:77], VaR(99.5%) = 63.

Astfel, nu doar că putem determina numărul de încercări necesar pentru a garanta deschiderea fiecărei uși, dar putem și evalua probabilitatea exactă de a deschide toate ușile din întregul spectru posibil.

Așadar, chiar și cu 12 chei/12 uși, cel mai probabil vom deschide toate ușile în aproximativ 45 de încercări; la un nivel de încredere de 99.5%, numărul de încercări necesar urcă la 63. Deschiderea sigură are loc abia la 77 de încercări, însă vom ajunge în acea situație cu o probabilitate extrem de mică, de doar 1/12! = 1/479,001,600. Tot atât de probabil e să deschidem toate ușile din 12 încercări, întrucât variabila aleatoare are o distribuție simetrică.

Pentru $ n $, suma nu este alta decât distribuția mahoniană Canfield, Janson, and Zeilberger (2011) deplasată cu $ +n $, ceea ce reflectă acumularea progresivă a efortului în funcție de ordinea în care sunt potrivite cheile.

În concluzie,

Principiul de optimalitate nu poate determina acțiunea optimă de urmat — inclusiv probabilitățile asociate tranzițiilor — dar ne asigură că nu trebuie să căutăm soluția optimă pentru întregul proces dinamic. Este suficient să găsim decizia optimă pentru fiecare etapă, deoarece o soluție globală optimă este formată din decizii locale optime. Principiul nu îți spune ce să faci, ci cum arată o soluție optimă.

Referințe Link spre