1 svar
96 visningar
Zeshen 479
Postad: 22 okt 2021 15:34 Redigerad: 22 okt 2021 15:35

Konvergens hastighet & markovkedjor

Hej,

 

Låt A vara en sannolikhetsmatris och α den minsta elementet i A. Vi försöker hitta x så att Ax = x. (jämnviktsläget)

Skulle någon förklara varför den andra största egenvärdet av en sannolikhetsmatris är 1-mα och därmed konvergenshastigheten av x lika med 1-mαn?

 

Här är lite bakgrund och exempel:

_JN_ 7
Postad: 26 okt 2021 21:44

Detta är min tolkning av resonemanget: Eftersom A är en sannolikhetsmatris summerar alla kolonner till 1. För att skapa matrisen A-αB har vi dragit bort α från varje element, och således har totalt mα dragits från varje kolonn (eftersom Am×m). Kolonnerna i A-αB summerar nu till 1-mα.

Vi kan tänka oss att vi tar en annan lämplig sannolikhetsmatris C, och multiplicerar med denna faktor så att kolonnerna summerar till 1-mα. Då kan vi skriva (1-mα)C=A-αB. C:s egenvärden är inte större än 1 (eftersom det är en sannolikhetsmatris), och egenvärdena till A-αB är därför inte större än 1-mα. Därför är vi garanterade konvergens som långsammast (1-mα)n.

Svara
Close