Cím:	,,Kínai étterem" - a véletlen permutációkról 2.
Szerző(k):	Surányi László
Füzet:	2018/november, 454 - 462. oldal	PDF  |  MathML

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   ,,Kínai étterem'' ‐ a véletlen permutációkról 2.     2.2 A ,,kínai étterem folyamat'' (Chinese restaurant process) Most már rátérhetünk a címben szereplő témánkra. Hogyan értjük, hogy a tanulók véletlen sorrendben érkeznek? Vagy általánosabban: hogyan modellezhetjük a ,,véletlen permutációkat''? Nyilván sokféleképpen képzelhetjük el az előbbit, de talán még szemléletesebb, ha a ,,karácsonyi ajándékozásra'' gondolunk. Itt minden tanuló nevét bedobják egy kalapba, jól összekeverik, majd a tanulók egyesével kihúznak egy-egy nevet. Ha itt a sorsolás véget is érne, akkor ez egy jó modell lenne a véletlen permutációra. Azonban a karácsonyi ajándékozásnál vigyázni kell arra is, hogy senki ne húzza önmagát. Ennyiben tehát nekünk nem jó szemléltetés, maradunk az eredetinél, amikor meg van engedve, hogy egyesek önmagukat húzzák. Ez a modell jó, előállít egy véletlen permutációt ‐ de van vele egy probléma. Ha pl. kiderül, hogy valakit még meg akarnak hívni az osztálykarácsonyra, akkor az egész sorsolást elölről kell kezdeni. A modell nem ,,dinamikus''. És persze a ciklusok sem fognak közvetlenül látszani. A ciklus-szerkezet és az újrakódolás alapján azonban (lásd a 4. feladat megoldását) lehet dinamikus modellt is csinálni ‐ ez lesz az úgynevezett ,,Kínai étterem folyamat'' (Chinese restaurant process). A továbbiakhoz érdemes megjegyezni, hogy vélhetően honnan a folyamat neve. Talán onnan, hogy úgy képzeljük: a kínai vendéglőben egy-egy asztal körül praktikusan végtelen sokan ülhetnek, és bármely két vendég széke közé le lehet tenni még egy széket. Tekintsük egy $n$ elemű permutáció újrakódolt alakját. Gondoljuk embereknek a permutáció elemeit, a számuk azt jelzi, hányadikként érkeztek a vendéglőbe. Az első ‐ az 1-gyel véget érő ‐ ciklus tagjait ültessük az első asztalhoz abban a sorrendben, ahogy a ciklusban jönnek. A második ‐ az első asztalhoz le nem ültetettek közül a legkisebb sorszámúval véget érő ‐ ciklus tagjait ültessük a második asztalhoz, szintén a ciklus sorrendjében, és így tovább. Tegyük fel, hogy van már egy eljárásunk, amely minden újrakódolt permutációt ugyanolyan $\left(\frac{1}{n!}\right)$ valószínűséggel állít elő. Megérkezik az új vendég, fogja a székét és le akar ülni valamelyik asztalhoz, vagy új asztalt is kezdhet. Olyan ‐ természetesen a véletlenen alapuló ‐ utasítást akarunk neki adni, amellyel elérhető, hogy minden $n+1$ elemű permutáció újrakódolt alakja is egyenlő valószínűséggel ,,valósuljon meg''. Hogy mit akarunk, azt pontosabban a következő ‐ a középponti kérdésről lévén szó ez alkalommal szám nélküli ‐ feladatban fogalmazzuk meg.   Feladat. Tegyük fel, hogy az újonnan érkező vendégnek van egy véletlen szám előállítója. (Mondjuk egyenletes eloszlással forgat körbe egy $n+1$ csúcsú szabályos sokszöget.) Milyen valószínűséggel üljön az egyes asztalokhoz a székével, hogy most minden $n+1$ elemű újrakódolt permutáció ugyanolyan valószínűséggel álljon elő, ha azt látja, hogy az $i$-edik asztalnál $a_i$ számú ember ül?   Megoldás. Tippelhetnénk arra, hogy valahogy úgy kell a valószínűségeket választani, hogy az egyes asztalnál ülők száma ne nagyon térjen el egymástól. De ez nem jó tipp. Azt kell ugyanis elérnünk, hogy kijelölve mondjuk a ,,balra tarts'' irányt, az új vendég bármely asztalnál ülőtől balra egyforma valószínűséggel üljön le és ugyanilyen valószínűséggel kezdjen új asztalt. Ez összesen $n+1$ helyet jelent, tehát mindegyik helyre $\frac{1}{n+1}$ valószínűséggel kell leülnie.   Tehát az $i$-edik asztalhoz $\frac{a_i}{n+1}$ valószínűséggel ül le, új asztalt $\frac{1}{n+1}$ valószínűséggel kezd. (Vagyis úgy vesszük, hogy az első üres asztalnál egy hely van). Ez a választás jó, ugyanis azt jelenti, hogy az $n$ elemű véletlen permutáció újrakódolt alakjának bármely két eleme közé, illetve az elejére vagy a végére ugyanolyan valószínűséggel tesszük az $n+1$ számot. Tehát ha az $n$ elemű véletlen permutációk egyforma valószínűséggel álltak elő, akkor valóban egyenlő valószínűséggel áll elő minden $n+1$ elemű permutáció is. Ez lesz tehát a   ,,Kínai étterem folyamat'' (KÉF). Az első vendég leül az első asztalhoz. A második vendég $1/2$‐$1/2$ valószínűséggel ül az első vendég mellé, vagy kezd új asztalt. Ezután az $n$-edik új vendég $\frac{a_i}{n}$ valószínűséggel ül az $i$-edik asztalhoz, ha ott érkezésekor $a_i$ számú ember ül, illetve $\frac{1}{n}$ valószínűséggel kezd új asztalt. (Az $i$-edik asztalnál $a_i$ helyre ülhet, az üres asztalnál egy hely van.) Beláttuk, hogy ez a modell minden azonos elemszámú permutációt ugyanolyan valószínűséggel állít elő. A leírt folyamat eredménye a véletlen permutációk egy dinamikus modellje. Dinamikus, mert az új ember érkezésekor nem kell mindent elölről kezdenünk, mint a karácsonyi sorsolásnál. A KÉF erejét szemlélteti az, amilyen egyszerűvé válik segítségével a 3. feladat meg-oldása (de lásd a következő feladatok megoldását is):   7. feladat*.${}^1$ 1 Adjunk választ a KÉF segítségével arra a kérdésre, hogy milyen valószínűséggel lesz $n$ elem egy véletlen permutációjában két előre kijelölt elem azonos ciklusban? (A $3$. feladat ,,nyelvén'' megfogalmazva: Mi a valószínűsége annak, hogy valamelyik (előre kijelölt) másik helyen, például az első helyen ülő tanulónak is fel kell állnia?)   2.3. További kérdések a véletlen permutációk ciklus-szerkezetéről Folytathatjuk is a kérdezést. Megkérdezhetjük például a következőket: Mi a valószínűsége annak, hogy az első és a második helyen ülő tanulónak is fel kell állnia? És mi a valószínűsége annak, hogy mindkettő megússza, hogy fel kelljen állnia? A következő két feladat általánosságban veti fel ezeket a kérdéseket. Az elsőre adott megoldások mindegyike egészen más szemlélet alapján közelíti meg a feladatot. Így összehasonlíthatjuk a kombinatorikus-számolós, a csoportelméleti-kódolós és a valószínűségi szemléletmódot.   8. feladat. Mi a valószínűsége annak, hogy a $3$. feladatban nemcsak az $n$-edik helyen ülőnek, hanem még $s-1$ (előre kijelölt) másik helyen ülő ember mindegyikének fel kell állnia? (Értelemszerűen az $n$ helyen ülőt már nem választhatjuk ki.) Kissé átfogalmazva a kérdést: Mi a valószínűsége annak, hogy összesen $s$ előre kijelölt helyről fel kell állnia az ott ülőnek? És a permutációk nyelvén megfogalmazva: Mi a valószínűsége annak, hogy $n$ elem egy véletlen permutációjában előre kijelölt elem egy ciklusban lesz?   1. megoldás számolással. A kérdés megválaszolására alkalmazható a 3. feladat első megoldásának a gondolatmenete. A számolás áttekinthetősége érdekében a számolást az $s=4$ esetben hajtjuk végre. Megint jelölje $k$ azt, hogy hány ember áll fel összesen. Ezek közül $k-4$ választható szabadon az $n-4$ további ember közül, ezt $\left(\genfrac{}{}{0ex}{}{n-4}{k-4}\right)$-féleképp tehetjük meg. A $k$ ember ismét $\left(k-1\right)!$-féleképpen alkothatja a ciklust, a maradó $n-k$ ember pedig bármilyen sorrendben ülhet a maradó $n-k$ helyen, ez egy $\left(n-k\right)!$-os szorzó. Összességében ez $\left(n-4\right)!\left(k-1\right)\left(k-2\right)\left(k-3\right)=6\left(n-4\right)!\left(\genfrac{}{}{0ex}{}{k-1}{3}\right)$ lehetőséget jelent, és ezt kell minden $k=\mathrm{4,5,}\text{...}\mathrm{,}n$-re összeadni. Felhasználjuk, hogy $\begin{array}{c}{\displaystyle \sum _4^n\left(\genfrac{}{}{0ex}{}{k-1}{3}\right)=\left(\genfrac{}{}{0ex}{}{n}{4}\right)\mathrm{,}}\end{array}$ így az összeg $6\left(n-4\right)!\left(\genfrac{}{}{0ex}{}{n}{4}\right)=\frac{n!}{4}$. Tehát a keresett valószínűség $1/4$. Az általános esetben a $\begin{array}{c}{\displaystyle \sum _s^n\left(\genfrac{}{}{0ex}{}{k-1}{s-1}\right)=\left(\genfrac{}{}{0ex}{}{n}{s}\right)}\end{array}$ összefüggést kell használni, és a keresett valószínűség $1/s$.   Megjegyzés. A 3. feladat második megoldása közvetlenül nem általánosítható. A harmadik megoldásból viszont, amely az ,,újrakódolást'' használja, gyorsan kiolvasható a válasz.   2. megoldás az ,,újrakódolás'' segítségével. Először tisztázzuk a következőt. Nyilván elég azt vizsgálnunk, hogy mi a valószínűsége annak, hogy az utolsónak érkező tanulóval együtt másik $s-1$, előre kijelölt helyen ülőnek is fel kell állnia. Az is nyilvánvaló, hogy nem változtat a valószínűségen, ha ehelyett azt vizsgáljuk, hogy nem az utolsó, hanem az elsőnek érkező ‐ tehát az első helyen ülő ‐ tanuló kezdi a felállást és másik, előre kijelölt helyen ülő $s-1$ tanulónak kell még felállnia. És ez könnyen lefordítható az újrakódolás segítségével. A megfelelő permutáció újrakódolt alakjánál ugyanis ez azt jelenti, hogy a kijelölt $s-1$ helynek a sorszámai mind előbb jönnek az 1-nél. Vagyis a kérdés a permutációk nyelvén a következőre egyszerűsödik: Mi a valószínűsége, hogy az első n szám egy véletlen permutációjának az újrakódolásánál előre kijelölt $s-1$ szám előbb jön az $1$-esnél? Most is csoportosítjuk az újrakódolt permutációkat. Két permutáció akkor kerül azonos csoportba, ha az 1-es és a másik $s-1$ kijelölt szám összességében ugyanazt az $s$ helyet foglalja el, másrészt a többi szám a két permutációban ugyanúgy helyezkedik el. Így minden egyes csoportba $s!$ permutáció kerül, hiszen az $s$ kitüntetett számot ennyiféleképpen lehet permutálni. És ezek közül nyilván $\left(s-1\right)!$ olyan van, ahol az 1 van az utolsó helyen, vagyis az $s-1$ kijelölt szám után. A válasz tehát 1/$s$. És az eredeti kérdésre visszatérve megint azt kaptuk, hogy a permutációk $1/s$-ed részében fog mind az $s$ kijelölt helyen ülő tanulóra sor kerülni. A permutációkra vonatkozóan a következőt kaptuk:   Tétel. Annak a valószínűsége, hogy $n$ elem egy véletlen permutációjában előre kijelölt $s$ elem egy ciklusban van, $1/s$.   Megjegyzés a fenti 2. megoldáshoz. Ez a megoldás nyilván elegánsabb az előző megoldásnál. Viszont ugyanaz a fogalmi nehézség van benne, amire az újrakódolásnál már utaltunk. Elvileg hasonló fogalmi nehézség van a következő megoldásnál is, de a KÉF szemléletessége miatt ez könnyebben ,,fogható''. Ráadásul a megoldás a 7. feladat megoldásának az általánosítása.   3. megoldás a ,,kínai étterem folyamat'' segítségével. A kimondott tételre adunk egy új bizonyítást. Tudjuk, hogy a ,,kínai étterem folyamat'' során az $n$ vendég minden permutációja ugyanolyan valószínűséggel áll elő. Ez viszont azt is jelenti, hogy nyugodtan feltehetjük, hogy az előre kijelölt $s$ elem az első $s$ szám, vagyis a KÉF nyelvén: az első $s$ vendég. A kérdés tehát erre egyszerűsödik: Mi a valószínűsége, hogy a ,,kínai étterem folyamat'' során az első $s$ vendég ugyanannál az asztalnál fog ülni? Minthogy az első vendég benne van, az a kérdés, hogy milyen valószínűséggel fog az utána érkező $s-1$ vendég mindegyike az ő asztalához ülni. A második vendég nyilván $1/2$ valószínűséggel ül az ő asztalához. Most már ketten ülnek ennél az asztalnál, így a harmadik vendég már $2/3$ valószínűséggel fog ehhez az asztalhoz ülni. Ugyanígy az $i$-edik vendég érkezésekor már $i-1$ ember ül ennél az asztalnál, tehát ő $\left(i-1\right)/i$ valószínűséggel fog oda leülni. A keresett valószínűséget úgy kapjuk, hogy ezeket az értékeket összeszorozzuk $i=\mathrm{2,3,}\text{...}\mathrm{,}s$-re. A szorzat, s így a keresett valószínűség $1/s$.   9. feladat. Mi a valószínűsége annak, hogy a $3$. feladatban $s-1$ előre kijelölt helyen ülő tanuló egyikének sem kell felállnia az utolsóval együtt? Vagy átfogalmazva: mi a valószínűsége annak, hogy elem egy véletlen permutációjában előre kijelölt $s-1$ elem egyike sincs egy előre kijelölt $s$-edikkel egy ciklusban?   Megoldás. Ez a valószínűség ugyanúgy kiszámolható, mint a 8. feladatban kérdezett valószínűség is kiszámolható volt. Az ott közölt második megoldás gondolata is alkalmazható ebben az esetben. Megint feltehető, hogy az az elem, amivel a többi nem lehet egy ciklusban, épp az 1-es. A permutációkat ugyanúgy csoportosítjuk, mint ott, és most az a kikötés, hogy a többi $s-1$ elem mindegyike az 1-es után jöjjön az újrakódolásnál. Megint minden csoportban $s$! permutáció van és közülük megint $\left(s-1\right)!$ teljesíti a kikötést. A keresett valószínűség most is $1/s$. Végül ugyanúgy, mint ott, most is alkalmazható a KÉF is. Most az a kérdés, hogy mi annak a valószínűsége, hogy az első után érkező $s-1$ vendég egyike sem ül az első asztalhoz. A második vendég $1/2$ valószínűséggel ül más asztalhoz, a harmadik vendég vagy a másodikkal ül egy asztalhoz, vagy új asztalt kezd, ennek $2/3$ a valószínűsége, és általában az $i$-edik vendég a számára lehetséges $i$hely közül bárhova ülhet, kivéve az első asztalához, ez egy helyet zár ki. Tehát $\left(i-1\right)/i$ annak a valószínűsége, hogy ő a kikötésünknek megfelelő helyre ül. Megint ezeket az értékeket kell összeszorozni és az eredmény ismét $1/s$. Tételként megfogalmazva a nyert eredményt:   Tétel. Annak a valószínűsége, hogy $n$ elem egy véletlen permutációjában $s-1$ előre kijelölt elem egyike sem lesz egy $s$-edik előre kijelölttel egy ciklusban, $1/s$.   10. feladat*. Mi a valószínűsége annak, hogy elemek egy véletlen permutációjában előre kijelölt elem mindegyike különböző ciklusban lesz?   Ismét alkalmazható mindhárom megoldás (lásd a függelékben), és a válasz a következő:   Tétel. Annak a valószínűsége, hogy n elem egy véletlen permutációjában s előre kijelölt elem mindegyike más ciklusban lesz, $1/s!$.   2.4. Várható ciklushossz és ciklusszám A ,,kínai étterem folyamat'' bevezetésénél már láttuk, rossz várakozás az, hogy a ciklusok hossza egyenletesen fog eloszlani. A KÉF modell ennek az ellenkezőjét mutatja: a ,,tipikus'' esetben a ciklusok nagysága egyáltalán nem lesz egyenletes. (Ez kiderül például a 9. feladatnál is.) Ha egy asztalnál a vendégek száma egyszer nagyobb a többinél, akkor onnantól kezdve nagyobb valószínűséggel fog ehhez az asztalhoz ülni a következő vendég, ami után megint még nagyobb valószínűséggel fog ideülni a következő stb. Ez persze még csak heurisztikus érv. De a következő fel-adatban ezt egy módon pontosan is megfogalmazzuk.   11. feladat. Várhatóan hány ember fog részt venni a $3$. feladat ,,forgásában'', ha az osztályban $n$ tanuló van? Vagy ugyanez az ,,éttermes'' megfogalmazásban: Az $n$-edik vendég érkezése után várhatóan hány ember fog ülni az első vendég asztalánál?   1. megoldás. Felhasználjuk, hogy a várható értékek akkor is összeadódnak, ha a változók nem függetlenek. Legyen $X_i$az a valószínűségi változó, amelynek értéke 1, ha az $i$-edik vendég az első asztalhoz ült, és 0, ha nem. (Vagyis $X_i$ az ,,$i$-edik vendég az első asztalnál ül'' esemény karakterisztikus változója vagy indikátora.) Az első asztalnál ekkor $X_1+X_2+\text{...}+X_n$ vendég fog ülni. Ennek a változónak a várható értékét keressük. Ez tehát megegyezik az egyes változók várható értékének az összegével. Az első változó mindig 1 (az első vendég az első asztalnál ül), a többi változó várható értéke $1/2$, hiszen ennyi a valószínűsége annak, hogy az $i$-edik vendég az első asztalnál ül. A keresett várható érték tehát $\left(n+1\right)/2$.   2. megoldás. A 8. feladat megoldása során megfogalmazott állítás alapján egy másik, gyorsabb bizonyítást is adhatunk ugyanerre. Ott láttuk, hogy minden 1 és $n$ közötti $k$-ra ugyanannyi, $1/n$ a valószínűsége annak, hogy az első asztalnál $k$ vendég ül. Így a várható érték $\sum _1^n\frac{k}{n}=\frac{n+1}{2}$.   Tétel. Az első $n$ szám egy véletlen permutációjában az $1$-et tartalmazó ciklus várható elemszáma $\left(n+1\right)/2$.   12. feladat*. Állításunk tehát azt mondja, hogy az első asztalnál ülők számának várható-értéke a vendégek számának felénél $1/2$-del több. Másrészt azt mondja, hogy bármely vendégre igaz, hogy ennyi az ő asztalánál ülő vendégek számának várható értéke. De lehetetlen, hogy két ‐ vagy pláne több ‐ asztalnál üljenek ennyien. Ha $A$ az első vendég asztalánál ülők száma, $B$ a második vendég asztalánál ülők száma, akkor e két valószínűségi változó mindegyikének $\left(n+1\right)/2$ a várható értéke, így összegük várható értéke $n+1$, több, mint a vendégek száma. Hogyan oldható fel ez az ellentmondás?   13. feladat*. Következik-e az előbb megfogalmazott tételből, hogy a legnagyobb ciklus várható elemszáma (a legfoglaltabb asztalnál ülő vendégek száma) is $\left(n+1\right)/2?$   Egy véletlen permutáció legnagyobb ciklusának várható értékét pontosan meghatározni nehezebb feladat. Ez Golomb-nak sikerült, aki 1964-ben bizonyította, hogy ha $M_n$ jelöli az $n$ elemű véletlen permutáció legnagyobb ciklusának várható értékét, akkor $M_n/n$ egy állandóhoz tart, amelynek értéke 0,624 329 9$\text{...}$, az úgynevezett Golomb‐Dickman-féle konstans. Nemcsak a legnagyobb ciklus várható hossza érdekes kérdés, hanem az is, hogy várhatóan hány ciklus van $n$ elem egy véletlen permutációjában. Ez számolással aránylag nehezen jön ki, a KÉF segítségével egyszerű. Jelöljük ugyanis $E\left(n\right)$-nel ezt a várható értéket. $E\left(1\right)=1$, $E\left(2\right)=3/2$ nyilvánvaló. Általában ha $E\left(n-1\right)$-et már ismerjük, akkor a KÉF szerint az érkező $n$-edik vendég $1/n$ valószínűséggel kezd új asztalt, azaz növeli a ciklusok számát. Tehát $E\left(n\right)=E\left(n-1\right)+1/n$. Ebből következik, hogy   Tétel. Egy $n$ elemű véletlen permutációban a ciklusszám várható értéke $\sum _1^n\frac{1}{n}$. A KÉF alkalmazása az alábbi feladattal lesz ,,kerek'':   14. feladat*. Bizonyítsuk be a KÉF segítségével is a $6$. feladat állítását, amely szerint annak a valószínűsége, hogy egy adott elem egy $n$ elemű véletlen permutációban pontosan $k$ elemű ciklusban van, $k$-tól függetlenül mindig $1/n$.   Befejezés Egyrészt szeretném még egyszer hangsúlyozni, hogy Gyenes Zoltánnal együtt gondoltuk át az itt leírtak legnagyobb részét. Remélhetőleg sikerült valamennyire érzékeltetni, hogy a ,,kínai étterem folyamat'' segítségével milyen jól szemléltethetők és kezelhetők a véletlen permutációk egyszerű tulajdonságai. Elegánsan szemlélteti pl. a ciklusszám várható értékét, de különösen frappánsnak tűnik ebből a szempontból a 7. feladat megoldása, valamint az utána következő három feladat hasonló megoldása. És érdemes megfontolni a következőt is. Ha a ,,kínai étterem folyamatot'' minden előzmény nélkül definiáljuk, és úgy kérdezzük meg, hogy vajon az első két vendég, vagy az utolsó kettő fog-e nagyobb valószínűséggel egy asztalnál ülni, akkor erre ‐ a háttér ismerete nélkül ‐ elég nehéznek látszik a válasz.   Függelék ‐ megoldások     5. feladat. Csak az identitáson, azaz az $12\text{...}n$ permutáción nem változtat. Minden más permutációnál az első elmozduló szám hátrébb kerül az újrakódolásnál.   7. feladat. Beláttuk, hogy a KÉF minden $n$ elemű véletlen permutációt ugyanolyan valószínűséggel állít elő. De ez azt is jelenti, hogy bármely két vendégre ugyanannyi lesz a valószínűsége annak, hogy ez a két vendég egy asztalnál ül. Elég tehát az első két vendégre kiszámolni ezt a valószínűséget. Az első vendég biztosan az első asztalhoz ül, a második pedig $1/2$ valószínűséggel ül mellé. Ennyi tehát a valószínűsége, hogy $n$ elem egy véletlen permutációjában két előre kijelölt elem egy ciklusban van.   10. feladat. Ismét alkalmazható mind a háromféle megoldás. Kijön számolással. Kijön az újrakódolással is. Most itt is fel kell tennünk, hogy az első szám van kijelölve és a kikötés az, hogy ezek nagyság szerint fordított sorrendben jöjjenek. A csoportok most is azok, mint a korábbi két megoldásban (lásd a 8. feladatnál), minden csoportban $s$! permutáció van, de ezek közül most minden csoportban csak egy felel meg a kikötésünknek, tehát a keresett valószínűség $1/s!$. Végül alkalmazható a KÉF is, és most az a kikötés, hogy az első $s$ vendég mindegyike új asztalt kezdjen, ez az $i$-edik vendég esetében $1/i$ valószínűséggel történik, tehát a keresett valószínűség $1/s!$-nak adódik.   12. feladat. Nincs ellentmondás. Az $A+B$ valószínűségi változó értéke ugyanis akár $2n$ is lehet, ha az összes vendég az első asztalnál ül, azaz az egész permutáció egyetlen ciklus. Ebben az esetben ugyanis, és általában is, ha az első két vendég egy asztalnál ül, azt a ciklust, amelyben ülnek, ez a változó kétszer számolja meg.   13. feladat. Nem. Ez a várható érték nyilvánvalóan nagyobb, hiszen minden olyan eset, amikor az első elem nem a legnagyobb ciklusban van ‐ azaz nem az első asztalnál ülnek a legtöbben ‐ a leghosszabb ciklus várható értékéhez többet ad hozzá, mint az első asztalnál ülők várható értékéhez. A 3. feladat első megoldásában használt számolással könnyen kijön, hogy ha $k>n/2$, akkor $P$(van pontosan $k$ hosszú $\text{ciklus})=1/k$. Másrészt ha van ilyen hosszú ciklus, akkor biztosan ez a leghosszabb, így minden ilyen $k$-ra 1-et ad a ,,legnagyobb ciklus hossza'' valószínűségi változó várható értékéhez. Ez önmagában $\left(n+1\right)/2$, és ehhez jönnek még azok az esetek, amikor csak kisebb ciklusok vannak. Páros $n$-re is könnyű látni, hogy $P($van pontosan $n/2$ hosszú $\text{ciklus)}>1/n$, tehát a legalább $n/2$ hosszú ciklusok is több, mint $\left(n+1\right)/2$-t adnak a várható értékhez.   14. feladat. Elég ezt belátni az első elemről. Tehát a KÉF-nél elég azt belátni, hogy az első vendég asztalánál $1/n$ valószínűséggel ülnek pont $k$-an ($k$-tól függetlenül). $n=\mathrm{1,2}$-re könnyen belátható az állítás. Tegyük fel, hogy $n$-re már tudjuk az állítást. Bebizonyítjuk $n$ helyett $\left(n+1\right)$-re is. Azt nézzük, hogy hogyan ülhet pontosan $k$ ember az első asztalnál, miután az $\left(n+1\right)$-edik vendég leült. Ez kétféleképp lehetséges: 1) Az utolsó vendég az első asztalhoz ült és így lettek ott $k$-an. Ez akkor van, ha az első $n$ vendég közül $k-1$ vendég ül az első asztalnál és az utolsó vendég ehhez az asztalhoz ül. Az előbbi valószínűsége az indukciós feltevés szerint $1/n$, az utolsó vendég pedig $\frac{k-1}{n+1}$ valószínűséggel fog ehhez az asztalhoz ülni. Ennek az esetnek a valószínűsége tehát $\frac{k-1}{n\left(n+1\right)}$. 2) Az utolsó vendég nem ide ült, de már az első $n$ vendég után is $k$ vendég ült az első asztalnál. Utóbbinak megint $1/n$ a valószínűsége az indukciós feltevés szerint. Annak a valószínűsége pedig, hogy az utolsó vendég nem ide ült, $\frac{n+1-k}{n+1}$. Ennek az esetnek a valószínűsége tehát $\frac{n+1-k}{n\left(n+1\right)}$ A két esetet összeadva azt kapjuk, hogy a valószínűség éppen $\frac{1}{n+1}$, és ezt akartuk belátni.   ${\displaystyle \begin{array}{c}\hfill {\displaystyle \text{<span style="font-weight: bold;">Surányi László</span>}}\hfill \end{array}}$ 1A *-gal jelölt feladatok megoldása a függelékben található.