Aktuell information för SF1904

Rättningsnorm.

Komplettering för de som erhållit betyget FX sker 19/6 kl 10-12 i sal L51. Kompletteringen är i form av två uppgifter av tentakaraktär.

Gränserna var A 44, B 38, C 32, D 26, E 20, FX 18.

12-05-15 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.

12-05-09

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 stationä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.

12-04-24

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

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.

Ungefärligt innehåll.

12-04-10

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.

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

12-03-27

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

Borde ha Nämnt 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.

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

Gav exemplen X_n=resultat av tärningskast n (lite urartat fall eftersom de är oberoende) samt X_n=poängsumman av n tärningskast och angav övergångsmatriserna och noterade att de båda var Markovkedjor.

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

Ungefärligt innehåll.