Za´padoˇceska´ univerzita v Plzni Fakulta aplikovany´ch vˇed Katedra matematiky
Bakal´ aˇ rsk´ a pr´ ace 1 proti 100 pravdˇ epodobnost v´ yhry
Plzeˇ n 2013
Martina Abrahamov´a
Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem bakal´aˇrskou pr´aci vypracovala samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 29. kvˇetna 2013 Martina Abrahamov´a
Podˇ ekov´ an´ı T´ımto bych chtˇela podˇekovat vedouc´ımu bakal´aˇrsk´e pr´ace panu Mgr. Michalu Frieslovi, Ph.D. za odborn´e veden´ı t´eto pr´ace, cenn´e rady a n´apady, vstˇr´ıcn´ y pˇr´ıstup a ˇcas vˇenovan´ y t´eto pr´aci.
Abstrakt C´ılem t´eto bakal´aˇrsk´e pr´ace je sezn´amit se s pravidly televizn´ı soutˇeˇze 1 proti 100 a zkoumat pravdˇepodobnost, ˇze hr´aˇc zv´ıtˇez´ı. Pravdˇepodobnost bude zkoum´ana pomoc´ı tˇr´ı model˚ u v´ ypoˇctu, a to modelu absorpˇcn´ıho stavu Markovsk´eho ˇretˇezce poˇctu soupeˇr˚ u, modelu rozkladu podle d´elky hry a modelu prvn´ı chybn´e odpovˇedi hr´aˇce. D´ale bude vyˇsetˇrov´ana z´avislost pravdˇepodobnosti v´ yhry hr´aˇce ve hˇre na pravdˇepodobnosti jeho spr´avn´e odpovˇedi a odpovˇedi soupˇeˇr˚ u a provedena simulaˇcn´ı studie. Kl´ıˇcov´a slova: Pravdˇepodobnost, jev, hra, odpovˇed’, v´ yhra, absorpce, Markovsk´e ˇretˇezce, simulace
Abstract This work explores the rules of a television game show 1 proti 100“ and ” analyses the probability of the contestant winning. The probability is analysed through three calculation models; the first looks at the overall number of contestants through the absorbing states of a Markov chain; the second is a division model utilising the length of the game as the dataset; and the third is a probabilistic analysis based on the first incorrect answer. These are followed by a comparative analysis of winning-probability based on the probability of the contestant’s correct answer and on the probability of the opponent’s correct answers. A simulation study is conducted to support our calculations. Keywords: Probability, event, game, answer, win, absorption, Markov chain, simulation
Obsah ´ 1 Uvod
1
2 Pravidla hry
2
3 Modely v´ ypoˇ ctu 3.1 Hlavn´ı hr´aˇc a soupeˇr . . . . . . . . . . . . . . . . . 3.2 Rozklad podle d´elky hry . . . . . . . . . . . . . . . 3.2.1 Strategie v´ ypoˇctu . . . . . . . . . . . . . . . 3.2.2 Jevy pouˇzit´e v modelu . . . . . . . . . . . . 3.2.3 V´ ypoˇcet modelu . . . . . . . . . . . . . . . . 3.3 Podle okamˇziku prvn´ı chybn´e odpovˇedi hr´aˇce . . . . 3.3.1 Strategie v´ ypoˇctu . . . . . . . . . . . . . . . 3.3.2 Jevy pouˇzit´e v modelu . . . . . . . . . . . . 3.3.3 V´ ypoˇcet modelu . . . . . . . . . . . . . . . . 3.4 Absorpˇcn´ı stav Markovsk´eho ˇretˇezce poˇctu soupeˇr˚ u 3.5 Shrnut´ı matematick´ ych model˚ u . . . . . . . . . . . 4 Pr˚ ubˇ eh pravdˇ epodobnosti 4.1 V z´avislosti na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce 4.1.1 Monotonie . . . . . . . . . . . . . . . . . 4.1.2 Konvexnost a konk´avnost . . . . . . . . 4.2 V z´avislosti na spr´avn´e odpovˇedi soupeˇr˚ u. . . . 4.2.1 Monotonie . . . . . . . . . . . . . . . . . 4.2.2 Konvexnost a konk´avnost . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . . .
. . . . . .
. . . . . . . . . . .
. . . . . .
. . . . . . . . . . .
. . . . . .
. . . . . . . . . . .
. . . . . .
. . . . . . . . . . .
. . . . . .
. . . . . . . . . . .
3 3 3 3 4 4 8 8 8 8 11 14
. . . . . .
16 16 16 17 20 20 21
5 Simulace
23
6 Z´ avˇ er
26
´ 1 Uvod Televizn´ı vˇedomostn´ı soutˇeˇze byly dˇr´ıve velmi popul´arn´ı, at’ uˇz pro ty, kteˇr´ı chtˇeli vyhr´at vysnˇen´e miliony, a nebo pro ty, kteˇr´ı byli pouze div´aky, jenˇz si chtˇeli ovˇeˇrit, jak velk´e vˇedomosti maj´ı. C´ılem t´eto bakal´aˇrsk´e pr´ace je vypoˇc´ıtat pravdˇepodobnost v´ yhry pr´avˇe v jedn´e z televizn´ıch vˇedomostn´ıch soutˇeˇz´ı a to konkr´etnˇe ve hˇre 1 proti 100. Tato bakal´aˇrk´a pr´ace je rozdˇelena na dvˇe ˇca´sti, na teoretickou a praktickou ˇca´st. V teoretick´e ˇca´sti budou rozebr´any tˇri modely v´ ypoˇctu pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce nad soupeˇri a bude vyˇsetˇren pr˚ ubˇeh pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100 v z´avislosti na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce a soupeˇr˚ u. V praktick´e ˇca´sti bude vytvoˇrena simulace hry 1 proti 100 v softwaru MATLAB. V druh´e kapitole uvedeme pravidla televizn´ı vˇedomostn´ı soutˇeˇze 1 proti 100. Tˇret´ı kapitola se bude zab´ yvat jednotliv´ ymi modely v´ ypoˇctu pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100, modelem rozkladu podle d´elky hry, modelem prvn´ı chybn´e odpovˇedi hr´aˇce a modelem absorpˇcn´ıho stavu Markovsk´eho ˇretˇezce poˇctu soupeˇr˚ u. Na u ´vod tˇret´ı kapitoly zadefinujeme pojmy hlavn´ı hr´aˇc a soupeˇr. U kaˇzd´eho modelu v´ ypoˇctu bude demonstrov´ana strategie v´ ypoˇctu, budou uveden´e jevy vyskytuj´ıc´ı se v jednotliv´ ych v´ ypoˇctech a nakonec bude proveden samotn´ y v´ ypoˇcet. Na konci tˇret´ı kapitoly shrneme v´ ysledky jednotliv´ ych pˇr´ıstup˚ u k v´ ypoˇctu a porovn´ame jednotliv´e modely z hlediska pˇresnosti v´ ysledk˚ u a komplikovanosti v´ ypoˇctu. ˇ Ctvrt´ a kapitola bude vˇenov´ana vyˇsetˇren´ı pr˚ ubˇehu pravdˇepodobnosti v´ yhry ve hˇre v z´avislosti na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce a soupeˇr˚ u. Pro kaˇzd´ y pˇr´ıpad bude vyˇsetˇrena monotonie a konvexnost a konk´avnost. Praktick´e ˇca´sti je vˇenov´ana kapitola p´at´a. Tato kapitola se bude zab´ yvat popisem pˇriloˇzen´e simulace hry 1 proti 100. V t´eto kapitoleme srovn´ame analyticky z´ıskan´e v´ ysledky a v´ ysledky z´ıskan´e pomoc´ı simulace.
1
2 Pravidla hry Hra 1 proti 100 je televizn´ı vˇedomostn´ı soutˇeˇz, kde hr´aˇc a z´aroveˇ n jeho 100 soupeˇr˚ u dostane v kaˇzd´em kole jednu vˇedomostn´ı ot´azku se tˇremi variantami odpovˇedi. Ot´azka je stejn´a pro vˇsechny hr´aˇce hraj´ıc´ı v urˇcit´em kole. Hr´aˇc m˚ uˇze pˇrem´ yˇslet nad odpovˇed´ı neomezen´ y ˇcas, m´a nˇekolik moˇznost´ı z´achrany a vol´ı, zda n´asleduj´ıc´ı ot´azka bude snadn´a nebo obt´ıˇzn´a. Kaˇzd´ y soupeˇr m´a na odpovˇed’ deset vteˇrin a ˇspatn´a odpovˇed’ ho definitivnˇe vyˇrazuje ze hry. Hr´aˇc, pot´e, co spr´avnˇe odpov´ı na zadanou ot´azku dotane finanˇcn´ı odmˇenu ve v´ yˇsi poˇctu vyˇrazen´ ych hr´aˇc˚ u vydˇelenou poˇctem vˇsech soupeˇr˚ u hraj´ıc´ıch v tomto kole vyn´asobenou ˇca´stkou p˚ ul milionu. Pokud hr´aˇc vyˇrad´ı vˇsechny 100 soupeˇre hned v prvn´ım kole vyhr´av´a 100 ∗500000 Kˇc. Hra prob´ıh´a do t´e doby, neˇz se vyˇrad´ı vˇsichni soupeˇri nebo dokud hr´aˇc neodpov´ı ˇspatnˇe. V takov´em pˇr´ıpadˇe odch´az´ı bez v´ yhry.
2
3 Modely v´ypoˇctu V´ ypoˇcty v kapitole 3.2 a 3.3 vych´azej´ı z teorie pravdˇepodobnosti, ˇcten´aˇr se m˚ uˇze o teorii pravdˇepodobnosti v´ıce doˇc´ıst v publikaci [1].
3.1
Hlavn´ı hr´ aˇ c a soupeˇ r
Jako hlavn´ıho hr´aˇce oznaˇc´ıme jedince, kter´ y m´a ve hˇre lepˇs´ı podm´ınky, tedy m˚ uˇze pˇrem´ yˇslet nad odpovˇed´ı neomezen´ y ˇcas, m´a nˇekolik moˇznost´ı z´achrany a vol´ı mezi lehkou a tˇeˇzkou ot´azkou. Hlavn´ı hr´aˇc odpov´ıd´a spr´avnˇe na zadanou ot´azku s pravdˇepodobnost´ı p a ˇspatnˇe s pravdˇepodobnost´ı 1 − p. Prvn´ı ˇspatn´a odpovˇed’ ho vyˇrad´ı ze hry a ta d´ale nepokraˇcuje. Jako soupeˇre uvaˇzujeme jedince, kter´ y m´a ve hˇre pouze deset vteˇrin na odpovˇed’ a ˇz´adn´ ym zp˚ usobem nem˚ uˇze hru ovlivnit (nem˚ uˇze vyb´ırat ot´azku ani pouˇz´ıt z´achrany). Soupeˇr odpov´ıd´a spr´avnˇe na ot´azku s pravdˇepodobnost´ı q a ˇspatnˇe s pravdˇepodobnost´ı 1 − q (pro zjednoduˇsen´ı poˇc´ıt´ame se stejnou pravdˇepodobnost´ı pro vˇsechny soupeˇre). Po prvn´ı ˇspatn´e odpovˇedi je soupeˇr automaticky vyˇrazen ze hry. Ve vˇsech modelech v´ ypoˇctu pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100 zanedeb´av´ame vˇsechny jeho v´ yˇse zm´ınˇen´e v´ yhody.
3.2 3.2.1
Rozklad podle d´ elky hry Strategie v´ ypoˇ ctu
Jedn´ım z moˇzn´ ych zp˚ usob˚ u, jak vypoˇc´ıtat pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce nad soupeˇri ve hˇre 1 proti 100, je rozloˇzen´ı hry podle d´elky. Oznaˇcme i poˇcet kol, ot´azky jsou zad´av´any v kolech 1 aˇz i a hlavn´ı hr´aˇc v posledn´ım it´em kole zv´ıtˇez´ı. Hlavn´ı hr´aˇc odpov´ı v kaˇzd´em kole 1 aˇz i na zadanou ot´azku spr´avnˇe. Kaˇzd´ y ze sta soupeˇr˚ u hlavn´ıho hr´aˇce odpov´ı v jednom z kol 1 aˇz i chybnˇe a alespoˇ n jeden z nich odpov´ı poprv´e chybnˇe v kole i. Strategie tohoto v´ ypo3
Modely v´ypoˇctu
Rozklad podle d´elky hry
ˇctu tedy spoˇc´ıv´a v tom, ˇze hlavn´ı hr´aˇc odpov´ıd´a do kola i spr´avnˇe a minim´alnˇe jeden z jeho soupeˇr˚ u postoup´ı do it´eho kola, kde odpov´ı poprv´e ˇspatnˇe. T´ım je zaruˇcena v´ yhra hlavn´ıho hr´aˇce v tomto it´em kole, jelikoˇz on odpovˇedˇel spr´avnˇe a zbyv´aj´ıc´ı poˇcet soupeˇr˚ u (minim´alnˇe jeden) se v tomto kole vyˇradil.
3.2.2
Jevy pouˇ zit´ e v modelu
V tomto pˇr´ıstupu k v´ ypoˇctu vystupuje jev H i , kter´ y oznaˇcuje, ˇze hlavn´ı hr´aˇc odpov´ı spr´avnˇe v kolech 1 aˇz i, jev Jji , kter´ y vyjadˇruje postupu jt´eho soupeˇre ze vˇsech 100 soupeˇr˚ u do posledn´ıho kola i . D´ale zde vystupuje jev Ski , kter´ y pˇredstavuje vyˇrazen´ı kt´eho soupeˇre nˇekdy bˇehem kol 1 aˇz i y pˇredstavuje vyˇrazen´ı vˇsech zbyl´ ych 99 soupeˇr˚ u bˇehem kol a jev Vji , kter´ i 1 aˇz i. D´ale je v tomto modelu pouˇz´ıv´an jev Uj , kter´ y reprezentuje, ˇze jt´ y soupeˇr odpov´ı poprv´e ˇspatnˇe v kole i a vˇsech 99 zb´ yvaj´ıc´ıch soupeˇr˚ u odpov´ı ˇspatnˇe nejpozdˇeji v kole i. Celkov´a pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce nad soupeˇri je oznaˇcena P a je vypoˇc´ıt´ana jako
P = P
∞ [
i
(H ∩
i=1
= P
= P
∞ [
100 [
Uji )
j=1 i
(H ∩
100 [
(Jji ∩ Vji ))
i=1
j=1
∞ [
100 [
(H i ∩
i=1
(Jji ∩
j=1
\
Ski )),
k6=j
kde v posledn´ım pr˚ uniku je k z mnoˇziny {1,2,..,100} kromˇe hodnoty, kter´a pˇredstavuje poˇrad´ı jt´eho hr´aˇce.
3.2.3
V´ ypoˇ cet modelu
Pravdˇepodobnost, ˇze hlavn´ı hr´aˇc odpov´ı spr´avnˇe na zadan´e ot´azky bˇehem kol 1 aˇz i, vypoˇcteme jako pr˚ unik i nez´avisl´ ych jev˚ u, tedy hlavn´ı hr´aˇc odpov´ı i i kr´at spr´avnˇe. Pravdˇepodobnost jevu H reprezentuje v´ yraz P (H i ) = pi , 4
Modely v´ypoˇctu
Rozklad podle d´elky hry
kde p je pravdˇepodobnot spr´avn´e odpovˇedi hlavn´ıho hr´aˇce na zadanou ot´azku. D´ale uvaˇzujeme, ˇze alespoˇ n jeden ze soupeˇr˚ u odpov´ı poprv´e ˇspatnˇe na ot´azku v kole i a vˇsichni ostatn´ı soupeˇri nejpozdˇeji v kole i. Pˇredpokl´ad´ame tedy, ˇze pˇrinejmenˇs´ım jeden ze 100 soupeˇr˚ u odpov´ı v kolech 1 aˇz i−1 spr´avnˇe a v kole i odpov´ı poprv´e na ot´azku ˇspatnˇe. Ostatn´ı soupeˇri odpov´ı v nˇekter´em z kol 1 aˇz i ˇspatnˇe. Pravdˇepodobnost jevu Jji , pravdˇepodobnost spr´avn´e odpovˇedi jt´eho soupeˇre v kolech 1 aˇz i a ˇspatn´e odpovˇedi v kole i (soupeˇr odpov´ı i − 1kr´at spr´avnˇe a jednou ˇspatnˇe), reprezentuje v´ yraz P (Jji ) = q i−1 (1 − q), kde q je pravdˇepodobnost spr´avn´e odpovˇedi soupeˇre na zadanou ot´azku. Ostatn´ı soupeˇri, kteˇr´ı nemus´ı nutnˇe postoupit aˇz do posledn´ıho kola i, odpov´ı na nˇekterou zadanou ot´azku bˇehem kol 1 aˇz i chybnˇe. Pravdˇepodobnost jevu Ski , tedy pravdˇepodobnost ˇspatn´e odpovˇedi kt´eho soupeˇre v jednom z kol 1 aˇz i, m´a tvar P (Ski ) = (1 − q) + q(1 − q) + q 2 (1 − q) + ... + q i−1 (1 − q) i−1 X P (Ski ) = q n (1 − q).
(3.1)
n=0
Jelikoˇz v´ yraz (3.1) vyjadˇruje geometrickou ˇradu s prvn´ım ˇclenem 1 − q a kvocientem q, m˚ uˇzeme ˇcleny geometrick´e ˇrady seˇc´ıst. Souˇcet v´ yrazu (3.1) je P (Ski )
=
i−1 X n=0
n
q (1 − q) =
i X
q n−1 (1 − q) = (1 − q)
n=1
qi − 1 = 1 − qi. q−1
Pro n´aˇs model v´ ypoˇctu staˇc´ı postup jednoho libovoln´eho soupeˇre do posledn´ıho kola i. U zbyl´ ych 99 soupeˇr˚ u pro n´as jiˇz nen´ı d˚ uleˇzit´e, ve kter´em i kole vypadnou. Jev Vj pˇredstavuje vyˇrazen´ı zbyl´ ych 99 hr´aˇc˚ u bˇehem kol 1 aˇz i. Jev Vji je tedy pr˚ unikem 99 nez´avisl´ ych jev˚ u Ski . Pravdˇepodobnost jevu Vji vypoˇc´ıt´ame jako \ P (Vji ) = P ( Ski ) = (1 − q i )99 . k6=j
Pravdˇepodobnost jevu Uji , ˇspatn´e odpovˇedi jt´eho soupeˇre v kole i a ostatn´ıch 99 soupeˇr˚ u nejpozdˇeji v kole i, vypoˇc´ıt´ame jako pravdˇepodobnost pr˚ ui i niku jev˚ u Jj a Vj , kter´e jsou nez´avisl´e. Hodnota pravdˇepodobnosti jevu Uji 5
Modely v´ypoˇctu
Rozklad podle d´elky hry
vypad´a n´asledovnˇe P (Uji ) = P (Jji ∩ Vji ) \ P (Uji ) = P (Jji ∩ Ski ) k6=j
P (Uji )
= q
i−1
(1 − q)(1 − q i )99 .
Jelikoˇz nev´ıme, kter´ y ze 100 soupeˇr˚ u, kteˇr´ı ve hˇre 1 proti 100 vystupuj´ı, postoup´ı aˇz do posledn´ıho kola i, sjednot´ıme vˇsechny jevy Uji pˇres vˇsechna j jdouc´ı od jedn´e do sta (jev U1i reprezentuje postup prvn´ıho soupeˇr˚ u do kola i i, jev U100 pˇredstavuje postup st´eho soupeˇre do kola i). Sjednocen´ı jev˚ u Uji m´a tvar P(
100 [
Uji ) = P (U1i ) + P (U2i ) + P (U3i ) + . . .
j=1
−P (U1i ∩ U2i ) − P (U1i ∩ U3i ) − . . . +P (U1i ∩ U2i ∩ U3i ) + P (U1i ∩ U2i ∩ U4i ) + . . . −P (U1i ∩ U2i ∩ U3i ∩ U4i ) − . . . ...
(3.2)
Jednotliv´e ˇr´adky v´ yrazu (3.2) maj´ı tvar 100 i−1 + + + ... = q (1 − q)(1 − q i )99 1 100 2(i−1) i i i i −P (U1 ∩ U2 ) − P (U1 ∩ U3 ) − . . . = (−1) q (1 − q)2 (1 − q i )98 2 100 3(i−1) i i i i i i P (U1 ∩ U2 ∩ U3 ) + P (U1 ∩ U2 ∩ U4 ) + . . . = q (1 − q)3 (1 − q i )97 3 ... P (U1i )
P (U2i )
P (U3i )
V´ yraz (3.2) m˚ uˇzeme vyj´adˇrit jako alternuj´ıc´ı ˇradu ve tvaru P(
100 [
j=1
Uji )
100 X 100 = (−1)k+1 q k(i−1) (1 − q)k (1 − q i )100−k . k k=1
Pravdˇepodobnost P, ˇze hlavn´ı hr´aˇc poraz´ı vˇsechny re v kole i, vypoS100 soupeˇ i i ˇc´ıt´ame jako pravdˇepodobnost pr˚ uniku jev˚ u H a j=1 Uj , kter´e jsou opˇet nez´avisl´e. Prvˇepodobnost pr˚ uniku tˇechto dvou jev˚ u jeˇstˇe seˇcteme pˇres vˇsechny 6
Modely v´ypoˇctu
Rozklad podle d´elky hry
i jdouc´ı od jedn´e do nekoneˇcna, jelikoˇz hra m˚ uˇze trvat od jednoho do nekoneˇcnˇe mnoha kol. Tento souˇcet pˇredstavuje sjednocen´ı disjunktn´ıch jev˚ u. Pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100 vypoˇc´ıt´ame jako P =
∞ X
i
P (H )P (
i=1
P =
100 [
Uji )
j=1
∞ X
p
i=1
i
100 X k=1
100 (−1)k+1 q k(i−1) (1 − q)k (1 − q i )100−k . k
(3.3)
V´ yraz (3.3) neum´ıme explicitnˇe seˇc´ıst, seˇcteme tedy jen prvn´ıch n ˇclen˚ u. Pro urˇcen´ı poˇctu ˇclen˚ u n, kter´e seˇcteme, odhadneme zbytek ˇrady po seˇcten´ı prvn´ıch n ˇclen˚ u a urˇc´ıme konstatntu ,Pna kter´e bude z´aviset pˇresnost v´ y∞ i p , jelikoˇ z v´ y raz sledku. Zbytek ˇ r ady odhadneme ˇ r adou i=n P100 100 k+1 k(i−1) k i 100−k (−1) q (1 − q) (1 − q ) reprezentuje hodnotu pravdˇepok=1 k dobnosti, tedy hodnotu z intervalu (0,1), a v´ yraz pi se m˚ uˇze po vyn´asoben´ı toutoP hodnotou pouze zmenˇsit. Odhad zbytku ˇrady 3.3 a n´asledn´e seˇcetn´ı i a tvar ˇrady ∞ i=n p m´ |
∞ X i=n
p
i
100 X 100 k=1
k
k+1 k(i−1)
(−1)
q
k
i 100−k
(1 − q) (1 − q )
| <
∞ X
pi
i=n n
p < . 1−p Konstantu vol´ıme jako hodnotu 0,001, tedy aproximovan´a hodnota pravdˇepodobnosti P bude s pˇresnost´ı na jedno desetinn´e m´ısto procenta.
7
Modely v´ypoˇctu
3.3
3.3.1
Podle okamˇziku prvn´ı chybn´e odpovˇedi hr´aˇce
Podle okamˇ ziku prvn´ı chybn´ e odpovˇ edi hr´ aˇ ce Strategie v´ ypoˇ ctu
Dalˇs´ım modelem v´ ypoˇctu pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100 je model prvn´ı chybn´e odpovˇedi hlavn´ıho hr´aˇce. V tomto pˇr´ıstupu k v´ ypoˇctu odpov´ı hlavn´ı hr´aˇc na ot´azku poprv´e ˇspatnˇe pozdˇeji neˇz vˇsichni jeho soupeˇri, tzn. vˇsichni soupeˇrov´e se do urˇcit´eho kola vyˇrad´ı a hlavn´ı hr´aˇc aˇz pot´e odpov´ı ˇspatnˇe. Pro n´aˇs model oznaˇc´ıme kolo i jako kolo, ve kter´em odpov´ı hlavn´ı hr´aˇc poprv´e ˇspatnˇe. V tomto modelu odpov´ı hlavn´ı hr´aˇc na vˇsechny zadan´e ot´azky bˇehem kol 1 aˇz i − 1 spr´avnˇe a na ot´azku zadanou v i-t´em kole odpov´ı poprv´e chybnˇe. Kaˇzd´ y ze sta soupeˇr˚ u vypadne v nˇekter´em z kol 1 aˇz i − 1, tedy kaˇzd´ y z nich odpov´ı na nˇekterou zadanou ot´azku bˇehem tˇechto kol ˇspatnˇe a t´ım pro nˇej hra konˇc´ı. T´ım je zaruˇcena v´ yhra hlavn´ıho hr´aˇce, jelikoˇz vˇsech sto soupeˇr˚ u vypadne nepojzdˇej´ı v kole i − 1, kde hlavn´ı hr´aˇc jeˇstˇe odpov´ı spr´avnˇe.
3.3.2
Jevy pouˇ zit´ e v modelu
V tomto pˇr´ıstupu k v´ ypoˇctu vystupuje jev H i , kter´ y oznaˇcuje spr´avnou odpovˇed’ hlavn´ıho hr´aˇce v kolech 1 aˇz i − 1 a ˇspatnou odpovˇed’ v kole i. D´ale y vyjadˇruje ˇspatnou odpovˇed’ jt´eho soupeˇre v nˇezde vystupuje jev Sji , kter´ kter´em z kol 1 aˇz i−1 a jev U i , kter´ y reprezentuje vyˇrazen´ı vˇsech 100 soupeˇr˚ u do kola i − 1. Celkov´a pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce nad soupeˇri je oznaˇcena P a je vypoˇc´ıt´ana jako P =
∞ [ i=2
3.3.3
i
P (H ∩
100 \
Sji )
j=1
=
∞ [
P (H i ∪ U i ).
i=2
V´ ypoˇ cet modelu
Pravdˇepodobnost jevu H i vypoˇc´ıt´ame jako pr˚ unik pravdˇepodobnost´ı i nez´avisl´ ych jev˚ u, jev˚ u pˇredstavuj´ıc´ıch jednu ˇspatnou odpovˇed’ v kole i a jevu reprezentuj´ıc´ı i−1 spr´avn´ ych odpovˇed´ı bˇehem kol 1 aˇz i−1. Pravdˇepodobnost 8
Modely v´ypoˇctu
Podle okamˇziku prvn´ı chybn´e odpovˇedi hr´aˇce
jevu H i m´a tvar P (H i ) = pi−1 (1 − p). Vˇsichni soupeˇri odpov´ı v nˇekter´em z kol 1 aˇz i − 1 ˇspatnˇe. Pravdˇepodobnost jevu Sji , tedy ˇspatn´e odpovˇedi j-t´eho soupeˇre v jednom z kol 1 aˇz i − 1 vypoˇceteme jako P (Sji ) = (1 − q) + q(1 − q) + q 2 (1 − q) + ... + q i−2 (1 − q).
(3.4)
V´ yraz (3.4) m˚ uˇzeme vyj´adˇrit jako geometrickou ˇradu s prvn´ım ˇclenem 1 − q a kvocientem q, kterou um´ıme seˇc´ıst. Souˇcet t´eto geometrick´e ˇrady m´a tvar P (Sji )
=
i−2 X
n
q (1 − q) =
n=0
i−1 X
q n−1 (1 − q) =
n=1
= (1 − q)
q
i−1
−1 = 1 − q i−1 . q−1
(3.5)
Ve hˇre 1 proti 100 figuruje 100 soupeˇr˚ u a kaˇzd´ y z nich odpov´ıd´a v kolech 1 aˇz i − 1 s pravdˇepodobnost´ı vypoˇc´ıtanou ve v´ yrazu (3.5). Pravdˇepodobnost jevu U i tedy vypoˇc´ıt´ame jako pr˚ unik 100 nez´avisl´ ych jev˚ u Sji i
P (U ) = P (
100 \
Sji ) = (1 − q i−1 )100 .
j=1
Jak jiˇz bylo ˇreˇceno, pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce v kole i vyi i poˇcteme jako pr˚ unik jev˚ u H a S , kter´e jsou nez´avisl´e. Pravdˇepodobnost pr˚ uniku tˇechto jev˚ u jeˇstˇe seˇcteme (tento souˇcet pˇredstavuje sjednocen´ı disjunktn´ıch jev˚ u) pˇres vˇsechna i jdouc´ı od dvou do nekoneˇcna, jelikoˇz hra m˚ uˇze teoreticky trvat od dvou (jedno kolo nen´ı moˇzn´e, v pˇr´ıpadˇe, ˇze by hra trvala pouze jedno kolo, nastal by spor s t´ımto modelem, jelikoˇz hlavn´ı hr´aˇc by v prvn´ım kole odpovˇedˇel chybnˇe a prohr´al by) do nekoneˇcnˇe mnoha kol P =
∞ X
P (H i )P (U i )
i=2
P = P =
∞ X i=2 ∞ X
pi−1 (1 − p)(1 − q i−1 )100 pi (1 − p)(1 − q i )100 .
i=1
9
(3.6)
Modely v´ypoˇctu
Podle okamˇziku prvn´ı chybn´e odpovˇedi hr´aˇce
V´ yraz (3.6) uprav´ıme rozmocnˇen´ım v´ yrazu (1 − q i )100 P
=
∞ X 100 i 100 2i 100 3i i (1 − p)p [1 − q + q − q + 1 2 3 i=1
... +
100 98i 100 99i 100 100i q − q + q ]. 98 99 100
(3.7)
. D´ale m˚ uˇzeme v´ yraz (3.7) vyj´adˇrit jako souˇcet 101 geometrick´ ych ˇrad P
=
X X X ∞ ∞ ∞ ∞ X 100 100 100 i i i i 2i (1 − p)[ p − pq + pq − pi q 3i + 1 2 3 i=1 i=1 i=1 i=1
...
+
X X X ∞ ∞ ∞ 100 100 100 i 98i i 99i pq − pq + pi q 100i ]. 98 i=1 99 i=1 100 i=1
(3.8)
Tˇechto 101 geometrick´ ych ˇrad z v´ yrazu (3.8) m˚ uˇzeme postupnˇe seˇc´ıst 100 pq 100 pq 2 p P = (1 − p)( − + − 1−p 1 1 − pq 2 1 − pq 2 ... 100 pq 99 100 pq 100 − + ). 99 1 − pq 99 100 1 − pq 100 Pravdˇepodobnost v´ yhry P hlavn´ıho hr´aˇce nad vˇsemi soupeˇri v modelu prvn´ı chybn´e opdovˇedi hlavn´ıho hr´aˇce m´a po u ´pravˇe tvar 100 X pq n n 100 P = (1 − p) (−1) . n 1 − pq n n=0
10
Modely v´ypoˇctu
3.4
Absorpˇcn´ı stav Markovsk´eho ˇretˇezce poˇctu soupeˇr˚ u
Absorpˇ cn´ı stav Markovsk´ eho ˇ retˇ ezce poˇ ctu soupeˇ r˚ u
V´ ypoˇcty prov´adˇen´e v t´eto kapitole jsou zaloˇzeny na teorii n´ahodn´ yh proces˚ u, pˇredevˇs´ım Markov´ ych ˇretˇezc˚ u. V´ıce o tˇechto ˇretˇezc´ıch a n´ahodn´ ych procesech se m˚ uˇze ˇcten´aˇr doˇc´ıst v publikac´ıch [2] a [3]. Posledn´ım z model˚ u v´ ypoˇctu v t´eto pr´aci je model hry pomoc´ı Markovsk´eho ˇretˇezce. Pr˚ ubˇeh hry lze modelovat markovov´ ym ˇretˇezcem s mnoˇzinou stav˚ u {sj }101 (stavy pˇ r edstavuj´ ı poˇ c et ˇ z ij´ ıch soupeˇ r ˚ u,kromˇe stavu 101, kter´ y j=0 pˇredstavuje ˇspatnou odpovˇed’ hlavn´ıho hr´aˇce na zadanou ot´azku, nebo-li prohru hlavn´ıho hr´aˇce nad soupeˇri, jejichˇz poˇcet n´as v tomto stavu nezaj´ım´a) a matic´ı pˇrechodu P = [pi,j ]101 i,j=0 . Stavy 1 aˇz 100 pˇredstavuj´ı poˇcty nevyˇrazan´ ych soupeˇr˚ u, tedy stav 1 pˇredstavuje hru, ve kter´e zbyl jeden soupeˇr a hlavn´ı hr´aˇc, stav 2 reprezentuje situaci se dvˇema soupeˇri a hlavn´ım hr´aˇcem atd. Stav 0, pˇredstavuje ˇz´adn´eho soupeˇre, tedy v´ıtˇezstv´ı hlavn´ıho hr´aˇce. Stav 101 reprezentuje prohru hlavn´ıho hr´aˇce. Ze stav˚ u 0 a 101 nem˚ uˇze hra pokraˇcovat do ˇza´dnˇeho jin´eho stavu, jedn´a se o absorpˇcn´ı stavy Markovova ˇretˇezce. Nyn´ı sestav´ıme matici pˇrechodu P v z´avislosti na parametrech p a q.Sestaven´ı matice budemem demonstrovat na stavu 2. Pokud se hra nach´az´ı ve stavu 2, tedy ve stavu kdy zb´ yvaj´ı dva soupeˇri a hlavn´ı hr´aˇc, m˚ uˇze hra pokraˇcovat do 4 stav˚ u, do stavu 0, kdy hlavn´ı hr´aˇc zv´ıtˇez´ı, do stavu 1, kdy jeden ze dvou soupeˇr˚ u odpov´ı ˇspatnˇe, setrvat ve stavu 2 nebo pˇrej´ıt do stavu 101, kdy hra konˇc´ı, protoˇze hlavn´ı hr´aˇc odpovˇedˇel ˇspatnˇe. Pˇrechod ze stavu 2 do stavu 0 reprezentuje ˇspatnou odpovˇed’ obou soupeˇr˚ u a spr´avnou odpovˇed’ hlavn´ıho hr´aˇce, pravdˇepodobnost tohoto pˇrechodu je p2,0 = p(1 − q)2 . Pˇri pˇrechodu ze stavu 2 do stavu 1 odpov´ı jeden konkr´etn´ı soupeˇr z tˇechto dvou hraj´ıc´ıch soupeˇr˚ u spr´avnˇe, druh´ y odpov´ı ˇspatnˇe a hlavn´ı hr´aˇc odpov´ıd´a spr´avnˇe. Pravdˇepodobnost tohoto pˇrechodu m´a tvar 2 p2,1 = pq(1 − q). 1 Setrv´an´ı ve stavu 2 je moˇzn´e, pokud hlavn´ı hr´aˇc i oba soupeˇri odpov´ı 11
Modely v´ypoˇctu
Absorpˇcn´ı stav Markovsk´eho ˇretˇezce poˇctu soupeˇr˚ u
na zadanou ot´azku spr´avnˇe. Pravdˇepododnost setrv´an´ı ve stavu 2 je p1,1 = pq 2 . Pˇrechod ze stavu 2 do stavu 101 pˇredstavuje konec hry prohrou hlavn´ıho hr´aˇce. Jelikoˇz se jedn´a o konec hry, zaj´ım´a n´as pouze odpovˇed’ hlavn´ıho hr´aˇce, kter´a je ˇspatn´a. Odpovˇedi soupeˇr˚ u pro n´as v tomto okamˇziku nemaj´ı v´ yznam. Pravdˇepodobnost pˇrechodu ze stavu 2 do stavu 101 m´a tvar p2,101 = (1 − p). Pˇrechod do stav˚ u 3 aˇz 100 nen´ı ze stavu 2 moˇzn´ y, jelikoˇz soupeˇri mohou pouze ub´ yvat, pokud ˇspatnˇe odpov´ı, nikoliv pˇrib´ yvat. Pravdˇepodobnost pˇrechodu je tedy p2,k = 0
k = {3, 4, 5, . . . , 99, 100}.
Jak jiˇz bylo zm´ınˇeno, stavy 0 a 101 jsou absorpˇcn´ımi stavy Markovova ˇretˇezce, tedy ze stavu 0 m˚ uˇzeme pˇrej´ıt pouze do stavu 0, ze stavu 101 pouze do stavu 101. Pravdˇepodnosti setrv´an´ı ve stavech 0 a 101 je tedy p0,0 = 1 p101,101 = 1. Analogicky dopln´ıme prvky zb´ yvaj´ıc´ıch ˇra´dk˚ u. V´ ysledn´a matice pˇrechodu P je ˇctvercov´a matice ˇra´du 102 ve tvaru 1 0 0 0 ... p(1 − q) pq 0 0 ... 2 2 p(1 − q)2 pq(1 − q) 0 ... 1 pq 3 3 2 2 3 p(1 − q)3 pq(1 − q) pq (1 − q) ... 1 2 pq 4 4 4 3 2 2 3 p(1 − q)4 pq(1 − q) pq (1 − q) pq (1 − q) ... P= 1 2 3 . . . . .. .. .. .. ... 99 99 99 99 2 97 3 96 p(1 − q)99 pq(1 − q) pq (1 − q) pq (1 − q) ... 1 2 3 p(1 − q)100 100 pq(1 − q)100 100 pq 2 (1 − q)98 100 pq 3 (1 − q)97 . . . 1 2 3 0 0 0 0 ... Stavy 1 aˇz 100 jsou stavy pˇrechodn´e. Nyn´ı n´as zaj´ım´a pravdˇepodobnost absorpce ze stavu 100 do stavu 0. Sestav´ıme soustavu rovnic podle n´asleduj´ıc´ı 12
0 1−p 1−p 1−p 1−p .. .
. 1−p 1−p 1
Modely v´ypoˇctu
Absorpˇcn´ı stav Markovsk´eho ˇretˇezce poˇctu soupeˇr˚ u
rovnice pro v´ ypoˇcet pravdˇepodobnosti absorpce ze stavu i do stavu j podle pravdˇepodobnost´ı pˇrechod˚ u X ui,j = pi,j + piν uνj , i ∈ T, j ∈ /T ν∈T
kde T je mnoˇzina pˇrechodn´ ych stav˚ u, tedy stav˚ u 1 aˇz 100. Po dosazen´ı jednotliv´ ych pravdˇepodobnost´ı pˇrechod˚ u z matice pˇrechodu P do rovnice (3.9) z´ısk´av´ame soustavu 100 n´asleduj´ıc´ıch rovnic. u1,0 = p(1 − q) + pqu1,0 2 2 u2,0 = p(1 − q) + pq(1 − q)u1,0 + pq 2 u2,0 1 3 3 3 2 u3,0 = p(1 − q) + pq(1 − q) u1,0 + pq 2 (1 − q)u2,0 + pq 3 u3,0 1 2 .. . (3.9) Jelikoˇz n´as zaj´ım´a absorpce ze stavu 100 do stavu 0, potˇrebujeme vyj´adˇrit vˇsechny pravdˇepodobnosti ui,j , i = {1, 2, . . . , 99, 100}, j = 0. Explicitn´ı vyj´adˇren´ı vˇsech tˇechto pravdˇepodobnost´ı je velmi n´aroˇcn´e, z tohoto d˚ uvodu budou tyto pravdˇepodobnosti vyj´adˇreny numericky. Postupnˇe budeme dosazovat hodnoty parametr˚ u p a q, p, q ∈ (0, 1). Pro tyto hodnoty n´aslednˇe vyˇc´ısl´ıme pravdˇepodobnost u100,0 , kter´a pˇredstavuje v´ yhru hlavn´ıho hr´aˇce. Numerick´ y v´ ypoˇcet byl proveden v programu MATLAB. Pro hodnoty pravdˇepodobnost´ı p a q byly voleny hodnoty k · 0, 05, kde k= {0,1,2, . . . , 20}. Jednotliv´e rovnice z v´ yrazu (3.9) lze vyj´adˇrit ve tvaru k X k p(1 − q)n q k−n uk−n,0 (3.10) uk,0 = k − n n=0 kter´ y pouˇzijeme jako v´ ypoˇcetn´ı tvar v programu MATLAB. Jelikoˇz MATLAB poˇc´ıt´a s pˇresnost´ı na 15 m´ıst, podle vzorce (3.10) n´am nevypoˇc´ıt´a explicitn´ı v´ ysledek d´ıky velk´ ym hodnot´am kombinaˇcn´ıch ˇc´ısel. Vyj´adˇr´ıme tedy v´ yraz (3.10) pomoc´ı pˇrirozen´eho logaritmu a v´ ypoˇcet kombinaˇcn´ıch ˇc´ısel pomoc´ı logaritmick´e Gamma funkce, kter´a je v MATLABU vestavˇena. Upraven´ y v´ yraz m´a tvar uk,0 =
k X
elnΓ(k+1)−(lnΓ(k−n+1)+lnΓ(i+1)ln(p(1−q)
n=0
13
n q k−n u k−i,0 )
.
Modely v´ypoˇctu
3.5
Shrnut´ı matematick´ych model˚ u
Shrnut´ı matematick´ ych model˚ u
Po numerick´em vyj´adˇren´ı pravdˇepodobnosti v´ yhry pro urˇcit´e promˇenn´e p a q z´ısk´av´ame pro vˇsechny metody v´ ypoˇctu stejn´e hodnoty. V prvn´ım modelu rozklad hry podle d´elky z´ısk´av´ame aproximovan´ y v´ ysledek, jelikoˇz jsme nebyli schopni z´ıskat pomoc´ı tvaru funkce z´ıskan´eho v tomto modelu explicitn´ı v´ ysledek. Tvar funkce z´ıskan´ y pomoc´ı tohoto modelu je velmi komplikovan´ y, jelikoˇz sˇc´ıt´ame dvˇe nekoneˇcn´e sumy. V druh´em modelu z´ısk´av´ame explicitn´ı v´ ysledky, jelikoˇz tvar funkce z´ıskan´ y v modelu podle prvn´ı chybn´e odpovˇedi hr´aˇce je tvoˇren koneˇcn´ ym, nikoliv nekoneˇcn´ ym souˇctem jako v pˇredchoz´ım modelu. Tvar funkce z´ıskan´ y pomoc´ı tˇret´ıho modelu, modelu absorpˇcn´ıho stavu Markovsk´eho ˇretˇezce, d´av´a takt´eˇz explicitn´ı v´ ysledek. V tomto modelu z´ısk´av´ame soustavu 100 rovnic, ze kter´e je velmi sloˇzit´e analyticky vyj´adˇrit v´ ysledek. Po numerick´em vyj´adˇren´ı v softwaru MATLAB z´ısk´av´ame v´ ysledek aproximovan´ y. Z hlediska komplikovanosti je tedy nejjednoduˇsˇs´ım tvarem funkce tvar funkce z´ıskan´ y v modelu podle prvn´ı chybn´e odpovˇedi hr´aˇce, tento tvar je pˇri numerick´em vyj´adˇren´ı tak´e nejpˇresnˇejˇs´ım v´ ysledkem. Na obr´azku 3.1 je zn´azornˇen graf pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100 v z´avislosti jak na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce, tak na spr´avn´e odpovˇedi soupeˇr˚ u. Pro lepˇs´ı grafickou pˇredstavivost jsou na obr´azku 3.2 vyobrazeny vrstevnice funkce reprezentuj´ıc´ı pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100. Dalˇs´ı grafy z´avislosti pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce P na jednotliv´ ych promˇenn´ ych p a q jsou zn´azornˇeny v n´asleduj´ıc´ı kapitole, viz obr´azek 4.1 a obr´azek 4.2.
14
Modely v´ypoˇctu
Shrnut´ı matematick´ych model˚ u
Obr´azek 3.1: Pravdˇepodbnost v´ yhry P v z´avislosti na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce a soupeˇr˚ u
Vrstevnice Pravdepodobnost spravne odpovedi hlavniho hrace
1 0.9 0.9 0.8 0.8 0.7
0.7 0.6
0.6
0.5
0.5
0.4
0.4
0.3
0.3
0.2 0.2 0.1 0.1 0
0
0.2 0.4 0.6 0.8 Pravdepodobnost spravne odpovedi souperu
Obr´azek 3.2: Vrstevnice
15
1
4 Pr˚ ubˇ eh pravdˇ epodobnosti 4.1
Pr˚ ubˇ eh pravdˇ epodobnosti v z´ avislosti na spr´ avn´ e odpovˇ edi hlavn´ıho hr´ aˇ ce
Nyn´ı se pod´ıv´ame na z´avislost pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce nad soupeˇri. Vyˇsetˇr´ıme z´avislost pravdˇepodobnosti v´ yhry na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce a soupeˇr˚ u, pˇredevˇs´ım n´as bude zaj´ımat monotonie, konvexnost a konk´avnost funkce reprezentuj´ıc´ı pravdˇepodobnost P.
4.1.1
Monotonie
Pro vyˇsetˇren´ı monotonie funkce pˇredstavuj´ıc´ı pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100 v z´avislosti na promˇenn´e p, tedy spr´avn´e odpovˇedi hlavn´ıho hr´aˇce na zadanou ot´azku, vyuˇzijeme tvaru funkce z´ıskan´eho z modelu v´ ypoˇctu pravdˇepodobnosti v´ yhry podle rozkladu podle d´elky hry. V tomto modelu je pravdˇepodobnost v´ yhry vypoˇc´ıt´ana jako P =
∞ X
i
P (H )P (
i=1
P =
∞ X i=1
100 [
Uji )
j=1
p
i
100 X k=1
100 (−1)k+1 q k(i−1) (1 − q)k (1 − q i )100−k . k
(4.1)
S i avis´ı pouze na promˇenn´e q, tedy V´ıd´ıme, ˇze pravdˇepodobnost P ( 100 j=1 Uj ) z´ spr´avn´e odpovˇedi soupeˇre, nikoli na promˇenn´e p, podle kter´e vyˇsetˇrujeme monotonii. Uprav´ıme tedy v´ yraz (4.1) jako P =
∞ X
p i · ci ,
c ∈ (0, 1).
(4.2)
i=1
Nyn´ı v´ yraz (4.2), kter´ y pˇredstavuje mocninnou ˇradu, zderivujeme pro vyˇsetˇren´ı monotonie. U mocninn´ ych ˇrad m˚ uˇzeme uvnitˇr oboru konvergence derivovat ˇcleny ˇclen po ˇclenu a je zˇrejm´e, ˇze interval (0,1), na kter´em chceme derivovat patˇr´ı do oboru konvergence t´eto mocninn´e ˇrady.
16
Pr˚ ubˇeh pravdˇepodobnosti
V z´avislosti na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce
Derivace v´ yrazu (4.2) m´a tvar 0
P =
∞ X
ipi−1 · ci ,
c ∈ (0, 1).
i=1
V n´asleduj´ıc´ı tabulce 4.1 jsou zn´azornˇen´e jednotliv´e ˇcinitele z prvn´ı derivace a jejich v´ ysledn´e znam´enko. V´ yraz
interval (0,1)
ici
kladn´ y
pi−1
kladn´ y
ipi−1 ci
kladn´ y
Tabulka 4.1: Hodnoty ˇcinitel˚ u prvn´ı derivace podle p
Hodnota prvn´ı derivace v´ yrazu (4.2) je kladn´a, funkce je tedy na intervalu (0,1) rostouc´ı vzhledem k promˇenn´e p.
4.1.2
Konvexnost a konk´ avnost
Zda-li je funkce konvexn´ı nebo konk´avn´ı vyˇsetˇr´ıme z tvaru funkce vyj´adˇren´e v modelu podle prvn´ı chybn´e odpovˇedi hr´aˇce. V tomto modelu je pravdˇepodobnost P vypoˇc´ıt´ana jako ∞ X P = P (H i )P (S i ) i=2
P =
∞ X
pi (1 − p)(1 − q i )100 .
(4.3)
i=1
Jelikoˇz P (S i ) = (1 − q i )100 nez´avis´ı na promˇenn´e p, podle kter´e vyˇsetˇrujeme konvexnost a konk´avnost, ale pouze na promˇenn´e q, uprav´ıme v´ yraz (4.3) na tvar P =
∞ X
pi (1 − p)ci ,
i=1
17
c ∈ (0, 1).
(4.4)
Pr˚ ubˇeh pravdˇepodobnosti
V z´avislosti na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce
Konvexnost a konk´avnost urˇc´ıme podle hodnoty druh´e derivace zkouman´e funkce. Pokud je druh´a derivace z´aporn´a, funkce je konk´avn´ı, pokud funkce nab´ yv´a v druh´e derivaci kladn´e hodnoty je funkce konvexn´ı. V´ yraz (4.4) reprezentuje mocninou ˇradu a interval (0,1) opˇet spad´a do oboru konvergence mocninn´e ˇrady (4.4), m˚ uˇzeme ji tedy derivovat ˇclen po ˇclenu. Prvn´ı derivace funkˇcn´ı ˇrady (4.4) podle promˇenn´e p je 0
P =
∞ X
ci (ipi−1 − ipi − pi ),
c ∈ (0, 1).
(4.5)
i=1
Prvn´ı derivace je opˇet mocninnou ˇradou, kterou m˚ uˇzeme opˇet derivovat ˇclen po ˇclenu, jelikoˇz polomˇer konvergence je u mocninn´ ych ˇrad pˇri derivov´an´ı zachov´an a interval (0,1) znovu spad´a do oboru konvergence mocninn´e ˇrady (4.5). Vypoˇc´ıt´ame druhou derivaci, ze kter´e urˇc´ıme, zda-li je funkce konvexn´ı nebo konk´avn´ı. Druh´a derivace v´ yrazu (4.4) m´a tvar 00
P =
∞ X
ci i(i − 1)(1 − p)pi−2 ,
c ∈ (0, 1).
i=1
V tabulce 4.2 jsou zn´azornˇeny kladnosti respektive z´apornosti jednotliv´ ych ˇcinitel˚ u vystupuj´ıc´ıch v druh´e derivaci. Hodnota druh´e derivace funkce pˇredstavuj´ıc´ı v´ yhru hlavn´ıho hr´aˇce ve hˇre 1 proti 100 podle promˇenn´e p, tedy pravdˇepodobnosti spr´avn´e odpovˇedi hlavn´ıho hr´aˇce, je nez´aporn´a. Funkce je tedy konvexn´ı vzhledem k p.
Na obr´azku 4.1 je zobrazen graf pr˚ ubˇehu pravdˇepodobnosti P v z´avislosti na pravdˇepodobnosti spr´avn´e odpovˇedi hlavn´ıho hr´aˇce pro 9 vybran´ ych hodnot q.
18
Pr˚ ubˇeh pravdˇepodobnosti
V z´avislosti na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce V´ yraz
interval (0,1)
ci i
kladn´ y
i−1
nez´aporn´ y
1−p
kladn´ y
pi−2
kladn´ y
ci i(i − 1)(1 − p)pi−2
nez´aporn´ y
Pravdepodobnost vyhry
Tabulka 4.2: Hodnoty ˇcinitel˚ u v druh´e derivace podle p
Pravdepodobnost vyhry hlavniho hrace v zavislosti na jeho spravne odpovedi 1 q=0.1 0.9 q=0.2 q=0.3 0.8 q=0.4 q=0.5 0.7 q=0.6 q=0.7 0.6 q=0.8 q=0.9 0.5 0.4 0.3 0.2 0.1 0
0
0.2 0.4 0.6 0.8 Pravdepodobnost spravne odpovedi souperu
1
Obr´azek 4.1: Pr˚ ubˇeh pravdˇepodobnosti v z´avislosti na spr´avn´e odpovˇedi hlavn´ıho hr´aˇce
Jak je z obr´azku vidˇet, jednotliv´e grafy jsou funkce rostouc´ı a konvexn´ı. V´ ypoˇcet toto tvrzen´ı potvrzuje.
19
Pr˚ ubˇeh pravdˇepodobnosti
4.2
4.2.1
V z´avislosti na spr´avn´e odpovˇedi soupeˇr˚ u
Pr˚ ubˇ eh pravdˇ epodobnosti v z´ avislosti na spr´ avn´ e odpovˇ edi soupeˇ r˚ u Monotonie
Pro vyˇsetˇren´ı monotonie funkce pˇredstavuj´ı pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce nad soupeˇri ve hˇre 1 proti 100 podle promˇenn´e q, tedy spr´avn´e odpovˇedi soupeˇre na zadanou ot´azku, vyuˇzijeme tvaru funkce z´ıskan´eho v modelu podle prvn´ı chybn´e odpovˇedi hr´aˇce. V tomto pˇr´ıstupu je hledan´a funkce vypoˇc´ıt´ana jako ∞ X
P =
P (H i )P (S i )
i=2 ∞ X
P =
pi (1 − p)(1 − q i )100 .
(4.6)
i=1 i
i
Vid´ıme, ˇze v´ yraz P (H ) = p (1 − p) je z´avisl´ y pouze na promˇenn´e p, nikoliv na promˇenn´e q, podle kter´e monotonii vyˇsetˇrujeme. Jak jiˇz bylo zm´ınˇeno, v´ yraz P (H i ) pˇredstavuje pravdˇepodobnost, tedy hodnotu mezi 0 a 1. V´ yraz (4.6) m˚ uˇzeme tedy zapsat v upraven´em tvaru P =
∞ X
ci · (1 − q i )100 ,
c ∈ (0, 1).
(4.7)
i=1
Nyn´ı z´ıskan´ y v´ yraz (4.7) zderivujeme podle promˇenn´e q, abychom mohli vyˇsetˇrit monotonii v z´avislosti na t´eto promˇenn´e. V´ yraz 4.7 reprezentuje mocninnou ˇradu a interval (0,1) patˇr´ı do oboru konvergence t´eto mocninn´e ˇrady, m˚ uˇzeme ji tedy derivovat po ˇclenech. Prvn´ı derivace v´ yrazu (4.7) podle q m´a tvar 0
P =·
∞ X
−100iq i−1 (1 − q i )99 ci ,
c ∈ (0, 1).
(4.8)
i=1
V tabulce 4.3 jsou zn´azornˇeny kladnosti respektive z´apornosti jednotliv´ ych ˇcinitel˚ u, ze kter´ ych se skl´ad´a prvn´ı derivace v´ yrazu 4.7. Hodnota v´ yrazu 4.8 je z´aporn´a, dan´a funkce je tedy klesaj´ıc´ı vzhledem k q. 20
Pr˚ ubˇeh pravdˇepodobnosti
V z´avislosti na spr´avn´e odpovˇedi soupeˇr˚ u V´ yraz
interval (0,1)
−100i
z´aporn´ y
q i−1
kladn´ y
(1 − q i )99
kladn´ y
−100iq i−1 (1 − q i )99
z´aporn´ y
Tabulka 4.3: Hodnoty ˇcinitel˚ u prvn´ı derivace podle q
4.2.2
Konvexnost a konk´ avnost
Konvexnost a konk´avnost funkce pˇredstavuj´ıc´ı v´ yhru hlavn´ıho hr´aˇce v z´avislosti na spr´avn´e odpovˇedi soupeˇr˚ u, vyˇsetˇr´ıme stejnˇe jako v pˇredchoz´ım pˇr´ıpadˇe z funkce z´ıskan´e v modelu podle prvn´ı chybn´e odpovˇedi hr´aˇce. V tomto modelu je pravdˇepodobnost v´ yhry P hlavn´ıho hr´aˇce nad soupeˇri vypoˇc´ıt´ana jako ∞ X P = P (H i )P (S i ) n=1
P =
∞ X
pi (1 − p)(1 − q i )100 .
(4.9)
i=1
V´ yraz P (H) = pi (1 − p) z´avis´ı pouze na promˇenn´e p, podle kter´e nevyˇsetˇrujeme monotonii. Budeme tedy tento v´ yraz br´at jako hodnotu mezi 0 a 1 (jedn´a se o hodnotu pravdˇepodobnosti) a uprav´ıme v´ yraz (4.9) na tvar P =
∞ X
ci · (1 − q i )100 ,
c ∈ (0, 1).
(4.10)
i=1
Prvn´ı derivaci v´ yrazu 4.10 jsme z´ıskali jiˇz v pˇredchoz´ı ˇc´ast ve tvaru ∞ X 0 P =· −100iq i−1 (1 − q i )99 ci , c ∈ (0, 1). (4.11) i=1
Nyn´ı vypoˇc´ıt´ame druhou derivaci v´ yrazu (4.10) pro vyˇsetˇren´ı konvexnosti nebo konk´avnosti funkce reprezentuj´ıc´ı pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100 v z´avislosti na spr´avn´e odpovˇedi soupeˇr˚ u. V´ yraz 21
Pr˚ ubˇeh pravdˇepodobnosti
V z´avislosti na spr´avn´e odpovˇedi soupeˇr˚ u
(4.11) reprezentuje opˇet mocninnou ˇradu a pˇri derivov´an´ı mocninn´e ˇrady se zachov´av´a polomˇer konvergence, m˚ uˇzeme tedy opˇet derivovat po ˇclenech. Druh´a derivace v´ yrazu (4.10) je P 00 = ·
∞ X
−100iq i−2 (1 − q i )98 (100iq i − q i − i + 1)ci ,
c ∈ (0, 1).
i=1
Konvexnost a konk´avnost nelze t´ımto zp˚ usobem urˇcit, jelikoˇz nulov´ y bod i i pro v´ yraz (100iq − q − i + 1) z´avis´ı na i a tˇeˇzko urˇc´ıme, pro kter´e hodnoty bude funkce konvexn´ı a pro kter´e konk´avn´ı.
Pravdepodobnost vyhry
Na obr´azku 4.2 je zobrazena z´avislost pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce na spr´avn´e odpovˇedi soupeˇr˚ u. Pravdepodobnost vyhry hlavniho hrace v zavislosti na spravne odpovedi souperu 1 p=0.1 p=0.2 0.9 p=0.3 p=0.4 0.8 p=0.5 p=0.6 0.7 p=0.7 p=0.8 0.6 p=0.9 0.5 0.4 0.3 0.2 0.1 0
0
0.2 0.4 0.6 0.8 Pravdepodobnost spravne odpovedi hlavniho hrace
1
Obr´azek 4.2: Pr˚ ubˇeh pravdˇepodobnosti v z´avislosti na spr´avn´e odpovˇedi soupeˇr˚ u
22
5 Simulace Posledn´ı ˇca´st´ı t´eto bakal´aˇrsk´e pr´ace je simulace hry 1 proti 100 v programu MATLAB. Jedn´a se o programovou simulaci televizn´ı vˇedomostn´ı soutˇeˇze 1 proti 100. Program n´ahodnˇe generuje spr´avn´e a chybn´e odpovˇedi hlavn´ıho hr´aˇce a soupeˇr˚ u, na z´akladˇe vstupn´ıch parametr˚ u simuluje v´ ysledek hry a vypoˇc´ıt´av´a odhad pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce nad soupeˇri. Vstupn´ımi parametry t´eto simulace jsou pouze pravdˇepodobnosti spr´avn´ ych odpovˇed´ı hlavn´ıho hr´aˇce a soupeˇr˚ u, tedy promˇenn´e p a q. V simulaci nejprve n´ahodnˇe vygenerujeme spr´avn´e a ˇspatn´e odpovˇedi vˇsech hr´aˇcu vystupuj´ıc´ıch ve hˇre 1 proti 100. D´ale zaznamen´ame poˇcet soupeˇr˚ u, kteˇr´ı odpovˇedˇeli ˇspatnˇe, ti automaticky vypad´avaj´ı ze hry, a vypoˇc´ıt´ame v´ yˇsi finanˇcn´ı odmˇeny pro hlavn´ıho hr´aˇce. Simulace prob´ıh´a do t´e doby, dokud hlavn´ı hr´aˇc neodpov´ı ˇspatnˇe, nebo dokud nevypadnou vˇsichni jeho soupeˇri. Odpovˇedi hlavn´ıho hr´aˇce a soupeˇr˚ u vygenerujeme pomoc´ı funkce rand(1). Funkce rand(1) generuje n´ahodn´e ˇc´ıslo s rovnomˇern´ ym rozdˇelen´ım na intervalu (0,1). Na z´akladˇe vstupn´ıch paramatr˚ u urˇc´ıme, zda-li odpovˇedˇel hlavn´ı hr´aˇc a soupeˇri spr´avnˇe nebo chybnˇe. Pokud je vygenerovan´a hodnota pomoc´ı funkce rand(1) menˇs´ı neˇz pravdˇepodobnost spr´avn´e odpovˇedi, je vytvoˇrena hodnota 1, tedy spr´avn´a odpovˇed’. V opaˇcn´em pˇr´ıpadˇe je vytvoˇrena hodnota 0, tedy ˇspatn´a odpovˇed’. Simulaci nech´ame probˇehnout celkem 10 000kr´at a z tˇechto 10 000 pozorov´an´ı vypoˇc´ıt´ame pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce nad soupeˇri ve tvaru P =
n , 10000
kde n je poˇcet simulac´ı. kdy hlavn´ı hr´aˇc ve hˇre zv´ıtˇezil. V n´asleduj´ıc´ıch tabulk´ach 5.1 a 5.2 jsou zobrazeny data z´ıskan´a analyticky pomoc´ı model˚ u v´ ypoˇctu a data z´ıskan´a ze simulace. Jak je z tabulek vidˇet, data z´ıskan´a ze simulace se liˇs´ı maxim´alnˇe o 0,5 procentn´ıho bod˚ u, neˇz data z´ıskan´a analyticky. Data z´ıskan´a pomoc´ı simulace jsou tedy celkem pˇresn´a ve srovn´an´ı s analyticky z´ıskan´ ymi hodnotami.
23
Simulace p/q 10 % 20 % 30 % 40 % 50 % 60 % 70 % 80 % 90 %
10 % 0,42 % 1,91 % 4,82 % 9,53 % 16,45 % 25,99 % 38,62 % 54,82 % 75,10 %
20 % 0,06 % 0,48 % 1,67 % 4,19 % 8,74 % 16,19 % 27,62 % 44,30 % 67,81 %
30 % 0,01 % 0,13 % 0,58 % 0,65 % 4,51 % 9,80 % 19,26 % 35,16 % 60,64 %
40 % 0% 0,02 % 0,16 % 0,17 % 2,03 % 5,32 % 12,4 % 26,47 % 53,02 %
50 % 0% 0% 0,03 % 0,03 % 0,71 % 2,39 % 6,95 % 18,16 % 43,91 %
60 % 0% 0% 0% 0% 0,17 % 0,78 % 3,05 % 10,59 % 33,61 %
70 % 0% 0% 0% 0% 0,02 % 0,13 % 0,83 % 4,48 % 21,83 %
80 % 0% 0% 0% 0% 0% 0,01 % 0,08 % 0,89 % 9,52 %
90 % 0% 0% 0% 0% 0% 0% 0% 0,01 % 0,94 %
80 % 0% 0% 0% 0% 0% 0% 0,08 % 0,97 % 9,36 %
90 % 0% 0% 0% 0% 0% 0% 0% 0,01 % 0,98 %
Tabulka 5.1: Analyticky z´ıskan´e hodnoty pravdˇepodobnost´ı p/q 10 % 20 % 30 % 40 % 50 % 60 % 70 % 80 % 90 %
10 % 0,58 % 2,00 % 4,88 % 9,54 % 16,20 % 25,81 % 38,52 % 54,40 % 75,42 %
20 % 0,51 % 0,43 % 1,84 % 3,92 % 8,51 % 16,17 % 27,50 % 44,23 % 67,80 %
30 % 0,01 % 0,15 % 0,48 % 1,49 % 4,69 % 10,24 % 18,77 % 35,11 % 60,5 %
40 % 0% 0,03 % 0,2 % 0,74 % 2,04 % 4,99 % 12,53 % 26,11 % 53,49 %
50 % 0% 0,01 % 0,04 % 0,14 % 0,58 % 2,16 % 6,74 % 18,10 % 44,22 %
60 % 0% 0% 0% 0,04 % 0,12 % 0,72 % 3,00 % 10,25 % 33,03 %
70 % 0% 0% 0% 0% 0% 0,09 % 0,81 % 4,10 % 21,89 %
Tabulka 5.2: Hodnoty pravdˇepodobnost´ı z´ıskan´e pomoc´ı simulace
D´ale jsme ze zaznamenan´ ych dat pro zaj´ımavost vytvoˇrili 2 histogramy pro zvolen´e vstupn´ı parametry. Na opr´azku 5.1 je zobrazen histogram poˇctu kol v jednotliv´ ych simulac´ıch a na obr´azku 5.2 je zobrazen histogram poˇctu vyˇrazen´ ych soupeˇr˚ u v jednom kole.
24
Simulace
Histogram poctu kol 3000 p=0.7,q=0.5 2500
Cetnost
2000
1500
1000
500
0
0
2
4
6
8 Pocet kol
10
12
14
Obr´azek 5.1: Histogram poˇctu kol
Histogram poctu vyrazenych souperu v jednom kole 3000 p=0.7,q=0.5 2500
Cetnost
2000
1500
1000
500
0
0
10
20
30 40 Pocet souperu
50
60
70
Obr´azek 5.2: Histogram poˇctu vyˇrazen´ ych soupeˇr˚ u v jednom kole
25
6 Z´avˇer C´ılem t´eto bakal´aˇrsk´e pr´ace bylo zkoumat pravdˇepodobnost v´ıtˇezstv´ı hlavn´ıho hr´aˇce ve hˇre 1 proti 100 a prov´est simulaci t´eto hry. K v´ ypoˇctu t´eto pravdˇepodobnosti byly vyuˇzity tˇri modely v´ ypoˇctu: model absorpˇcn´ıho stavu Markovsk´eho ˇretˇezce, model rozkladu podle d´elky hry a model podle okamˇziku prvn´ı chybn´e odpovˇedi hlavn´ıho hr´aˇce. Jako prvn´ı metoda byla zvolena metoda rozklad podle d´elky hry. V tomto modelu jsme hru vyj´adˇrili tak, ˇze hlavn´ı hr´aˇc odpov´ıdal na vˇsechny zadan´e ot´azky spr´avnˇe a alespoˇ n jeden jeho soupeˇr s n´ım postoupil do posledn´ıho kola, kde odpovˇedˇel chybnˇe. V´ ysledn´ y tvar funkce z´ıskan´ y pomoc´ı tohoto modelu je velmi sloˇzit´ y a velmi tˇeˇzko jsme z nˇej nˇeco vyˇcetli. Tento tvar jsme museli aproximovat a vyj´adˇrit hodnoty numericky pro pˇredstavu v´ ysledku. Druh´ ym modelem byl zvolen pˇr´ıstup v´ ypoˇctu podle prvn´ı chybn´e odpovˇedi hr´aˇce. V tomto modelu hra prob´ıhala tak, ˇze hlavn´ı hr´aˇc odpovˇedˇel chybnˇe na ot´azku pozdˇeji neˇz vˇsichni jeho soupeˇri a on zv´ıtˇezil. Tento model d´av´a nejlepˇs´ı v´ ysledek, jelikoˇz tvar funkce jsme mohli explicitnˇe seˇc´ıst a z´ıskali jsme koneˇcnou sumu oproti pˇredchoz´ımu modelu, kde byl tvar funkce vypoˇc´ıt´an pomoc´ı dvou nekoneˇcn´ ych souˇct˚ u. Tˇret´ım a posledn´ım modelem byl model absorpˇcn´ıho stavu Markovsk´eho ˇretˇezce. Pr˚ ubˇeh hry jsme modelovali pomoc´ı markovsk´eho ˇretˇezcem s mnoˇzinou stav˚ u, kter´e reprezentovali poˇcty ˇzij´ıc´ıch soupeˇr˚ u, kromˇe posledn´ıho stavu kter´ y reprezentoval prohru hlavn´ıho hr´aˇce. V tomto modelu n´as zaj´ımala absorpce ze stavu, kter´ y pˇredstavoval poˇc´atek hry, tedy vˇsech 100 soupeˇr˚ u a hlavn´ı hr´aˇc byli ve hˇre, do stavu, kde ˇzil pouze hlavn´ı hr´aˇc. V tomto modelu jsme z´ıskali soustavu sta rovnic, jejichˇz explicitn´ı vyj´adˇren´ı bylo velmi n´aroˇcn´e. Opˇet jsme tedy v´ ysledek vyj´adˇrili numericky, pomoc´ı softwaru MATLAB. D´ale jsme shrnuli v´ ysledky jednotliv´ ych metod a vykreslili r˚ uzn´e grafy pravdˇepodobnosti v´ yhry hlavn´ıho hr´aˇce nad soupeˇri ve hˇre 1 proti 100. Jak jiˇz bylo zm´ınˇeno, nejelegantnˇejˇs´ı tvar funkce jsme z´ıskali pomoc´ı modelu podle prvn´ı chybn´e odpovˇedi hr´aˇce. ˇ Ctvrt´ a kapitola byla vˇenov´ana vyˇsetˇrov´an´ı pr˚ ubˇehu pravdˇepodobnosti, kdy jsme vyˇsetˇrili monotonii a konvexnost a konk´avnost funkce pˇredstavuj´ıc´ı pravdˇepodobnost v´ yhry hlavn´ıho hr´aˇce ve hˇre 1 proti 100. K vyˇsetˇren´ı 26
Z´avˇer
pr˚ ubˇehu byly pouˇzity tvary funkc´ı z´ıskan´ ych v prvn´ıch dvou modelech. Posledn´ı kapitola byla vˇenov´ana simulaci hry 1 proti 100 v softwaru MATLAB. V t´eto kapitole byl pops´an program, kter´ ym byla simulace provedena a porovn´any v´ ysledky z´ıskan´e analyticky a v´ ysledky z´ıskan´e pomoc´ı simulaˇcn´ı studie. Hodnoty z´ıskan´e pomoc´ı simulace se t´emˇeˇr shodovaly s analyticky z´ıskan´ ymi hodnotami. Pokud shrneme v´ ysledky t´eto bakal´aˇrsk´e pr´ace, podaˇrilo se n´am z´ıskat pˇredstavu o tom, jakou m´a hr´aˇc v konkr´etn´ı televizn´ı vˇedomostn´ı soutˇeˇzi 1 proti 100 pravdˇepodobnost v´ yhry. Jelikoˇz jsme zanedbali vˇsechny v´ yhody hlavn´ıho hr´aˇce v t´eto hˇre, pravdˇepodonost v´ yhry by mˇela b´ yt ve skuteˇcnosti vˇetˇs´ı, neˇz jsme vypoˇc´ıtali.
27
Literatura ´ [1] Reif J., Kobeda Z.: Uvod do pravdˇ epodobnosti a spolehlivosti Nakladatelstv´ı Z´apadoˇcesk´e univerzity, Plzeˇ n 2000 [2] Mandl P.: Pravdˇ epodobnostn´ı dynamick´ e modely Nakladatelstv´ı Academia, Praha 1985 [3] Pr´aˇskov´a Z., Lachout P.: Z´ aklady n´ ahodn´ ych proces˚ u Nakladatelstv´ı Karolinum, Praha 2001
28
