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:

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 $A \in ℝ^{m \times 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 Avbryt