En Markov-kæde er inden for matematikken en tidsdiskret , der beskriver en talfølge af mulige begivenheder, hvor sandsynligheden af hver begivenhed udelukkende afhænger af det, som bliver opnået ved den foregående begivenhed.Definition at Brilliant.org "Brilliant Math and Science Wiki". Retrieved on 12 May 2019 Processen har således , hvilket vil sige, at processens forløb kan bestemmes ud fra dens nuværende tilstand uden kendskab til tidligere tilstande.
En Markov-kæde som er tidskontinuerlig kaldes en Markovprocess.
Anvendelse
Markov-kædeanalysen, hvor spillet gentages flere gange, og sandsynligheden for næste valg afhænger af forrige spiltilstand, benyttes ofte i spilteori. Alle mulige kombinationer af handlinger definerer tilstande i kæden, og overgangssandsynlighederne opstilles i en overgangsmatrix. Analysen af denne matrix fører til beregning af den stationære fordeling, som giver mulighed for at beregne den gennemsnitlige payoff for hver spiller over tid.
Teorien bag overgangsligninger og ligevægtsligninger er centrale begreber i anvendelsen af Markovkæder i spilteorien. Overgangsligninger beskriver udviklingen af sandsynligheder fra runde til runde, mens ligevægtsligninger beskriver den stationære fordeling, hvor sandsynlighederne ikke længere ændrer sig.
Overgangsligning: πt+1 = π Ligevægtsligning: π = π · P Betingelse: ∑i πi = 1 Forventet payoff: E(U) = ∑i πi · ui Ligevægtsligningerne bruges til at finde den stationære fordeling og dermed de gennemsnitlige payoffs (Mulige gevinster).
Kildehenvisninger
Kategori:Grafteori Kategori:Kunstig intelligens Kategori:Spilteori