Springen naar inhoud

stochastische matrices


  • Log in om te kunnen reageren

#1


  • Gast

Geplaatst op 25 februari 2005 - 19:27

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Math

    Math


  • >1k berichten
  • 1460 berichten
  • VIP

Geplaatst op 25 februari 2005 - 23:37

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.
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>

#3

Bert

    Bert


  • >250 berichten
  • 718 berichten
  • Ervaren gebruiker

Geplaatst op 26 februari 2005 - 09:02

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

#4

Bert

    Bert


  • >250 berichten
  • 718 berichten
  • Ervaren gebruiker

Geplaatst op 26 februari 2005 - 10:53

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:

0   1
1   0

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.

#5

Math

    Math


  • >1k berichten
  • 1460 berichten
  • VIP

Geplaatst op 26 februari 2005 - 12:22

Niet alles klopt van je post, Bert:

want alle eigenvectoren met alleen maar positieve elementen zijn stabiele eindtoestanden.

Dit hoeft helemaal niet zo te zijn!

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.

Klopt, zoiets noemt men een markov-keten en vandaar is de som der elementen in een kolom steeds 1.
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
0 1
1 0
Vergelijk het eens met de matrix P
0 1 0
1 0 0
0 0 1
en tevens met beginvector [1/3 1/3 1/3]T
Deze zal een convergentiefase ingaan op den duur, probeer zelf maar!
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>

#6

Math

    Math


  • >1k berichten
  • 1460 berichten
  • VIP

Geplaatst op 26 februari 2005 - 13:19

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:

0   1
1   0

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

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...
controleer zelf nog maar eens: de karakteristieke vergelijking is tenslotte :shock: - 1
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>

#7

Math

    Math


  • >1k berichten
  • 1460 berichten
  • VIP

Geplaatst op 26 februari 2005 - 13:28

Ander (gemakkelijk, want 2x2 matrix!) voorbeeld:

Matrix =
1 2
3 2
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:
1/2 1/5 0
1/2 3/5 1/5
0   1/5 4/5
karakteristieke vgl = :?: 4 -19/10 :shock: 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 wl 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>

#8

Bert

    Bert


  • >250 berichten
  • 718 berichten
  • Ervaren gebruiker

Geplaatst op 26 februari 2005 - 14:16

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:

0   1
1   0
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

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...
controleer zelf nog maar eens: de karakteristieke vergelijking is tenslotte :shock: - 1

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.

#9

Math

    Math


  • >1k berichten
  • 1460 berichten
  • VIP

Geplaatst op 26 februari 2005 - 14:22

:shock: Ik weet niet wat ik moet zeggen... Hoe ondoordacht kun je zijn. Je hebt uiteraard gelijk...

Kun je mijn voorbeelden trouwens volgen?
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>

#10

Bert

    Bert


  • >250 berichten
  • 718 berichten
  • Ervaren gebruiker

Geplaatst op 26 februari 2005 - 14:28

Niet alles klopt van je post, Bert:

want alle eigenvectoren met alleen maar positieve elementen zijn stabiele eindtoestanden.

Dit hoeft helemaal niet zo te zijn!

Het is me niet helemaal duidelijk wat je hier precies bedoelt maar ik stel het volgende vast:
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.

#11

Math

    Math


  • >1k berichten
  • 1460 berichten
  • VIP

Geplaatst op 26 februari 2005 - 14:42

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

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...
<i>Iets heel precies uitleggen roept meestal extra vragen op</i>

#12

Bert

    Bert


  • >250 berichten
  • 718 berichten
  • Ervaren gebruiker

Geplaatst op 26 februari 2005 - 14:57

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

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

Bij nader inzien denk ik dat je een dergelijke eigenvector niet altijd een stabiele eindtoestand kan noemen omdat, zoals in mijn eigen voorbeeld:
0  1
1  0
zelfs de kleinste afwijking van de eigenvector er al voor zorgt dat er geen convergentie naar (0,5 0,5)T optreedt.

Een louter uit positieve elementen bestaande eigenvector heeft als eigenwaarde λ=1 immers:

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

Een eigenvector a met louter positieve elementen voldoet dus altijd aan Ma=a.

#13

Bert

    Bert


  • >250 berichten
  • 718 berichten
  • Ervaren gebruiker

Geplaatst op 27 februari 2005 - 00:59

Voor de overige rele 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.

#14


  • Gast

Geplaatst op 27 februari 2005 - 19:42

waarschijnlijk een domme vraag maar:


hoe kom je aan |Mb| = |b| en |Mc|=|c|

#15

Bert

    Bert


  • >250 berichten
  • 718 berichten
  • Ervaren gebruiker

Geplaatst op 27 februari 2005 - 21:59

waarschijnlijk een domme vraag maar:
hoe kom je aan |Mb| = |b|   en |Mc|=|c|

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





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures