Aktuell information för SF1904

Tentamen

Betygsgränserna var FX 18, E 20, D 27, C 33, B 39, A 45.

Komplettering av tentamen

Registrering

Föreläsningsinformation

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

Pratade om system med flera sorters kunder där man ej får födelse-dödsprocesser men som naturligtvis ändå kan analyseras.

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 en videobutik med godishylla, chipshylla och filmhylla.

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.

10-11-23

Påminde om 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.

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.

Föreläsningsinformation

Beskrev hur man ur Q kan få fram P(t)-matrisen med hjälp av Kolmogorovs fram/bakåt-ekvationer samt hur man kan få ett system av kopplade differentialekvationer för de obetingade sannolikheterna dvs p'(t)=p(t)Q.

Det fantastiska är nu 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.

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.

10-11-08

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.

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.

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.

Införde övergångsintensitetsmatrisen Q som är P'(0) dvs elementvisa derivatan av p_ij)(t) i 0:an. På diagonal 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.

Föreläsningsinformation

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.

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

10-10-25

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 ändlig Markovkedja 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.