169. feladványunkban Brian munkába menet a lehető legmegjósolhatatlanabb módon akart folytatni egy + és - jelekből álló bináris sorozatot. Brian meghatározása erre a következő. Vesszük a sorozat legvégéről a lehető leghosszabb szakaszt, amit a teljes sorozat legalább még egy másik helyen tartalmaz, azaz előfordult már benne a szóban forgó szekvencia. Ezután megnézzük, hogy ez után a szakasz után a korábbi előfordulásai alkalmával milyen jel volt a rákövetkező, és megszámoljuk, hogy hányszor volt + jel a szóban forgó szakasz után (mondjuk N1-szer), és hányszor következett utána - jel (legyen N2 ilyen hely). A megfigyelt gyakoriságokból ezután valószínűségeket kreálunk: p1 = N1/(N1+N2), p2 = N2/(N1+N2). p1 tehát annak a valószínűsége, hogy eddig mekkora valószínűséggel következett + jel ilyen szekvenciák után, p2 pedig annak a valószínűsége, hogy eddig mekkora valószínűséggel következett - jel ilyen szekvenciák után.

Brian azt szeretné, hogy a statisztikák megfigyelésével a sorozat következő elemét ne lehessen megtippelni, de persze determinisztikusan sem szeretné folytatni. Ezért azt csinálja, hogy a két valószínűséget egyszerűen megcseréli, és ezek alapján sztochasztikusan generálja a sorozat következő tagját. A sorozat következő tagjának kiszámolása előtt tehát mindig kiszámolja p1 és p2 értékét, és p1 valószínűséggel - jelet ír (hazafelé utazik az eredeti történet szerint), illetve p2 valószínűséggel + jelet ír (a munkahely irányába utazik) a sorozat folytatásaként.

Brian sorozatának első tíz tagja meg volt adva, vagyis tudjuk, hogy a sorozat így indul: + + + + + - + + - +. A kérdés az volt, hogy mi a valószínűsége annak, hogy tíz további lépésen belül Brian eléri a végállomást, ami annak felel meg, hogy tíz további taggal bővítve a sorozatot lesz olyan tag, hogy addig a tagig tekintve a sorozatot abban tízszer több + jel szerepel, mint ahány - jel.

Megoldás

A megoldás menete: felírjuk a következő tíz lépés lehetséges kimeneteleinek valószínűségeit, majd összegezzük azokat, amikre teljesül a fenti feltétel, azaz Brian eléri a munkahelyét. A sorozat lehetséges folytatásainak száma természetesen lépésenként duplázódik, és a valószínűségeket is lépésenként kell számolnunk. Az elméletileg lehetséges folytatások száma 2^10 = 1024, de szerencsére nem kell ennyi esetet végignézni, mert gyakran előfordul, hogy N1 vagy N2 zérus, és ilyenkor p1 vagy p2 is zérus, azaz a folytatás ebben a speciálisan esetben determinisztikus.

Például rögtön a 11. és 12. tagja a sorozatnak egyértelmű. Nézzük, miből következik ez. Vennünk kell a sorozat legvégéről a lehető leghosszabb szakaszt, amit a teljes sorozat legalább még egy másik helyen tartalmaz, ez az első lépésben (amikor a 11. tagot szeretnénk meghatározni) a sorozat végén lévő - + szekvencia lesz, mert a hosszabb + - + az már sehol máshol nem fordul elő. A - + szekvencia viszont csak egy helyen fordul elő, és ott + jel követi, ezért most biztosan - jelnek kell követnie a valószínűségek megcserélése miatt.

Leírva a - jelet a sorozatunk végére, most a 12. tagot szeretnénk generálni. Ehhez megint vennünk kell a (most már meghosszabbított) sorozat legvégéről a lehető leghosszabb szakaszt, amit a teljes sorozat legalább még egy másik helyen tartalmaz. Ez jelen esetben a + - szekvencia lesz, mert a hosszabb - + - az nem szerepel máshol a sorozatban. A + - szekvencia most viszont két helyen is szerepel, ellenben mindkét helyen + követi, ezért a folytatás ugyanúgy meghatározott, mint az előbb, tehát a 12. tag is - kell legyen.

Az első elágazás a 13. tagnál lesz. Ha most megkeressük a sorozat legvégéről a lehető leghosszabb szakaszt, amit a teljes sorozat legalább még egy másik helyen tartalmaz, ez most szimplán az egy hosszú - szekvencia lesz, mert - - máshol nem szerepel. A - jelet viszont két helyen követi + jel, és egy helyen - jel (éppen a végén), ezért a folytatás 1/3 valószínűséggel + lesz, és 2/3 valószínűséggel - jel.

Ha ezt így folytatjuk, akkor szerencsénk lesz, mert az elméletileg lehetséges 1024 eset közül végül is csak 19 eset, azaz sorozat lehetséges, amit végig kell nézni, és ezek közül is csak három lesz az, amik teljesítik a feladat feltételeit. Az egyes sorozatokhoz tartozó valószínűségeket pedig úgy kapjuk, ha összeszorozzuk a sorozat nem determinisztikus lépéseiben az adott sorozatot folytató + vagy - jelhez tartozó valószínűségeket.

Összességében azt kapjuk, hogy az említett három lehetséges sorozat, amivel Brian beérhet a munkahelyére, az alábbi lehet:

Tíz lépésből 1/36 valószínűséggel: +++++-++-+---+++++++.

Tíz lépésből 1/72 valószínűséggel: +++++-++-+--+-++++++.

Vagy nyolc lépésből 1/36 valószínűséggel: +++++-++-+--++++++.

Így összesen tíz lépésen belül 5/72, azaz körülbelül 7% eséllyel ér be dolgozni. Előbb-utóbb egyébként mindenképpen beér valahova, vagy a munkahelyére, vagy haza. A leghosszabb útvonal az alábbi:

+++++-++-+--+-+++---++++--++--+-----+--+++-+-+-++----++-+++++++------+++--+-+---+-++-++--+++++--+--+--++-+-++++-+----+-+-+--++---+---++--++-++-+++-+++--+++----+----++++++-+-++-+-+--------+-+++++-++++---+-+--+---+--+-+-+++-+--++++-++---++-+---+++-++--+-++--++-----++---+++---+--++--+++-+++++---++----+-++---+-+++-++-++-+-++--+--+++++

Legkorábban pedig 38 állomásnyi utazással, azaz 28 plusz lépésben, 8:34-re érhet haza, mégpedig az alábbi tizenegy különböző lehetőség valamelyike szerint.

• +++++-++-+--++++---+-+++--+----++-----
• +++++-++-+--++++---+-+++--+-----++----
• +++++-++-+--+++---+-++++--+----++-----
• +++++-++-+--+++---+-++++--+-----++----
• +++++-++-+--+-++++---+++--++----+-----
• +++++-++-+--+-++++---+++--++-----+----
• +++++-++-+--+-++++----+++-+-+---+-----
• +++++-++-+--+-++++----+++--++---+-----
• +++++-++-+--+-+++---++++--++----+-----
• +++++-++-+--+-+++---++++--++-----+----
• +++++-++-+--+-+++----++++--++---+-----

Kapcsolódó cikk a Qubiten: