Aktuell information för SF1904

Komplettering

Tentamen 23/5

Tentamen 7/6

Grupp 3 nedlagd

I fortsättningen blir salarna enligt följande:

Föreläsningsinformation

Pratade om Littles formler som ger möjlighet att av en av l, l_q, w, w_q beräkna de övriga. Gav ett intuitivt resonemang om hur dessa formler kan ses som tillämpning av principen "what goes in must come out", dvs att flöde in i systemet måste vara flöde ut ur systemet, t ex att (i asymptotiskt skede)

λ=E(antal betjäningar)μ

och att l=l_q+E(antal betjäningar)

samt att

l_q=λw_q som kan tolkas som att när kunden kommer ser han l_q kunder och ovanstående relation säger att när han lämnar kön efter tiden w_q har λw_q kunder kommit och alltså står i kön.

Pratade lite om M/M/c och dessutom om förlustsystem (t ex utan kö) där vissa kunder ej ansluter sig. Vidare lite om generalisering där anslutningssannolikheten varierar med antalet kunder i systemet.

Spillde några ord om M/G/1-kön där man har allmän betjäningstidsfördelning.

Gick igenom kopplade köer (Jackson-nätverk) med ett exempel om ett datasystem med inloggning, CPU och I/O-enhet.

Pratade om en enkel återkopplad kö och nämnde att utprocesserna (ut ut systemet) i Jackssonnätverk är Poisson-processer men att flödena inne i nätverket inte är det i allmänhet. I återkopplingssystemet kan ju in-intensiteten utifrån vara låg (så att kunder kommer med stora tidsmellanrum) men återkopplingen vara sådan att betjänaren får jobba intermittent (samma kund loopar runt en massa gånger).

Ungefärligt innehåll.

11-05-06 Födelse-döds-processer där övergångsintensitetsmatrisen Q har bandstruktur, dvs processen kan bara hoppa upp ("födelse") eller ner ("död") ett steg i taget. Som exempel gavs kösystemet M/M/1 där kunder anländer enligt en Poissonprocess, eventuellt köar och sen får betjäning som tar en exponentialfördelad tid.

Villkor för att processen skall vara ergodisk, dvs att den har en unik gränsfördelning (asymptotisk fördelning) oavsett starttillstånd.

Tog fram asymptotiska fördelningen för M/M/1-systemet direkt och gick igenom den allmänna algoritm som finns i formelsamlingen för att hitta den stationära fördelningen för födelse-dödsprocesser.

Behandlade sedan M/M/2-systemet, dvs ett system där man har två parallella betjäningsstationer och en totalordnad kö samt har kundankomster enligt en Poissonprocess med intensitet λ. Visade hur Q-matrisen såg ut - återigen en födelse-dödsprocess och vi kunde få fram den stationära (asymptotiska) fördelningen med hjälp av algoritmen i formelsamlingen om λ<2μ som var krav för existens av stationärfördelning.

Gick igenom alla beteckningar (en hel sida(!) i formelsamlingen) inom köteorin samt hur det såg ut för M/M/1- respektive M/M/2-systemen där vi kunde se statuionära fördelningen samt förväntad kölängd l_q. Visade hur man kunde få l respektive l_q i M/M/1-systemet.

Ungefärligt innehåll.

11-04-28 Återknöt lite till hur Q kunde tolkas både vad gäller diagonalelementen och icke-diagonalelementen.

Det fantastiska är att det är lätt att få fram Q i en konkret situation samt elementen i Q är lätta att tolka. Gav ett exempel av tillförlighetskaraktär (Exempel 6.3 i kompendiet).

Definierade ergodiska processer samt att en irreducibel kedja (eller mer allmänt att kedjan har bara en sluten irreducibel delklass) på ett ändligt E är ergodisk. För kedjor med oändligt E krävs också att det existerar en stationär fördelning. Notera att den inbäddade hoppkedjan mycket väl kan få vara periodisk.

Definierade stationär fördelning och visade att den kan fås genom att lösa 0=πQ. Notera att man kan stryka godtycklig ekvation utom normeringsekvationen.

Visade hur ekvationssystemet 0=πQ relaterade till ekvationssystemet π=πP(t) eftersom P(h)=I+hQ+o(h).

Beskrev hur π_i kan tolkas som andel av tiden som en ergodisk kedja ligger i tillstånd i. Du kan läsa mer om detta här.

Diskuterade lite om kalkyler i samband med absorptionsproblem. I kontinuerlig tid svarar absorberande tillstånd mot att motsvarande rad i Q består av 0:or.

Införde Poissonprocessen som en matematisk modell för "händelser som inträffar fullständigt slumpmässigt i tiden" och framställde den på 3 olika sätt som kan visas vara ekvivalenta.

Nämnde en möjlig generalisering i form av förnyelseprocess där tiderna mellan händelser är oberoende likafördelade men inte nödvändigtvis exponentialfördelade.

Den i kursen aktuella generaliseringen är födelseprocesser som hoppar upp ett steg i taget och tiden mellan hopp nr k och nr k+1 är Exp(λ_k). Risken finns att en sådan process "exploderar", dvs hinner upp till oändligheten på ändlig tid - något som gör processen icke-reguljär.

Ungefärligt innehåll.

11-04-12 Lite om diskreta markovkedjor med oändligt tillståndsrum, där man måste kräva att en stationär fördelning finns (kedjan kan försvinna ut mot oändligheten). Lite om hur man tekniskt kan lösa π=πP genom att stryka godtycklig ekvation och ersätta den med normeringsekvationen.

Inledning om kontinuerlig tid. Införde övergångssannolikheterna p_ij(t) som bildar matrisen P(t). Visade Chapman-Kolmogorovs ekvationer dvs P(s+t)=P(s)P(t) och konstaterade att detta innebär att det är svårt att ange P(t) direkt.

Lite om kravet att processen skall vara reguljär, dvs bara ha ändligt många övergångar på ändlig tid.

Införde övergångsintensitetsmatrisen (generatorn) Q som är P'(0) dvs elementvisa derivatan av p_ij(t) i 0:an, dvs P(h)=I + hQ + o(h). Detta gav Komogorovs framåt- respektive bakåtekvationer som visar att vi kan få P(t) ur Q.

Pratade lite om minneslöshet hos exponentialfördelningen. Införde felintensiteter och hur dessa kan tolkas, samt att exponentialfördelningen är den enda fördelningen med konstant felintensitet.

Bevis för att minimum av exponentialfördelade är exponentialfördelad och att vilken som blir minst är oberoende av tiden till minimum.

Visade att uppehållstiden i ett tillstånd för en Markovprocess måste vara exponentialfördelad Exp(q_i) säg, eftersom detta är den enda minneslösa fördelningen.

På diagonalen i Q står q_ii som måste vara negativt och visade att q_i=-q_ii så man kan i Q-matrisen på diagonalen läsa av uppehålsstiderna fördelningar (de är Exp(q_i).

Ungefärligt innehåll.

11-03-31 Fortsättning om Markovkedjor i diskret tid.

Klassifikation av tillstånd för Markovkedjor, speciellt kommunicerande tillstånd (man kan gå fram och tillbaka mellan tillstånden) och irreducibla delklasser (alla tillstånd kommunicerar), slutna delklasser (inga pilar ut ur delklassen),

Begreppet ergodisk kedja, dvs en där fördelning efter lång tid inte beror av startfördelningen.

Visade att det alltid finns minst en sluten irreducibel delklass i en kedja med ändligt tillståndsrum E genom att utnyttja att tvåvägs-kommunikation är en ekvivalensrelation. För den intresserade finns här ett enkelt bevis för att en ändlig Markovkedja alltid har minst en stationär fördelning.

Satsen att en kedja med en enda sluten irreducibel delklass har en unik stationär fördelning.

Begreppet period för ett tillstånd, dvs största gemensamma delare till de tänkbara utflyktlängderna från tillståndet. Om perioden är 1 kallas tillståndet aperiodiskt. Satsen att två tillstånd som kommunicerar har samma period.

Huvudsatsen att en ändlig kedja är ergodisk om och endast om den bara har en enda sluten irreducibel delklass och denna är aperiodisk.

Den asymptotiska fördelningen måste vara den stationära om kedjan är ergodisk, dvs kan fås genom att lösa (det överbestämda) ekvationssystemet π=πP samt normeringsekvationen. Borde ha nämnt att man kan stryka vilken ekvation som helst utom normeringsekvationen.

Beskrev lite översiktligt hur periodiska kedjor uppträden samt hur det allmänna uppträdandet av ändliga kedjor ser ut. Det finns ett antal slutna irreducibla delklasser samt (eventuellt) ett antal genomgångstillstånd. Med A-kedjemetodik kan man beräkna sannolikheten att absorberas i respektive sluten irreducibel delklass. Är dessa sen aperiodiska konvergerar fördelningen mot den stationära i respektive sluten irreducibel delklass.

Konvergensen mot den asymptotiska fördelningen går mycket snabbt.

Ett enkelt kriterium för att kedjan skall vara ergodisk är att P har en fylld kolumn.

Markovkedjor används för simulering inom Markov Chain Monte Carlo (MCMC) som är en mycket kraftfull och användbar teknik.

Visade att i fördelningen i en ergodisk kedja kan asymptotiska sannolikheterna π_i fås som andelen av tiden som kedjan tillbringar i tillståndet i. Detta ger π_i=1/E(T_i) där T_i är tiden mellan två besök i tillstånd i .

Nämnde att Googles sidsorteringsalgoritm Pagerank baseras på den stationära fördelningen i den Markovkedja som beskriver länkstrukturen på Internet. Denna erhålls dock inte genom att lösa ekvationssytemet utan i stället genom att stega sig fram genom upprepad multiplikation av övergångsmatrisen.

Ungefärligt innehåll.

11-03-22

Repetition av betingad sannolikhet samt lagen om total sannolikhet. Introduktion till Markovteori. Allmänna stokastiska processer och markovegenskapen (minneslöshet). Markovprocesser med diskreta tillståndsrum (markovkedjor). Definierade viktiga begrepp, speciellt övergångsmatriser och obetingade sannolikheter och visade Chapman-Kolmogorovs ekvationer. Begreppet stationärfördelning, dvs en fördelning som uppfyller π=πP. Beskrev att huvudproblemet kommer att vara att uttala sig om Markovkedjans uppträdande efter lång tid.

För den intresserade finns här ett enkelt bevis för att en Markovkedja med ändligt tillståndsrum E alltid har minst en stationär fördelning.

Inledning till absorption för vissa Markovkedjor och illustrerade med ett tärningsspel enligt uppgift 16 i kompendiet.

Ungefärligt innehåll.