Introduction Review of Probability - Whitman College

1 markov CHAINS:ROOTS,THEORY, thispaper is todevelopanunderstandingof thetheoryunderlyingMarkov thisend,we willreviewsomebasic,relevant Probability willprogressto theMarkov chainsthemselves,andwe willconcludewitha casestudyanalysisfromtwo chainanalysishasitsrootsin prob-ability theory, so we beginwitha reviewof Probability . Thereviewwillbe briefandwillfocusmainlyontheareasof Probability theorythatarepertinent to markov discipline,it is important to be familiarwiththelan-guageof Probability beforelookingat ,wewillbeginwitha fewde nitionsanda fewmorewillbe introducedlateras necessary.

2 In Probability , thesamplespace,S, is thesetofallpossibleoutcomesforanexperime nt. Any subset,F, of thesamplespaceSis knownas anevent. For example,SheldonRossexplainsinhistextthat if theexperiment consistsof a cointoss,thenS=f(H)eads;(T)ailsgis thesamplespace[4].F=fHgis theevent thattheoutcomeof the ipis headsandE=fTgwouldbe theevent thattheoutcomeof thetossis , if theexperiment consistsof two successivecoin ips,thenS=f(H; H);(H; T);(T; H);(T; T)gis thesamplespace(where(H; T) denotesthatthe rstcoincameupheadsandthesecondcoincameup tails).F=f(H; H)gis theeventthatboth ipscameupheads,E=f(H; H);(H; T);(T; H)gis theevent thatheadsshowsuponat leastoneof thecoinsandso two eventsEandFof a samplespaceS, denotedE[F, is de nedas thesetof alloutcomesthatarein (clockwisefromtopleft):theeventsEandF, theintersectionE\F,thecomplementEc, andtheunionE[FFor , denotedE\F, is de nedas theoutcomesthatarein bothEandF.]]

3 Thecomplementof aneventEis thesetof allpoints in thesamplespacethatarenotinE. Thecomplement is writtenEc. Soif we reexaminetheexperimentof ippingtwo coins,theneveryoutcomein eitherEorFor bothisF[E=f(H; H);(H; T);(T; H)g. Theonlyoutcomesimultaneouslyin bothEandFisF\E=f(H; H)g. Lastly, thesetof outcomesinSthatarenotinEisEc=f(T; T)g. Theseideascanbe representedvisuallyby a theVenndiagramwe cansay thattheentireareain thebox is each ofthecirclesrepresents an event. Thepartwherethetwo interiorsoverlapis is theunion,andtheareathatis outsideoneof thecirclesisthecomplement to theevent representedby of bothof thecoin ippingexperiments,theexperimenterhasvery littlecontrolover theoutcomeof the ip(al-thoughI hearthatoneof thechemistryprofessorscanmake a coincomeupheadseverytimeby ippingit in such a way thatit doesn'tactu-allyrotateendover end,it justoscillatesback andforthcreatingtheMARKOV CHAINS:ROOTS,THEORY, ANDAPPLICATIONS3illusionthatit is rotating[7]).]

4 Thus it is oftendesirableto determinetheprobability thata speci cevent or essentiallythefractionof timesthatwe expecta speci cevent to , we writetheprobabilityof aneventFin thesamplespaceSasP(F), andwe assumethatP(F) is de ned,alongwiththefollowingthreeconditions :(i)0 P(F) 1;(ii)P(S) = 1;(iii)For any sequenceof eventsF1; F2; : : : ; Fnthataremutuallyexclusive ( empty),thenP 1[n=1Fn!=1Xn=1P(Fn):The rstof theseconditionssimplystatesthattheevent can'thappenlessthannever or morethaneverytimetheexperiment is willhave thattheprobabilitiesof alltheevents thatdon'toverlapaddupto give us theprobability thatoneof theseeventsis goingto nitionof Probability we canlookatthe rstcoin ipexperiment andsay thatif thecoinis wellbalancedandthe ipis fair,thenP(fHg) =12(Ifthe ipper is thatchemistryprofessorthenP(fHg) = 1).]

5 In thesecondcoin ipexperiment, withafair iptheprobability thateach ipwillyielda tailisP(f(T; T)g) = nitionof Probability , we canderive theprobabilitiesofunionsandcomplements as(i)P(E[F) =P(E) +P(F) P(E\F)(lookat theVennDiagram(Figure1) forvisualcon rmationof this)(ii)P(Ec) = 1 P(E) is thatwe sometimesneedto gureouthow likelyit is thataneventEwillhappenassumingor giventhatanothereventFhappens example,imaginethatI have eight tootsiepops,threered,threeblueandtwo oneof my tootsiepops,butI say thatin orderto getoneyou needto pick, withoutlooking,onethathasanIndianshootin ga give youa betterchanceatwinningthegame,I tellyouthatoneof thebrownoneshastheIndian,two of theredoneshave himandoneof ,youwouldpick oneof theredtootsiepopsbecauseyouhave a two4 TIMMARRINAN outof threechanceof gettingto keepthesucker.]

6 Andthatinstinctivecalculationis anexampleof conditionalprobability. Theprobability ofthesucker havinganIndianonit at allis48=12, buttheprobability ofthethewrapper havinganIndianonit giventhatit is redis23. Nowwe justhave to make thatinstinctive calculationexplicitso thatwecanuseit froma samplespaceS, we denotetheconditionalprobabilityofEgivenF asP(EjF) andit is calculatedusingtheformula(1)P(EjF) =P(E\F)P(F):AsRossnotes,thisformulamakes themostsenseif youthinkaboutit as theeventFoccurs,thenin orderforEto alsooccurtheactualoccurrencemustbe a point in theintersection,E\F[4].

7 Also,sincewe know thatFhasoccurred,it becomesournewsamplespaceso we take theprobability ofE\Frelative to theprobability ofFas is shownin Equation1. Sonow we have anequationthatrequiresusto know whatP(E\F) of theintersectionoftwo events is usuallynotveryobvious,butfortunatelywe canusually gureouttheP(EjF) termintuitivelyjustlike we thatis thecasethenwe canrewriteEquation1 as(2)P(EjF)P(F) =P(E\F):Withthetootsiepops,Ewas theevent thatthewrapper hada pictureof anIndianonit,andFwastheevent thatthewrapper cancalculatetheprobability of theintersectionof thesetwo events asP(E\F) =P(EjF)P(F)= 23 38 =14.

8 Which makes sensebecauseE\Frepresents theevent thatthewrapperis bothredandhasan Indianwhich happenson two of theeight tootsiepops(14of thetime).Inthisexampleit wouldhave beeneasytocomputetheprobability of theintersectiondirectly, butoftenit isnecessaryto might occurthattheconditionalprobability of aneventEgivenaneventFis thesameas theprobability ofEby of areMARKOV CHAINS:ROOTS,THEORY, ANDAPPLICATIONS5de nedasindependentwhenP(E\F) =P(E)P(F), andEquation1 showsthatthisimpliesP(EjF) =P(E) (andalsoP(FjE) =P(F)).Thede nitionof independencecanbe extendedto ; E2; : : : ; Enaresaidto be inde-pendent if foreverysubsetE10; E20; : : : ; Er0, (r0 n), of theseeventsP(E10\E20\: : :\Er0) =P(E10)P(E20): : : P(Er0)or theprobability of theintersectionof alltheevents in thesubsetisequaltotheproductof theprobability of each of theevents in thesubset[4].

9 Intuitively, theeventsE1; E2; : : : ; Enareindependent if theknowledgeof theoccurrenceof any of theseevents hasnoe ectontheprobability of any otherevent. Usingthesenewfoundmanipulationsofprobabi lity, we canunderstandanimportant resultknownas Bayes' ' ; F2; : : : ; Fnaremutuallyex-clusive events such thattheirunionis thesamplespaceS. Inotherwords,exactlyoneof thoseevents [i=1(E\Fi)andusingthefactthetheeventsETF i; i= 1;2; : : : n;aremutuallyexclusive, we obtainthatP(E) =nXi=1P(E\Fi)(3)=nXi=1P(EjFi)P(Fi):(4)Th us,Equation4 showshow, forgiven eventsF1; F2.]

10 Fnof whichoneandonlyonecanoccur,we cancomputeP(E) by rst\condition-ing"uponwhich oneof , it statesthatP(E) isequalto a weightedaverageofP(EjFi), each termbeingweightedbytheprobability of theevent onwhich it is thatEhasoccurredandwe areinterestedin deter-miningwhich oneof we treediagramto helpvisualizetheproblemP(FjjE) =P(E\Fj)P(E)(5)P(FjjE) =P(EjFj)P(Fj)Pni=1P(EjFi)P(Fi):(6)We callEquation6 Bayes' helpputBayes'formulainto somecontext,let'slook at ctestthattheyareusingaccuratelycomesuppo sitive forcoke 90%of thetime,butit alsoshowsa falsepositive 5%of thetimewhenno cocaineis actuallypresent.