Aktuell information för SF1904

Tentamen

Kompendiet

Föreläsningsinformation

13-05-03

Sista föreläsningen! Köteori där speciellt M/M/2 gicks igenom både via direkt kalkyl och via formelsamlingen. Littles formler "härleddes" och visade att dessa kan använda kunskap om (t ex) förväntad kölängd för att få förväntad kötid, förväntad tid i systemet samt förväntat antal i systemet.

Pratade om att Littles formler 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 modifikationer av M/M/2 där t ex betjäningsintensiteten ökar då många är i systemet eller att potentiella kunder bara ansluter sig med en viss sannolikhet om det är många i systemet. Tycker personligen detta modellerande är den mest intressanta aspekten av köteorin.

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 också om en enkel återkopplad kö och nämnde att utprocesserna (ut ur 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.

13-04-24

Friskade upp minnet om Poissonprocess och speciellt tolkningen som en modell för fullständigt slumpmässiga händelser i tiden och betonade att tiden mellan händelser (hopp) är Exp(λ). Visade på generaliseringar som icke-homogen Poissonprocess där sannolikheten att en händelse ska inträffa i (t,t+h) beror av t. Intervallängden h tänkes som alltid som mikroskopiskt. Vidare kan man generalisera processen till en allmän förnyelseprocess där tiderna mellan händelserna har en annan fördelning än exponentialfördelningen. Vidare kan man ha Poissonprocesser i planet (en bra modell för åsknedslag) där antalet händelser i en viss area är Poissonfördelat med väntevärde proportionellt mot arean. Dessutom antar man att antalet händelser i disjunkta mängder är oberoende.

I kursen diskuteras framför allt generaliseringen (ren) födelseprocess där uppehållstiden i tillstånd i är exponentialfördelad med intensitet λ_i varefter processen hoppar upp ett steg. Diskuterade att vi kan få explosion, dvs att man når oändligheten på ändlig tid och visade (tillräckligt och nödvändigt) villkor för att detta inte skall ske.

Tonvikten las dock på 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.

Visade hur man kan få väntevärdet för förväntat antal i systemet och förväntat antal i kön direkt ur stationära fördelningen.

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 en antal av beteckningarna (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 stationära fördelningen samt förväntad kölängd l_q.

Ungefärligt innehåll.

13-04-17

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

Härledde Kolmogorovs framåt- respektive bakåtekvationer som visar att vi kan få P(t) ur Q. Dessutom skrev jag upp det konkreta systemet av kopplade diffekvationer p'(t)=p(t)Q som behövs för att erhålla de obetingade sannolikheterna.

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).

Borde ha beskrivit 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.

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.

Ungefärligt innehåll.

13-04-10

Avslutade avsnittet om diskret tid. 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 .

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).

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.

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ållsstidernas fördelningar (de är Exp(q_i).

Elementen vid sidan av diagonalen gav sannolikheterna för hopp. Man hoppar med sannolikhet proportionellt mot icke-diagonalelementen dvs sannolikhet att hoppa från i till j är q_ij/q_i.

Borde också ha hunnit med att demonstrera hur lätt det är att ta fram Q-matrisen i en konkret situation men det får anstå till nästa föreläsning.

Ungefärligt innehåll.

13-03-27

Har lagt till detta godis om A-kedjor: Här är ett alternativt bevis för att (asymptotiskt) all massa i en ändlig A-kedja hamnar i de absorberande tillstånden. 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. Nämnde förra gången 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.

Borde också ha pratat om att i en ergodisk kedja är π_i=1/E(T_i) där T_i=tiden fr o m ett besök i tillstånd i till nästa besök där. Finns ett bevis här.

Konvergensen mot den asymptotiska fördelningen går mycket snabbt. Detta kan ge ett alternativt bevis för att en ändlig irreducibel, aperiodisk kedja är ergodisk. Man kan visa att P^k då är en fylld matris (alla element är >0) för något stort k. En sådan matris är då en kontraktiv avbildning i enlighet med "godiset" om feluppskattningen ovan och detta visar att kedjan alltmer närmas sig sin stationära fördelning.

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.

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.

13-03-20

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.

Här är ett alternativt bevis för att (asymptotiskt) all massa i en ändlig A-kedja hamnar i de absorberande tillstånden.

Ungefärligt innehåll.