Diese Seite enthält Beispiele von Ketten von Markov in der Handlung.

Brettspiele haben mit Würfeln gespielt

Ein Spiel von Schlangen und Leitern oder jedes andere Spiel, dessen Bewegungen völlig durch Würfel bestimmt werden, sind eine Kette von Markov, tatsächlich, eine fesselnde Kette von Markov. Das ist im Gegensatz zu Kartenspielen wie Black Jack, wo die Karten ein 'Gedächtnis' der vorigen Bewegungen vertreten. Um den Unterschied zu sehen, denken Sie die Wahrscheinlichkeit für ein bestimmtes Ereignis im Spiel. In den obengenannten erwähnten Würfel-Spielen, das einzige Ding, dass Sachen der aktuelle Staat des Ausschusses sind. Der folgende Staat des Ausschusses hängt vom aktuellen Staat und der folgenden Rolle der Würfel ab. Es hängt nicht ab, wie Dinge zu ihrem aktuellen Staat gekommen sind. In einem Spiel wie Black Jack kann ein Spieler einen Vorteil gewinnen, indem er sich erinnert, welche Karten bereits gezeigt worden sind (und folglich welche Karten nicht mehr im Deck sind), so ist der folgende Staat (oder Hand) des Spiels von den vorigen Staaten ziemlich abhängig.

Ein Zentrum-voreingenommener zufälliger Spaziergang

Denken Sie einen zufälligen Spaziergang auf dem Zahlenstrahl, wo, an jedem Schritt, sich die Position (nennen es x), um +1 (nach rechts) oder-1 (nach links) mit Wahrscheinlichkeiten ändern kann:

(wo c eine Konstante ist, die größer ist als 0)

Zum Beispiel, wenn die Konstante, c, 1 gleich ist, wird durch die Wahrscheinlichkeiten einer Bewegung nach links an Positionen x =-2,-1,0,1,2 beziehungsweise gegeben. Der zufällige Spaziergang hat eine Zentrieren-Wirkung, die als c Zunahmen schwach wird.

Da die Wahrscheinlichkeiten nur von der aktuellen Position (Wert von x) und nicht auf irgendwelchen vorherigen Positionen abhängen, befriedigt dieser voreingenommene zufällige Spaziergang die Definition einer Kette von Markov.

Ein sehr einfaches Wettermodell

Die Wahrscheinlichkeiten von Wetterbedingungen (modelliert entweder als regnerisch oder als sonnig), in Anbetracht des Wetters am vorhergehenden Tag,

kann durch eine Übergang-Matrix vertreten werden:

:

P = \begin {bmatrix }\

0.9 & 0.1 \\

0.5 & 0.5

\end {bmatrix }\

</Mathematik>

Die Matrix P vertritt das Wettermodell, in dem ein Sonnentag 90% ist

wahrscheinlich vor einem anderen Sonnentag und einem regnerischen Tag gefolgt zu werden, ist zu um 50 % wahrscheinlich

werde vor einem anderen regnerischen Tag gefolgt. Die Säulen können "sonnig" und etikettiert werden

"regnerisch" beziehungsweise, und die Reihen kann in derselben Ordnung etikettiert werden.

(P) ist die Wahrscheinlichkeit, dass, wenn ein gegebener Tag des Typs i ist, es sein wird

gefolgt von einem Tag des Typs j.

Bemerken Sie, dass die Reihen von P zu 1 resümieren: Das ist, weil P eine stochastische Matrix ist.

Das Voraussagen des Wetters

Wie man

bekannt, ist das Wetter am Tag 0 sonnig. Das wird durch einen Vektoren vertreten, in dem der "Sonnen"-Zugang 100 % ist, und der "regnerische" Zugang 0 % ist:

:

\mathbf {x} ^ {(0)} = \begin {bmatrix }\

1 & 0

\end {bmatrix }\</Mathematik>

Das Wetter am Tag 1 kann vorausgesagt werden durch:

:

\mathbf {x} ^ {(1)} = \mathbf {x} ^ {(0)} P =

\begin {bmatrix }\

1 & 0 \end {bmatrix }\ \begin {bmatrix }\ 0.9 & 0.1 \\ 0.5 & 0.5 \end {bmatrix }\

= \begin {bmatrix }\

0.9 & 0.1

\end {bmatrix}

</Mathematik>

So gibt es eine 90-%-Chance an diesem Tag 1 wird auch sonnig sein.

Das Wetter am Tag 2 kann ebenso vorausgesagt werden:

:

\mathbf {x} ^ {(2)} = \mathbf {x} ^ {(1)} P = \mathbf {x} ^ {(0)} P^2

= \begin {bmatrix }\ 1 & 0 \end {bmatrix }\ \begin {bmatrix }\ 0.9 & 0.1 \\ 0.5 & 0.5

\end {bmatrix} ^2

= \begin {bmatrix }\

0.86 & 0.14

\end {bmatrix}</Mathematik>

oder

:

\mathbf {x} ^ {(2)} = \mathbf {x} ^ {(1)} P

= \begin {bmatrix }\ 0.9 & 0.1 \end {bmatrix }\ \begin {bmatrix }\ 0.9 & 0.1 \\ 0.5 & 0.5 \end {bmatrix }\ = \begin {bmatrix }\ 0.86 & 0.14 \end {bmatrix}</Mathematik>

Allgemeine Regeln für den Tag n sind:

:

\mathbf {x} ^ {(n)} = \mathbf {x} ^ {(n-1)} P

</Mathematik>:

\mathbf {x} ^ {(n)} = \mathbf {x} ^ {(0)} P^n

</Mathematik>

Unveränderlicher Staat des Wetters

In diesem Beispiel sind Vorhersagen für das Wetter in entfernteren Tagen zunehmend

ungenau und neigen zu einem unveränderlichen Zustandvektoren. Dieser Vektor vertritt

die Wahrscheinlichkeiten des sonnigen und regnerischen Wetters in allen Tagen, und sind unabhängiger

des anfänglichen Wetters.

Der unveränderliche Zustandvektor wird als definiert:

\mathbf {q} = \lim_ {n \to \infty} \mathbf {x} ^ {(n) }\

</Mathematik>

aber läuft nur zu einem ausschließlich positiven Vektoren zusammen, wenn P eine regelmäßige Übergang-Matrix ist (d. h. dort

ist mindestens ein P mit allen Nichtnulleinträgen).

Da der q von anfänglichen Bedingungen unabhängig ist, muss es, wenn umgestaltet, durch P unverändert sein. Das macht es einen Eigenvektoren (mit eigenvalue 1) und bedeutet, dass es aus P abgeleitet werden kann. Für das Wetterbeispiel:

\begin {Matrix-}\

P & = & \begin {bmatrix }\

0.9 & 0.1 \\

0.5 & 0.5

\end {bmatrix }\

\\

\mathbf {q} P & = & \mathbf {q }\

& \mbox {(} \mathbf {q} \mbox {ist durch} P \mbox {unverändert.) }\

\\

& = & \mathbf {q} ich

\\

\mathbf {q} (P - I) & = & \mathbf {0} \\

& = & \mathbf {q} \left (\begin {bmatrix }\

0.9 & 0.1 \\ 0.5 & 0.5 \end {bmatrix }\

-

\begin {bmatrix }\

1 & 0 \\

0 & 1

\end {bmatrix }\

\right)

\\

& = & \mathbf {q} \begin {bmatrix }\

- 0.1 & 0.1 \\

0.5 &-0.5

\end {bmatrix}

\end {Matrix-}\

</Mathematik>

\begin {bmatrix }\

q_1 & q_2

\end {bmatrix }\ \begin {bmatrix }\

- 0.1 & 0.1 \\

0.5 &-0.5

\end {bmatrix }\ = \begin {bmatrix }\

0 & 0

\end {bmatrix }\</Mathematik>

So

- 0.1 q_1 + 0.5 q_2 = 0

</Mathematik>

und da sie ein Wahrscheinlichkeitsvektor sind, wissen wir das

q_1 + q_2 = 1.

</Mathematik>

Das Lösen dieses Paares von gleichzeitigen Gleichungen gibt den unveränderlichen Zustandvertrieb:

\begin {bmatrix }\ q_1 & q_2 \end {bmatrix }\ = \begin {bmatrix }\

0.833 & 0.167

\end {bmatrix }\</Mathematik>

Schließlich auf lange Sicht sind 83 % von Tagen sonnig.

Zitat-Rangordnung

Der Seitenreihe-Algorithmus von Google ist im Wesentlichen eine Kette von Markov über den Graphen von

das Web. Mehr Information kann in "Der Zitat-Rangordnung von PageRank gefunden werden: Das Holen der Ordnung zum Web"

Larry Page, Sergey Brin, R. Motwani und T. Winograd.

Siehe auch

• V Zeichen. Shaney

Außenverbindungen

• Monopol als eine Kette von Markov