stochastische matrices
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
stochastische matrices
een stochatische matrix heeft steeds een eigenwaarde die gelijk is aan 1, en de rest van de eigenwaarden is dan in absolute waarde kleiner dan 1,
hoe toon je dit aan voor een algemene stochatische matrix?
en wat is de eigenvector die hoort bij eigenwaarde 1?
alvast bedankt
hoe toon je dit aan voor een algemene stochatische matrix?
en wat is de eigenvector die hoort bij eigenwaarde 1?
alvast bedankt
- Berichten: 1.460
Re: stochastische matrices
Poeh ja... Daar kun je op zich een complete minicursus over schrijven...
Het idee is echter dat een stochastische matrix op den duur naar een fase toe convergeert waarbij de matrix niet meer verandert als hij vermenigvuldigd wordt met een vector, de beginvector. Zoals je ziet sla ik een hoop stappen over, maar als je met zo'n vraag komt veronderstel ik maar even voor het gemak dat je wel al e.e.a. van het onderwerp afweet.
Goed, omdat hij convergeert naar één fase toe betekent dat dus dat de eigenvectoren (die de vector, of in praktische toepassingen: de verdeling van de beginhoeveelheid, op elk gewenst moment kan weergeven) allemaal op één na moeten convergeren ofwel te verwaarlozen zijn voor grote n ofwel in praktische toepassingen: na een lange tijd (als je n in jaren ziet bijv).
Zo komt het dus dat er een eigenwaarde is die precies 1 is, dat bepaalt dus op den duur de vorm van de fase waarin de matrix niet meer verandert van n naar n+1.
Hoe je dit aan kunt tonen? Dat kan vrij gemakkelijk, maar is dat interessant genoeg om te weten of is dat niet je echte vraag?
De eigenvector die hoort bij de eigenwaarde 1 is niet zo te omschrijven (ja of je moet al met die algemene beschouwing bezig zijn), maar het is afhankelijk van de matrix en beginvector, dus niet zo snel en eenduidig te bepalen...
Ik hoop dat het duidelijk is voor je! Wil je wat anders weten dan vraag maar.
Het idee is echter dat een stochastische matrix op den duur naar een fase toe convergeert waarbij de matrix niet meer verandert als hij vermenigvuldigd wordt met een vector, de beginvector. Zoals je ziet sla ik een hoop stappen over, maar als je met zo'n vraag komt veronderstel ik maar even voor het gemak dat je wel al e.e.a. van het onderwerp afweet.
Goed, omdat hij convergeert naar één fase toe betekent dat dus dat de eigenvectoren (die de vector, of in praktische toepassingen: de verdeling van de beginhoeveelheid, op elk gewenst moment kan weergeven) allemaal op één na moeten convergeren ofwel te verwaarlozen zijn voor grote n ofwel in praktische toepassingen: na een lange tijd (als je n in jaren ziet bijv).
Zo komt het dus dat er een eigenwaarde is die precies 1 is, dat bepaalt dus op den duur de vorm van de fase waarin de matrix niet meer verandert van n naar n+1.
Hoe je dit aan kunt tonen? Dat kan vrij gemakkelijk, maar is dat interessant genoeg om te weten of is dat niet je echte vraag?
De eigenvector die hoort bij de eigenwaarde 1 is niet zo te omschrijven (ja of je moet al met die algemene beschouwing bezig zijn), maar het is afhankelijk van de matrix en beginvector, dus niet zo snel en eenduidig te bepalen...
Ik hoop dat het duidelijk is voor je! Wil je wat anders weten dan vraag maar.
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>
-
- Berichten: 718
Re: stochastische matrices
Dat de matrix M een eigenwaarde 1 heeft is eenvoudig te bewijzen, immers de som van de elementen in elke kolom van de matrix is 1 en de som van de elementen in elke kolom van de matrix M-I is dus 0. Dit betekent dat de rijen van M-I lineair afhankelijk zijn en de matrix M-I is dus singulier.
De bijbehorende eigenvectoren zijn alle stabiele eindtoestanden van het stochastische proces. Waarom de overige eigenwaarden in absolute zijn kleiner dan 1 zijn daar moet ik nog even over nadenken maar wellicht speelt het feit dat elke eigenvector die bij zo'n eigenwaarde ongelijk aan 1 hoort er minstens een element kleiner dan 0 moet zijn (want alle eigenvectoren met alleen maar positieve elementen zijn stabiele eindtoestanden).
De bijbehorende eigenvectoren zijn alle stabiele eindtoestanden van het stochastische proces. Waarom de overige eigenwaarden in absolute zijn kleiner dan 1 zijn daar moet ik nog even over nadenken maar wellicht speelt het feit dat elke eigenvector die bij zo'n eigenwaarde ongelijk aan 1 hoort er minstens een element kleiner dan 0 moet zijn (want alle eigenvectoren met alleen maar positieve elementen zijn stabiele eindtoestanden).
-
- Berichten: 718
Re: stochastische matrices
Na wat verder denkwerk kom ik tot de conclusie dat de uitspraak dat de absolute waarden van de overige eigenwaarden kleiner zijn dan 1 niet correct is.
Neem als eenvoudig voorbeeld de matrix:
De eigenwaarden van deze matrix zijn +1 en -1 en de bijbehorende eigenvectoren zijn (0,5 0,5)T en (-0,5 0,5)T
Verder kun je nog iets verder komen in de karakterisering van de eigenvectoren van andere eigenwaarden dan 1:
Stel dat s(a) de som is van de elementen van a.
De stochastische matrix M heeft als eigenschap dat s(Ma)=s(a)
Voor een eigenvector geldt dus dat: s(a)=s(Ma)=s(λa)=λs(a)
Daaruit volgt λ=1 of s(a)=0
Het voorbeeld laat trouwens nog iets zien: een stochastisch proces beschreven door een stochastische matrix (heet dat niet een Markov-keten of laat mijn herinnering me in de steek?) hoeft niet perse voor iedere beginvector te convergeren.
Neem als eenvoudig voorbeeld de matrix:
Code: Selecteer alles
0 1
1 0
Verder kun je nog iets verder komen in de karakterisering van de eigenvectoren van andere eigenwaarden dan 1:
Stel dat s(a) de som is van de elementen van a.
De stochastische matrix M heeft als eigenschap dat s(Ma)=s(a)
Voor een eigenvector geldt dus dat: s(a)=s(Ma)=s(λa)=λs(a)
Daaruit volgt λ=1 of s(a)=0
Het voorbeeld laat trouwens nog iets zien: een stochastisch proces beschreven door een stochastische matrix (heet dat niet een Markov-keten of laat mijn herinnering me in de steek?) hoeft niet perse voor iedere beginvector te convergeren.
- Berichten: 1.460
Re: stochastische matrices
Niet alles klopt van je post, Bert:
En idd niet alle beginvector zorgt voor convergentie. Nog sterker, niet elke Markov-matrix zorgt voor convergentie: het kan een immer doorgaand proces van vernadering van de matrix opleveren of zelfs een periodieke convergentie opleveren waarbij de convergentiefase bestaat uit bijv. 3 stappen die zich elke keer opvolgen.
Bert, je kwam met een vooorbeeldje: de matrix M
Vergelijk het eens met de matrix P
en tevens met beginvector [1/3 1/3 1/3]T
Deze zal een convergentiefase ingaan op den duur, probeer zelf maar!
Dit hoeft helemaal niet zo te zijn!want alle eigenvectoren met alleen maar positieve elementen zijn stabiele eindtoestanden.
Klopt, zoiets noemt men een markov-keten en vandaar is de som der elementen in een kolom steeds 1.Het voorbeeld laat trouwens nog iets zien: een stochastisch proces beschreven door een stochastische matrix (heet dat niet een Markov-keten of laat mijn herinnering me in de steek?) hoeft niet perse voor iedere beginvector te convergeren.
En idd niet alle beginvector zorgt voor convergentie. Nog sterker, niet elke Markov-matrix zorgt voor convergentie: het kan een immer doorgaand proces van vernadering van de matrix opleveren of zelfs een periodieke convergentie opleveren waarbij de convergentiefase bestaat uit bijv. 3 stappen die zich elke keer opvolgen.
Bert, je kwam met een vooorbeeldje: de matrix M
Code: Selecteer alles
0 1
1 0
Code: Selecteer alles
0 1 0
1 0 0
0 0 1
Deze zal een convergentiefase ingaan op den duur, probeer zelf maar!
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>
- Berichten: 1.460
Re: stochastische matrices
Na nog een keer je post te hebben bestudeerd, kom ik tot een fout in je beredenering (of berekening?). De eigenwaarden zijn idd bij die matrix: +1 en -1, maar de bijbehorende eigenvectoren zijn [1,1]T en [-1,1]T. Je hebt het nergens over een beginvector, dus ik neem aan dat er ergens iets fout zit...Bert schreef:Na wat verder denkwerk kom ik tot de conclusie dat de uitspraak dat de absolute waarden van de overige eigenwaarden kleiner zijn dan 1 niet correct is.
Neem als eenvoudig voorbeeld de matrix:
De eigenwaarden van deze matrix zijn +1 en -1 en de bijbehorende eigenvectoren zijn (0,5 0,5)T en (-0,5 0,5)TCode: Selecteer alles
0 1 1 0
controleer zelf nog maar eens: de karakteristieke vergelijking is tenslotte - 1
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>
- Berichten: 1.460
Re: stochastische matrices
Ander (gemakkelijk, want 2x2 matrix!) voorbeeld:
Matrix =
karakteristieke vgl = 2 -3 - 4
eigenwaarden: 4 en -1
eigenvectoren: bij 4 hoort [1,3/2]T en bij -1 hoort [-1,1]T
Dit is dus de algemene rekenwijze. Je hebt de matrix gedefinieerd en kunt dus bij een (nog niet gedefinieerde beginvector of beginverdeling) elke gewenste toestandsvector uitrekenen.
Stel nu dat je bij bovenstaande matrix de beginvector [1/4 3/4]T definieerd. Dat betekent dan dat de volgende stap (d.w.z. ná vermenigvuldiging van matrix met vector) de verdeling als volgt zou zijn: [7/4 , 9/4]T Het valt op dat de verdeling is gegroeid! Je begon met een totaal van 1 en nu heb je een totaal van 4.
Als je goed keek ben ik ook niet begonnen met een Markov-matrix en deze zal dus nooit een convergentie tonen. dat zie je dus aan én de waarden van de eigenwaarden én aan de toestandsvectoren.
Deze matrix vertoont andere situaties:
karakteristieke vgl = 4 -19/10 2 +26/25 -7/50
eigenwaarden: 1, 1/5 en 7/10
bijbehorende eigenvectoren: bij 1 hoort [2,5,5]T, bij 1/5 hoort [2,-3,1]T en bij 7/10 hoort [1,1,-2]T
Hier valt dus op dat de eigenwaarden wél absoluut gezien kleiner of gelijk aan 1 zijn. Convergentie is dus niet uitgesloten.
Na vermenigvuldiging van de matrix met de nu gedefinieerde beginvector [1/3 1/3 1/3]T volgt: [7/30 , 13/30 , 1/3]T, dus idd nog steeds een totaal van 1 waar ik ook mee begon.
De totale convergentievector bij de gegeven beginvector is dan nu: [1/6 , 5/12 , 5/12]T
Matrix =
Code: Selecteer alles
1 2
3 2
eigenwaarden: 4 en -1
eigenvectoren: bij 4 hoort [1,3/2]T en bij -1 hoort [-1,1]T
Dit is dus de algemene rekenwijze. Je hebt de matrix gedefinieerd en kunt dus bij een (nog niet gedefinieerde beginvector of beginverdeling) elke gewenste toestandsvector uitrekenen.
Stel nu dat je bij bovenstaande matrix de beginvector [1/4 3/4]T definieerd. Dat betekent dan dat de volgende stap (d.w.z. ná vermenigvuldiging van matrix met vector) de verdeling als volgt zou zijn: [7/4 , 9/4]T Het valt op dat de verdeling is gegroeid! Je begon met een totaal van 1 en nu heb je een totaal van 4.
Als je goed keek ben ik ook niet begonnen met een Markov-matrix en deze zal dus nooit een convergentie tonen. dat zie je dus aan én de waarden van de eigenwaarden én aan de toestandsvectoren.
Deze matrix vertoont andere situaties:
Code: Selecteer alles
1/2 1/5 0
1/2 3/5 1/5
0 1/5 4/5
eigenwaarden: 1, 1/5 en 7/10
bijbehorende eigenvectoren: bij 1 hoort [2,5,5]T, bij 1/5 hoort [2,-3,1]T en bij 7/10 hoort [1,1,-2]T
Hier valt dus op dat de eigenwaarden wél absoluut gezien kleiner of gelijk aan 1 zijn. Convergentie is dus niet uitgesloten.
Na vermenigvuldiging van de matrix met de nu gedefinieerde beginvector [1/3 1/3 1/3]T volgt: [7/30 , 13/30 , 1/3]T, dus idd nog steeds een totaal van 1 waar ik ook mee begon.
De totale convergentievector bij de gegeven beginvector is dan nu: [1/6 , 5/12 , 5/12]T
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>
-
- Berichten: 718
Re: stochastische matrices
Maar math, als (1 1)T een eigenvector is dan is (0,5 0,5)T dat natuurlijk ook (en ieder veelvoud van (1 1)T trouwens ook). Ik heb echter (0,5 0,5)T genomen omdat deze vector daadwerkelijk een kansverdeling geeft. Bij de andere eigenvector heeft dat niet zo'n betekenis maar ook daar mag je de eigenvector net zo normeren als je zelf wilt.Math schreef:Na nog een keer je post te hebben bestudeerd, kom ik tot een fout in je beredenering (of berekening?). De eigenwaarden zijn idd bij die matrix: +1 en -1, maar de bijbehorende eigenvectoren zijn [1,1]T en [-1,1]T. Je hebt het nergens over een beginvector, dus ik neem aan dat er ergens iets fout zit...Bert schreef:Na wat verder denkwerk kom ik tot de conclusie dat de uitspraak dat de absolute waarden van de overige eigenwaarden kleiner zijn dan 1 niet correct is.
Neem als eenvoudig voorbeeld de matrix:
De eigenwaarden van deze matrix zijn +1 en -1 en de bijbehorende eigenvectoren zijn (0,5 0,5)T en (-0,5 0,5)TCode: Selecteer alles
0 1 1 0
controleer zelf nog maar eens: de karakteristieke vergelijking is tenslotte - 1
- Berichten: 1.460
Re: stochastische matrices
Ik weet niet wat ik moet zeggen... Hoe ondoordacht kun je zijn. Je hebt uiteraard gelijk...
Kun je mijn voorbeelden trouwens volgen?
Kun je mijn voorbeelden trouwens volgen?
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>
-
- Berichten: 718
Re: stochastische matrices
Het is me niet helemaal duidelijk wat je hier precies bedoelt maar ik stel het volgende vast:Math schreef:Niet alles klopt van je post, Bert:
Dit hoeft helemaal niet zo te zijn!want alle eigenvectoren met alleen maar positieve elementen zijn stabiele eindtoestanden.
Als een eigenvector a van een stochastische matrix M alleen maar positieve elementen bevat dan moet het een eigenvector zijn van de eigenwaarde λ=1 en er geldt dus Ma=a. Met deze begin vector is de Markovketen dus stabiel (zij het op triviale wijze omdat het voor kan komen dat er geen enkele andere begin verdeling is die deze eindtoestand oplevert). Maar misschien interpreteer ik het woord stabiele eindtoestand in het kader van Markov ketens verkeerd (het is voor mij te lang geleden om me alles nog in detail te herinneren en het is voor mij geen dagelijkse kost meer) en in dat geval hoor ik graag van je.
- Berichten: 1.460
Re: stochastische matrices
Dit klopt en bedoel ik ook, maar ik geloof niet dat het zo is dat een louter uit postief bestaande eigenvector automatisch een "stabiele" eindtoestand levert of zelfs is...en er geldt dus Ma=a. Met deze begin vector is de Markovketen dus stabiel (zij het op triviale wijze omdat het voor kan komen dat er geen enkele andere begin verdeling is die deze eindtoestand oplevert).
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>
-
- Berichten: 718
Re: stochastische matrices
Bij nader inzien denk ik dat je een dergelijke eigenvector niet altijd een stabiele eindtoestand kan noemen omdat, zoals in mijn eigen voorbeeld:Dit klopt en bedoel ik ook, maar ik geloof niet dat het zo is dat een louter uit postief bestaande eigenvector automatisch een "stabiele" eindtoestand levert of zelfs is...Bert schreef:en er geldt dus Ma=a. Met deze begin vector is de Markovketen dus stabiel (zij het op triviale wijze omdat het voor kan komen dat er geen enkele andere begin verdeling is die deze eindtoestand oplevert).
Code: Selecteer alles
0 1
1 0
Een louter uit positieve elementen bestaande eigenvector heeft als eigenwaarde λ=1 immers:
Een eigenvector a met louter positieve elementen voldoet dus altijd aan Ma=a.Stel dat s(a) de som is van de elementen van a.
De stochastische matrix M heeft als eigenschap dat s(Ma)=s(a)
Voor een eigenvector geldt dus dat: s(a)=s(Ma)=s(λa)=λs(a)
Daaruit volgt λ=1 of s(a)=0
-
- Berichten: 718
Re: stochastische matrices
Voor de overige reële eigenwaarden kun je het volgende afleiden:
Definieer |a| als de som van de absolute waarden van elementen van a.
Nu kun je iedere vector a opsplitsen als volgt: a=b-c waarin b de positieve elementen van a bevat en c de absolute waarde van de negatieve elementen. Voor deze vector geldt ook nog dat |b-c|=|b|+|c| (maar dat geldt alleen maar omdat voor elke i: bi=0 of ci=0, anders zou er een ≤-teken moeten staan).
Stel nu dat |a| een eigenvector is bij de eigenwaarde λ dan geldt:
|λa|=|Ma|=|M(b-c)|= |Mb-Mc|≤|Mb|+|Mc|=|b|+|c|=|b-c|=|a|
en hieruit volgt dat |λ|≤1
Voor complexe eigenwaarden weet ik het nog niet.
Definieer |a| als de som van de absolute waarden van elementen van a.
Nu kun je iedere vector a opsplitsen als volgt: a=b-c waarin b de positieve elementen van a bevat en c de absolute waarde van de negatieve elementen. Voor deze vector geldt ook nog dat |b-c|=|b|+|c| (maar dat geldt alleen maar omdat voor elke i: bi=0 of ci=0, anders zou er een ≤-teken moeten staan).
Stel nu dat |a| een eigenvector is bij de eigenwaarde λ dan geldt:
|λa|=|Ma|=|M(b-c)|= |Mb-Mc|≤|Mb|+|Mc|=|b|+|c|=|b-c|=|a|
en hieruit volgt dat |λ|≤1
Voor complexe eigenwaarden weet ik het nog niet.
Re: stochastische matrices
waarschijnlijk een domme vraag maar:
hoe kom je aan |Mb| = |b| en |Mc|=|c|
hoe kom je aan |Mb| = |b| en |Mc|=|c|
-
- Berichten: 718
Re: stochastische matrices
Dat geldt omdat b en c alleen maar positieve elementen bevat. Daardoor staan |b| en |c| voor de som van de elementen van respectievelijk b en c. Ook Mb en Mc bevatten alleen maar positeve elementen (want alle elementen van M zijn positief). Het is een karakterisende eigenschap van stochastische matrices dat ze de som van de elementen van een vector invariant laten (alternatief: de som van de elementen in een kolom van de stochastische matrix is 1 voor iedere kolom).Anonymous schreef:waarschijnlijk een domme vraag maar:
hoe kom je aan |Mb| = |b| en |Mc|=|c|