xcjajx/Rachunek_prawdopodobienstwa
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects 1 Releases Wiki Activity
main
Rachunek_prawdopodobienstwa/Przewodnik_studenta_lab/05LRAP_przewodnik.ipynb

927 lines
187 KiB
Plaintext
Raw Permalink Normal View History

Upload files to "Przewodnik_studenta_lab"
2024-12-05 12:07:19 +01:00
{
"cells": [
{
"cell_type": "markdown",
"id": "577706",
"metadata": {
"collapsed": false
},
"source": [
"# Łańcuchy Markowa"
]
},
{
"cell_type": "markdown",
"id": "e1f50d",
"metadata": {
"collapsed": false
},
"source": [
"Łańcuchy Markowa stanowią przykład procesu stochastycznego, w którym rozważamy ciąg zmiennych losowych $X_0, X_1, X_2, \\ldots$ przyjmujących wartości w określonym zbiorze stanów $S$, przy czym to w jakim stanie znajdzie się zmienna losowa $X_{i+1}$ zależy tylko i wyłącznie od tego, w jakim stanie znalazła się zmienna losowa $X_i$. Formalna definicja łańcucha Markowa brzmi następująco.\n",
"\n",
"**Definicja (Łańcuch Markowa)**\n",
"\n",
"**Łańcuchem Markowa** nazywamy ciąg zmiennych losowych $X_0, X_1, X_2,\\dots$ taki, że dla dowolnych wartości $i_0,i_1,\\dots, i_t$ zachodzi\n",
"$$\\mathbb{P}(X_t=i_t|X_{t-1}=i_{t-1}, X_{t-2}=i_{t-2},\\dots, X_0=i_0)=\\mathbb{P}(X_t=i_t|X_{t-1}=i_{t-1}).$$\n",
"\n",
"Na tym kursie interesować nas będą tylko i wyłącznie **jednorodne** łańcuchy Markowa, tzn. takie, w których zbiorem wartości każdej zmiennej losowej jest zbiór stanów $S=\\{1,2,\\ldots,s\\}$ oraz dla każdego $t=1,2,\\ldots$ zachodzi\n",
"$$\\mathbb{P}(X_t=j|X_{t-1}=i)=\\mathbb{P}(X_1=j|X_{0}=i).$$\n",
"\n",
"Wówczas taki łańcuch możemy wyrazić za pomocą macierzy przechowującej powyższe wartości.\n",
"\n",
"**Definicja (macierz przejścia)**\n",
"\n",
"**Macierzą przejścia** (jednorodnego) łańcucha Markowa nazywamy macierz kwadratową $\\Pi=[p_{ij}]$, której wiersze i kolumny indeksowane są stanami łańcucha oraz taką, gdzie \n",
"$$ p_{ij}=\\mathbb{P}(X_1=j|X_{0}=i)$$\n",
"oznacza prawdopodobieństwo przejścia ze stanu $i$ do stanu $j$."
]
},
{
"cell_type": "markdown",
"id": "f7174b",
"metadata": {
"collapsed": false
},
"source": [
"**Przykład 1**\n",
"\n",
"Rozważmy łańcuch Markowa $X_0, X_1, X_2, \\ldots$ o dwóch stanach $0$ i $1$. Załóżmy, że w każdym kolejnym kroku prawdopodobieństwo przejścia do stanu przeciwnego jest dwa razy większe od prawdopodobieństwa pozostania w tym samym stanie. Zatem macierzą przejścia tego łańcucha jest macierz\n",
"$$\\Pi= \\left[\n",
" \\begin{array}{cc}\n",
" \\frac13 & \\frac23 \\\\\n",
" \\frac23 & \\frac13 \\\\\n",
" \\end{array}\n",
" \\right].$$\n",
" \n",
"Jeżeli napiszemy program, który będzie wypisywał po kolei w jakim stanie znajdzie się nasz łańcuch w kolejnych krokach, to otrzymamy losowy ciąg binarny. Przyjmijmy, że nasz łańcuch Markowa startuje od bitu $0$. "
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "a2daca",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"01000100010101101100100011010100101010011000101110100100101101010101011010010110010010101001010100010"
]
}
],
"source": [
"import random\n",
"\n",
"# definiujemy funkcję, ktora z prawdop. 1/3 zwraca ten sam bit, a z prawdop. 2/3 bit przeciwny\n",
"def random_bit(i):\n",
" if i==1:\n",
" return 0 if random.random() < (2/3) else 1\n",
" else:\n",
" return 1 if random.random() < (2/3) else 0\n",
"\n",
"bit = 0\n",
"print(bit, end=\"\")\n",
"for _ in range(100):\n",
" bit = random_bit(bit)\n",
" print(bit, end=\"\")"
]
},
{
"cell_type": "markdown",
"id": "52261f",
"metadata": {
"collapsed": false
},
"source": [
"**Definicja (rozkład początkowy)**\n",
"\n",
"Dla łańcucha Markowa $(X_i)_{i=0}^\\infty$ rozkład prawdopodobieństwa zmiennej losowej $X_0$ nazywać będziemy **rozkładem początkowym** tego łańcucha, natomiast rozkład zmiennej losowej $X_k$ nazywać będziem rozkładem po $k$ krokach. Powyższe rozkłady oznaczać będziemy odpowiednio za pomocą symboli $\\bar{\\rho}^0$ i $\\bar{\\rho}^k$.\n",
"\n",
"**Twierdzenie (rozkład po $k$ krokach)**\n",
"\n",
"Niech $(X_i)_{i=0}^\\infty$ będzie łańcuchem Markowa o macierzy przejścia $\\Pi$. Wtedy dla każdego $k, t=0,1,\\dots$, zachodzi\n",
"$$ \\bar{\\rho}^{t+1}=\\bar{\\rho}^{t}\\Pi=\\bar{\\rho}^0\\Pi^{t+1},$$\n",
"a także \n",
"$$\\bar{\\rho}^{t+k}=\\bar{\\rho}^t\\Pi^{k}.$$"
]
},
{
"cell_type": "markdown",
"id": "5b94a7",
"metadata": {
"collapsed": false
},
"source": [
"**Przykład 2 (Problem ruiny gracza)**\n",
"\n",
"Rozważmy łańcuch Markowa o macierzy przejścia\n",
"$$ \\Pi= \\left[\n",
" \\begin{array}{cccc}\n",
" 1 & 0 & 0 & 0 \\\\\n",
" p & 0 & 1-p & 0\\\\\n",
" 0 & p &0 & 1-p \\\\\n",
" 0 & 0 & 0 & 1\n",
" \\end{array}\n",
" \\right]\\,, $$\n",
"dla pewnego $p\\in(0,1)$. Załóżmy, że $p=\\frac13$ a rozkładem początkowym jest wektor $\\left(0, \\frac12, \\frac12, 0\\right)$. Zobaczmy, jak wyglądają rozkłady po $k$ krokach dla $k=1,2,\\ldots, 30$. \n"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "2710af",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Rozkład po 1 krokach: [0.16666667 0.16666667 0.33333333 0.33333333]\n",
"Rozkład po 2 krokach: [0.22222222 0.11111111 0.11111111 0.55555556]\n",
"Rozkład po 3 krokach: [0.25925926 0.03703704 0.07407407 0.62962963]\n",
"Rozkład po 4 krokach: [0.27160494 0.02469136 0.02469136 0.67901235]\n",
"Rozkład po 5 krokach: [0.27983539 0.00823045 0.01646091 0.69547325]\n",
"Rozkład po 6 krokach: [0.28257888 0.00548697 0.00548697 0.70644719]\n",
"Rozkład po 7 krokach: [0.28440786 0.00182899 0.00365798 0.71010517]\n",
"Rozkład po 8 krokach: [0.28501753 0.00121933 0.00121933 0.71254382]\n",
"Rozkład po 9 krokach: [2.85423970e-01 4.06442107e-04 8.12884215e-04 7.13356704e-01]\n",
"Rozkład po 10 krokach: [2.85559451e-01 2.70961405e-04 2.70961405e-04 7.13898627e-01]\n",
"Rozkład po 11 krokach: [2.85649771e-01 9.03204683e-05 1.80640937e-04 7.14079268e-01]\n",
"Rozkład po 12 krokach: [2.85679878e-01 6.02136455e-05 6.02136455e-05 7.14199695e-01]\n",
"Rozkład po 13 krokach: [2.85699949e-01 2.00712152e-05 4.01424304e-05 7.14239837e-01]\n",
"Rozkład po 14 krokach: [2.85706640e-01 1.33808101e-05 1.33808101e-05 7.14266599e-01]\n",
"Rozkład po 15 krokach: [2.85711100e-01 4.46027004e-06 8.92054008e-06 7.14275519e-01]\n",
"Rozkład po 16 krokach: [2.85712587e-01 2.97351336e-06 2.97351336e-06 7.14281466e-01]\n",
"Rozkład po 17 krokach: [2.85713578e-01 9.91171120e-07 1.98234224e-06 7.14283449e-01]\n",
"Rozkład po 18 krokach: [2.85713908e-01 6.60780747e-07 6.60780747e-07 7.14284770e-01]\n",
"Rozkład po 19 krokach: [2.85714128e-01 2.20260249e-07 4.40520498e-07 7.14285211e-01]\n",
"Rozkład po 20 krokach: [2.85714202e-01 1.46840166e-07 1.46840166e-07 7.14285505e-01]\n",
"Rozkład po 21 krokach: [2.85714251e-01 4.89467220e-08 9.78934440e-08 7.14285602e-01]\n",
"Rozkład po 22 krokach: [2.85714267e-01 3.26311480e-08 3.26311480e-08 7.14285668e-01]\n",
"Rozkład po 23 krokach: [2.85714278e-01 1.08770493e-08 2.17540987e-08 7.14285689e-01]\n",
"Rozkład po 24 krokach: [2.85714282e-01 7.25136622e-09 7.25136622e-09 7.14285704e-01]\n",
"Rozkład po 25 krokach: [2.85714284e-01 2.41712207e-09 4.83424415e-09 7.14285709e-01]\n",
"Rozkład po 26 krokach: [2.85714285e-01 1.61141472e-09 1.61141472e-09 7.14285712e-01]\n",
"Rozkład po 27 krokach: [2.85714285e-01 5.37138238e-10 1.07427648e-09 7.14285713e-01]\n",
"Rozkład po 28 krokach: [2.85714286e-01 3.58092159e-10 3.58092159e-10 7.14285714e-01]\n",
"Rozkład po 29 krokach: [2.85714286e-01 1.19364053e-10 2.38728106e-10 7.14285714e-01]\n",
"Rozkład po 30 krokach: [2.85714286e-01 7.95760353e-11 7.95760353e-11 7.14285714e-01]\n"
]
}
],
"source": [
"import numpy as np\n",
"\n",
"# Definiujemy macierz Pi\n",
"Pi = np.array([[1, 0, 0, 0],\n",
" [1/3, 0, 2/3, 0],\n",
" [0, 1/3, 0, 2/3],\n",
" [0, 0, 0, 1]])\n",
"\n",
"# Definiujemy rozkład początkowy\n",
"rho_0 = np.array([0, 1/2, 1/2, 0])\n",
"\n",
"rho_k = rho_0\n",
"for k in range(30):\n",
" rho_k = rho_k.dot(Pi)\n",
" print(\"Rozkład po\", k+1, \"krokach:\", rho_k)"
]
},
{
"cell_type": "markdown",
"id": "4e096b",
"metadata": {
"collapsed": false
},
"source": [
"Jak widać nasz rozkład zaczyna się stabilizować, przy czym dwie środkowe wartości zbiegają do $0$, a dwie skrajne odpowiednio do $0.285714286$ i $0.714285714$ (w przybliżeniu). "
]
},
{
"cell_type": "markdown",
"id": "998b80",
"metadata": {
"collapsed": false
},
"source": [
"**Definicja (rozkład stacjonarny)**\n",
"\n",
"Wektor $\\bar\\pi=(\\pi_1,\\dots,\\pi_s)$ nazywamy **rozkładem stacjonarnym** łańcucha Markowa o macierzy przejścia $\\Pi=[p_{ij}]$, jeśli spełnia poniższe warunki:\n",
" - $\\sum_{i}\\pi_i=1$,\n",
" - $\\pi_i\\ge 0$ dla każdego $i=1,2,\\dots,s$,\n",
" - $\\bar \\pi \\Pi=\\bar \\pi$.\n",
" \n",
"Dwa pierwsze warunki mówią nam, że wektor $\\bar\\pi$ jest rozkładem prawdopodobieństwa na stanach. Z kolei trzeci warunek mówi, że rozkład ten nie zmienia się po wykonaniu jednego kroku łańcucha Markowa (co można rozumieć jako swego rodzaju stan równowagi). \n",
"\n",
"Rozkład, który otrzymaliśmy w powyższym przykładzie jest właśnie rozkładem stacjonarnym. W ogólnym przypadku, aby wyznaczyć rozkład stacjonarny należy rozwiązać odpowiedni układ równań wynikający z pierwszego i trzeciego warunku definicji. Natomiast można też to zrobić numerycznie przeprowadzając podobną symulację jak powyżej. Jeśli nasz łańcuch ma dokładnie jeden rozkład stacjonarny, powinniśmy być w stanie wyznaczyć go startując od dowolnego rozkładu początkowego. Jeśli rozkładów stacjonarnych jest więcej, wówczas wybór rozkładu początkowego będzie miał znaczenie dla dalszej analizy."
]
},
{
"cell_type": "markdown",
"id": "b70f17",
"metadata": {
"collapsed": false
},
"source": [
"## Biblioteka PyDTMC\n",
"\n",
"Przydatną biblioteką do obsługi łańcuchów Markowa w Pythonie jest PyDTMC. Zanim ją zainstalujemy powinniśmy upewnić się, że mamy zainstalowane pakiety Matplotlib, NetworkX, NumPy i SciPy. Zainstalujmy też pakiety Graphviz i pydot potrzebne do graficznego przedstawienia łańcuchów Markowa."
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "d06eb0",
"metadata": {
"collapsed": true,
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Defaulting to user installation because normal site-packages is not writeable\r\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Requirement already satisfied: pydtmc in /home/user/.local/lib/python3.10/site-packages (8.7.0)\r\n",
"Requirement already satisfied: matplotlib<=3.7.3 in /home/user/.local/lib/python3.10/site-packages (from pydtmc) (3.7.3)\r\n",
"Requirement already satisfied: networkx in /usr/local/lib/python3.10/dist-packages (from pydtmc) (3.1)\r\n",
"Requirement already satisfied: numpy in /usr/local/lib/python3.10/dist-packages (from pydtmc) (1.23.5)\r\n",
"Requirement already satisfied: scipy in /usr/local/lib/python3.10/dist-packages (from pydtmc) (1.11.4)\r\n",
"Requirement already satisfied: contourpy>=1.0.1 in /usr/local/lib/python3.10/dist-packages (from matplotlib<=3.7.3->pydtmc) (1.2.1)\r\n",
"Requirement already satisfied: cycler>=0.10 in /usr/lib/python3/dist-packages (from matplotlib<=3.7.3->pydtmc) (0.11.0)\r\n",
"Requirement already satisfied: fonttools>=4.22.0 in /usr/lib/python3/dist-packages (from matplotlib<=3.7.3->pydtmc) (4.29.1)\r\n",
"Requirement already satisfied: kiwisolver>=1.0.1 in /usr/lib/python3/dist-packages (from matplotlib<=3.7.3->pydtmc) (1.3.2)\r\n",
"Requirement already satisfied: packaging>=20.0 in /usr/local/lib/python3.10/dist-packages (from matplotlib<=3.7.3->pydtmc) (23.2)\r\n",
"Requirement already satisfied: pillow>=6.2.0 in /usr/local/lib/python3.10/dist-packages (from matplotlib<=3.7.3->pydtmc) (10.4.0)\r\n",
"Requirement already satisfied: pyparsing>=2.3.1 in /usr/local/lib/python3.10/dist-packages (from matplotlib<=3.7.3->pydtmc) (3.0.9)\r\n",
"Requirement already satisfied: python-dateutil>=2.7 in /usr/local/lib/python3.10/dist-packages (from matplotlib<=3.7.3->pydtmc) (2.8.2)\r\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.10/dist-packages (from python-dateutil>=2.7->matplotlib<=3.7.3->pydtmc) (1.16.0)\r\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Defaulting to user installation because normal site-packages is not writeable\r\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Requirement already satisfied: graphviz in /usr/local/lib/python3.10/dist-packages (0.8.4)\r\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Defaulting to user installation because normal site-packages is not writeable\r\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Requirement already satisfied: pydot in /usr/lib/python3/dist-packages (1.4.2)\r\n"
]
}
],
"source": [
"!pip install pydtmc\n",
"!pip install graphviz\n",
"!pip install pydot"
]
},
{
"cell_type": "markdown",
"id": "29fd51",
"metadata": {
"collapsed": false
},
"source": [
"Łańcuch Markowa w PyDTMC definiujemy dzięki funkcji `MarkovChain`, która jako argumenty przyjmuje macierz przejścia oraz listę stanów.\n",
"\n",
"**Przykład 3 (Problem ruiny gracza jeszcze raz)**\n",
"\n",
"Zdefiniujmy ponownie łańcuch Markowa dla problemu ruiny gracza z parametrem $p=1/3$. Zobaczmy, jakie informacje na temat tego łańcucha jesteśmy w stanie uzyskać dzięki zastosowaniu biblioteki PyDTMC."
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "807da5",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"DISCRETE-TIME MARKOV CHAIN\n",
" SIZE: 4\n",
" RANK: 4\n",
" CLASSES: 3\n",
" > RECURRENT: 2\n",
" > TRANSIENT: 1\n",
" ERGODIC: NO\n",
" > APERIODIC: YES\n",
" > IRREDUCIBLE: NO\n",
" ABSORBING: YES\n",
" MONOTONE: YES\n",
" REGULAR: NO\n",
" REVERSIBLE: NO\n",
" SYMMETRIC: NO\n",
"\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAl0AAAJECAYAAAAsW5F4AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/OQEPoAAAACXBIWXMAAFxGAABcRgEUlENBAABDLUlEQVR4nO3deZyN9f//8eeZjTFjDINhTJbse2TfZcm+ExFKor5t31SfVEghUvlokYpsScg+lUkosmXfZV+yDDOMGYxZr98fvuaX7Oac93XOeNxvt3P7fJxznet6zaE8uq7rXJfDsiwBAADAtbzsHgAAAOB+QHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAYQHQBAAAY4JOB91pOmwIAbs9h9wAAkBHs6QIAADCA6AIAADCA6AIAADAgI+d0wQazZs2yewS3V6tWLYWHh9s9BgAA13BY1j2fD8+J9DZwODiX+HZmzpypLl262D0GnI8//AA8Gnu6PFDn1z5U2TqP2j2GW3qnbXm7RwAA4IY4pwsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAogsAAMAAH7sHgGcY8Vg1JV1OuOFrvn5ZlCuskB56pK2qt+4hLy9aHgCAfyO6cEfenPmnTh3ao/Evd1ap6g3V9c1PJEmJCRd16uAe/fTVCEV+M1px0VF6tM9rNk8LAID7YZcEMiSLf4AKlX1YrZ4dLEnaEDlLqakpNk8FAID7IbrgFLnDC0uSkhMvK/FivL3DAADghoguOEX034clSQE5cipbUE57hwEAwA1xThcyJOnyJZ08uEc/fTlcvlmyph9mBAAA1yK6cNf2rFuud9qWv+a53AUKq8P/vq/SNRvbNBUAAO6N6MJd++e3F9NSU3U++pS2LlugWaNeUakajdTptdHy9uaPFgAA/8Q5XcgQL29v5QwtoAbdnlP5ei20e82vWrdout1jAQDgdoguOE2hslUkSYe2rbV5EgAA3A/RBaexZEm6ctkIAABwLaILTnN050ZJUljxcjZPAgCA++FsZ2RIWmqq4mKitGXpfG1f8ZOCQvKqZtuedo8FAIDbIbpwR/55w+t/XjLC4XDIL2s25cwXrlrtn1Stdr0UkCOXnaMCAOCWiC7ckTdn/mn3CAAAeDTO6QIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6AIAADCA6IJtLCvN7hEAADDGx+4BcPeO/bXV7hGc4ujuzfLy8lZ4yQp2jwIAgMsRXR5o7cJpWqtpdo8BAADuAocXPYxlWff8WL9+vbJly6a33nrrnt6fmpoqLy8vzZo1K0NzXH2kpaUpODhYklS3bl1FRUU5Zb1dunSx9zcJAIAbILruEydPnlT79u1Vu3ZtvfPOO/e0jvPnz18TShnlcDjUoEEDORwOrV27VuXLl9fq1audsm4AANwN0XUfSEhIULt27RQYGKhZs2bJx+fejirHxsZKktOiS5Lq168vb29vJScnKyYmRnXr1tWoUaOctn4AANwF0ZXJWZalp556Svv379fChQszFEznz5+XJOXIkcNJ00n16tVTSkqKJCk1NVVpaWkaOHCgunbtqosXLzptOwAA2I3oyuQGDRqkOXPmaPbs2SpevHiG1nXp0iVJUkBAgDNGkyRVrFjxuvVZlqW5c+eqYsWK2rlzp9O2BQCAnYiuTGz
"text/plain": [
"<Figure size 313.5x304.7 with 1 Axes>"
]
},
"execution_count": 3,
"metadata": {
"image/png": {
"height": 290,
"width": 302
},
"needs_background": "light"
},
"output_type": "execute_result"
}
],
"source": [
"import pydtmc\n",
"p = [[1, 0, 0, 0], [1/3, 0, 2/3, 0], [0, 1/3, 0, 2/3], [0, 0, 0, 1]]\n",
"mc = pydtmc.MarkovChain(p, ['A', 'B', 'C', 'D'])\n",
"print(mc)\n",
"pydtmc.plot_graph(mc, dpi=300)"
]
},
{
"cell_type": "markdown",
"id": "64f17c",
"metadata": {
"collapsed": false
},
"source": [
"Niektóre z wyżej wymienionych parametrów/własności zostały zdefiniowane na wykładzie, pozostałe wyjaśnimy za chwilę. Zacznijmy od tego, że stany łańcucha możemy podzielić na **klasy**, które składają się ze wzajemnie **komunikujących się** stanów, czyli takich, dla których istnieje dodatnie prawdopodobieństwo przejścia z jednego w drugi i vice versa. Własność komunikowania się zadaje relację równoważności na zbiorze stanów, a powyżej wspomniane klasy są to po prostu klasy równoważności tej relacji.\n",
"\n",
"Stany możemy podzielić na dwa typy:\n",
" - **rekurencyjne** (*ang. recurrent*) czyli takie, dla których prawdopodobieństwo powrotu do tego stanu wynosi $1$, oraz\n",
" - **chwilowe** (*ang. transient*), czyli takie, dla których to prawdopodobieństwo jest mniejsze od $1$.\n",
" \n",
"Stany znajdujące się w tej samej klasie są oczywiście tego samego typu.\n",
" \n",
"Przypomnijmy, że łańcuch Markowa nazywamy **nierozkładalnym** (*ang. irreducible*), jeśli z każdego jego stanu jesteśmy w stanie z dodatnim prawdopodobieństwem przejść do każdego innego w skończonej liczbie kroków. Przez **okres** stanu $j$ rozumiemy liczbę $d(j) = NWD\\{t \\ge 1 : p^{(t)}_{jj} > 0\\}$, gdzie $p^{(t)}_{jj}$ oznacza prawdopodobieństwo przejścia ze stanu $j$ z powrotem do stanu $j$ w dokładnie $t$ krokach. Stan $j$ nazywamy **okresowym**, jeśli $d(j) > 1$, w przeciwnym wypadku mówimy, że stan $j$ jest **nieokresowy**. Łańcuch Markowa jest **nieokresowy** (*ang. aperiodic*), jeśli wszystkie jego stany są nieokresowe. Ponadto, łańcuch który jest jednocześnie nierozkładalny i nieokresowy nazywamy **ergodycznym**.\n",
"\n",
"**Ciekawostka:** Pojęcie ergodyczności jest bardzo ważne w matematyce i fizyce. Opisuje ono procesy, w których rozważamy pewną cząstkę poruszającą się w pewnym systemie. Ergodyczność takiego procesu mówi nam, że cząstka porusza się po tym systemie w sposób jednostajny i losowy. Co za tym idzie, możemy przewidywać własności takiego procesu na podstawie trajektorii (drogi) cząstki lub też na podstawie odpowiednio dużej liczby próbek losowych opisujących zachowanie tego systemu. \n",
"\n",
"Stanem **pochłaniającym** (*ang. absorbing*) nazywamy stan, z którego nie da się wyjść, innymi słowy jest to taki stan $j$, dla którego $p_{jj}=1$. Łańcuch Markowa jest **regularny** (*ang. regular*), jeśli jego macierz przejścia podniesiona do pewnej potęgi (całkowitej dodatniej) ma tylko dodatnie wyrazy. Łańcuch Markowa nazywamy **odwracalnym** (*ang. reversible*), jeśli łańcuch Markowa odpowiadający procesowi odwrotnemu do wyjściowego łańcucha jest tym samym łańcuchem. Natomiast **symetryczny** (*ang. symmetric*) łańcuch Markowa to taki, dla którego macierz przejścia jest symetryczna."
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "574726",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Stany rekurencyjne: ['A', 'D']\n",
"Stany chwilowe: ['B', 'C']\n",
"Rozkłady stacjonarne: [array([1., 0., 0., 0.]), array([0., 0., 0., 1.])]\n"
]
}
],
"source": [
"print(\"Stany rekurencyjne:\", mc.recurrent_states)\n",
"print(\"Stany chwilowe:\", mc.transient_states)\n",
"print(\"Rozkłady stacjonarne:\", mc.pi)"
]
},
{
"cell_type": "markdown",
"id": "057654",
"metadata": {
"collapsed": false
},
"source": [
"Co możemy teraz powiedzieć o łańcuchu z naszego przykładu? Jest to łańcuch, który posiada trzy klasy:\n",
" - $\\mathcal{C}_1 = \\{A\\}$, \n",
" - $\\mathcal{C}_2 = \\{B, C\\}$, \n",
" - $\\mathcal{C}_3 = \\{D\\}$.\n",
" \n",
"Klasy $\\mathcal{C}_1$ i $\\mathcal{C}_3$ zawierają stany rekurencyjne. Co więcej są to też stany pochłaniające. Klasa $\\mathcal{C}_2$ zawiera stany chwilowe. Na powyższej grafice każda klasa jest reprezentowana przez osobny kolor. Ponadto, stany rekurencyjne narysowane są w kształcie elipsy, a stany chwilowe w kształcie prostokąta.\n",
"Możemy też stwierdzić, że nasz łańcuch jest łańcuchem nieokresowym, ale nie jest nierozkładalny, a zatem nie może też być ergodyczny. \n",
"\n",
"Jak wiemy z wykładu każdy stan pochłaniający generuje nam rozkład stacjonarny, który jest równy $1$ na tym stanie i $0$ na pozostałych stanach. W przypadku rozważanego łańcucha Markowa dostajemy dzięki temu dwa rozkłady stacjonarne: $(1, 0, 0, 0)$ i $(0, 0, 0, 1)$. Wiemy ponadto, że każda kombinacja wypukła rozkładów stacjonarnych jest też rozkładem stacjonarnym, a zatem otrzymujemy tak naprawdę nieskończenie wiele takich rozkładów, każdy postaci $(p, 0, 0, 1-p)$ dla $p\\in[0,1]$.\n",
"\n",
"Biblioteka PyDTMC umożliwia nam również symulację naszego łańcucha, czyli przykładowe poruszanie się cząstki pomiędzy stanami zgodnie z rozkładem zadanym macierzą przejścia (ale w przypadku łańcuchów ze stanami pochłaniającymi taka symulacja nie zawsze jest ciekawa, bo jak tylko cząstka wpadnie do stanu pochłaniającego, nigdy go nie opuszcza)."
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "9f8db0",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['B', 'C', 'B', 'C', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D']\n"
]
}
],
"source": [
"print(mc.simulate(20, seed=30))"
]
},
{
"cell_type": "markdown",
"id": "063eee",
"metadata": {
"collapsed": false
},
"source": [
"Możemy też przedstawić taką symulację graficznie."
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "e8888f",
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAABvkAAAQMCAYAAAC86vVqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/OQEPoAAAACXBIWXMAABcSAAAXEgFnn9JSAABYKElEQVR4nOzdebhkV13v4e8vaZIwJgTCTBiaAEkzBRlkEBFlkuEiyjxFREFBZdALzxUZVPSiTBcnFJCgoIKoKDIYZhCQeWwGoZnCEAiEBAjQGXrdP2o3nFRXnT7nVFVXVvX7Pk89dWrvXbvWWX26n6Q/vfau1loAAAAAAACAfhyy7AEAAAAAAAAAmyPyAQAAAAAAQGdEPgAAAAAAAOiMyAcAAAAAAACdEfkAAAAAAACgMyIfAAAAAAAAdEbkAwAAAAAAgM6IfAAAAAAAANAZkQ8AAAAAAAA6I/IBAAAAAABAZ0Q+AAAAAAAA6IzIBwAAAAAAAJ0R+QAAAAAAAKAzIh8AAAAAAAB0RuQDAAA4yFTV56uqjT1OXva4Fq2qnj32PX+3qi677HGtqqq6+oSfs1ZVJx2Az95RVXvGPvcxi/5cAAA4kLYtewAAADAvVXV4krsnuVuSE5NcKcmlkuxJ8v0kpyf5apJPJ/lkkvcneX9r7aylDBjWUVVPSfLkDRx6XpLvJPlakg8neWOSl1+Yf66r6qgkj56w65WttQ8t6DNvmOTXxzb/RWvtGxOOPSnJi9Y53S+21k7ewGe+OMmDp+1vrdX+zjEvVfXoJEeNbf5Qa+2VB2oMB1JrbWdV/UuSn1+z+alV9bLW2leWNS4AAJgnkQ8AgJVQVXdO8rwkx0455LAkRya5VpKfWLP9rUluu9DBwWJtS3Lp4XHdJPdJ8qyqelKS57TW2jIHN8VRmRwwP5/kQwv6zGcmOXTN6+8lecYWz/XoJCevd0BVXTHJfbd4/kV4dJKrjW17cZJXHvCRHDi/n+SeSfbG1EsO235paSMCAIA5crlOAAC6V1W/kORVmR744GBziSTPSvLXyx7IhUFV3T7JT49t/pvW2te3eMobVtXt9nPMozL6xwUHs90ZVkyPPfZZPbkIrbUPJ3nN2OaHVNV1DsTnAwDAolnJBwBA16rqMhmFjEMn7D4/yReSfDvJxZIck9FqJ+jZ55N8c/j6kCRXyehne5KHVdWbW2t/fyAGdiH2fyZsW+9ynBvxmCRvmrSjqi6a5OEznr97rbWvJrnJkofx4iR3WfP60CS/neRhyxkOAADMj5V8AAD07r6ZHO6enOTSrbXtrbUTW2vXaa0dndF9+u6Z5K8yukcf9OaprbWbDI8bt9Yul+THMrof3ySPP4Bju9Cpqhtl30vyfry19oEZT32Xqrr2lH0PSXKZGc/PfLwqyfj9KR84/AMRAADomsgHAEDvbjlh29tba7/XWvvO+I7W2ldba//aWntEkisnedxGPqSqLl1Vv1FV/1xVu6rqzKo6p6q+VlXvqao/qaobbHTQVXVoVT20qt4wnOMHVfXF4fx3X3Ncm/B4yoTznTTl2KtP+fyTJxz7+QM1D+t9fo3cv6r+o6q+UlW7q+rrVfW6qrp3VdV+Tr/2c06sqj+qqjdX1alV9d01c/3eqnpRVT24qo46EN/3ogzB6ueTnDdh9w2q6vLz+Jyqun5V/WFVvbWqvlRV36uq71fVl6vq7VX1f9ebh6r6fFW1JJ+bcsiLtvJzuR+T7r/2khnPmYzu8/ab+2wc/Xw+essnrTq8qm5dVb9eVX9TVe+sqk8OP2vnDHN+WlX9d1U9r6ruWFWTVjJf4PdZ9r0fXzK6dOW6f25U1VMmHbP3e62qB1bVq4efh3OG/Tca9l99yvlPWnP+I6rqwxOO+UxVXXzC93TI8Pt5/PjTquoK48e31n6Q5J/HNh+e5IH7+7UAAIALO5frBACgd5MuU3juRt7YWjs3o/tDTTX85fnvZnR5t4tNOORyw+OmSR5XVS9P8vDW2vjKkbXnvEKS/8ho9dVaVx0e96yq/0hyv418HwfCIuZhyudcNckrktxsbNcxSe44PH6uqh7YWjt/nfNcJ6PLuN5myiF75/omSU7K6NKLz5lwngPyfc9Da21XVX06yfETdl81yde2eu6qumJG83nXKYdcaXjcOsnjq+rVSX55uFzj0gzB7V4Tdr1+i6d8U5K19+J7SFU9sbX2rTXb7pJk/J5vb8y+9wSc5hZJ3rzO/oskuWiSyye5eUaXBf1oVT1ouAfdAVGjlXCvzOjXfMtaaz+oqntn9Gfx2qi3Pcmzk/zK2Fsel31XZu5J8oDW2mlTPub1SR46tu3eSf7fVsYMAAAXFlbyAQDQu31W6yW53bCyatLKlQ2rqiOSnJLRpT8nBZ593pLkPkneN23lVFVdKslbs2/gG3fXJK/Z+GgXZxHzMMWRSd6ZfQPfuPsmeezUD6+6U5IPZnrg25AD+H1fqFXVCRldCnRa4JvkLkk+XFWTguOB9GMZxbC1vp/plzbdn79M8oM1ry+efSPUY8ZevzfJf23x8zbq+kneVFXHLfhz1nptZgx8e7XWPpXk1ybs+uWq+uH99IZVon8w4bintdbeuM5HvGvCth8vl+wEAKBzIh8AAL1775Ttv5Xk81X12ap6RVU9saruXFVHbuLcL8wFV+3stSfJqUk+nuTsCfuvleSVVTXpv7efk2TafbxOT/LRJN8eXv/EJsa6SIuYh0mOSnKV4eszk3wsoyAzyW9X1WHjG6vq+hldmu+iU9737eG8n1rn3HsdqO97Lqpqe5JpkefULZ7zUhnFnEkrZvck+Z+M5nLPhP3HJHntcI69PpLRiq2PTvnIzw/71z4+spWxD241YdsHhlW8W/GNJH83tu1RVbUtSarqhtn3Z+bZW/ysvc7KaJ4/lNG8TVsdeXSSPxnb9rn8aB7PmfCeb2bf+X5/kt0bGNdN13x9aka/r87YwPsmaq39bZIXT9j1wqq6bFUdnuSlScZ/378tyVP3c+4vZN95OySTL/cMAADdEPkAAOjdyUm+t87+a2R0r7Lfz2hl3BlV9V9V9YhhpdZEVXXrJPefsOulSa7eWju2tbYjo79Y/83sGzl+PMkDxs559SQPnnDO72e0AuzyrbUbJLlskt9Z53s6YBYxDxvwhCTHtNaun+TYJO+bcMwxuWBk2OtZmbzq7tNJ7pzk6Nba9Vtr181o5eDtMoqCbe3BS/q+t6yqTszo+5h0S4aPtNa2eqnO387o12DcWzKah+sMc3m1Ydu4q2UU3JMkrbW7t9ZukuTuE45Nkqe21m4y9ph27EbcaMK2j81wvmQU7db+vFwlP7ok6PgK0y8l+adNnv+7GV0a9e4Z/T44apjnE1trN2it7b006qQgdvequtzeF621H85nJsfB/5gw3zfZxGVW35Xk+sPvh+u31i6T0c/+lzbzDa/xyCSfGNt2+Yzm44+SXG9s3+lJ7rfepXvXmBSWT9z0CAEA4EJE5AMAoGvDPZgekg3ehy+j/wa+VUaX3ftMVU1aqZUkvzph23uSPKi19sNVUa21c1prz83kv3B/xNjr+yQ5dMJxT2ytvby11oZzntta+8Psu2JoGRYxD+v5h9ba01tr5w3n/UZGEW2SC/yFf1VdK8nPTDjuS0lu1Vp73doYMMzzm1trv5Dkr8bec6C/7814clW9b3h8oKq+luQDSW445finb+VDhvvZPWzCrtOT3GNsHr6U5B7DvnGTznGgXHPCtm/McsLW2ieS/OfY5scM9y2879j2P937s7yJ87+vtfbw1tqrhp//Scd8NZMvb1mZvHpxEXYluX1r7QLRtLX27mnj3p/W2tkZ/Tk5vsr257LvZVBbkge31r6ywdN/c8K2a2xuhAAAcOEy6V95AgBAV1prr6iqLyd5bpKbbOKtV07ymqq6bWvtv8f23WHC8ccmee+ofezjChO23byqLtla23vfwEl/+b4nyd9MGd8Lkzxoyr4DZRHzsJ5nTdg2vrJnr6PHXt9xynF/1FqbFJ9+qLX2g7FNB/r73oyrD4+NeEFr7e+3+Dk7Mvn7+ofW2lnjG1trZ1XVPyb59bFdV6yqHa2
"text/plain": [
"<Figure size 900x525 with 1 Axes>"
]
},
"execution_count": 12,
"metadata": {
"image/png": {
"height": 518,
"width": 892
},
"needs_background": "light"
},
"output_type": "execute_result"
}
],
"source": [
Update Przewodnik_studenta_lab/05LRAP_przewodnik.ipynb
2024-12-05 12:14:56 +01:00
"pydtmc.plot_sequence(mc, 20, seed=30, plot_type='matrix', dpi=75)"
Upload files to "Przewodnik_studenta_lab"
2024-12-05 12:07:19 +01:00
]
},
{
"cell_type": "markdown",
"id": "0bf3e8",
"metadata": {
"collapsed": false
},
"source": [
"**Przykład 4**\n",
"\n",
"Rozważmy teraz łańcuch zadany macierzą przejścia\n",
"$$ \\Pi= \\left[\n",
" \\begin{array}{cccc}\n",
" 1/3 & 1/3 & 1/3 & 0 \\\\\n",
" 1/3 & 0 & 1/3 & 1/3\\\\\n",
" 0 & 1/2 &0 & 1/2 \\\\\n",
" 1/2 & 0 & 0 & 1/2\n",
" \\end{array}\n",
" \\right]\\,, $$"
]
},
{
"cell_type": "code",
"execution_count": 43,
"id": "be28b8",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"DISCRETE-TIME MARKOV CHAIN\n",
" SIZE: 4\n",
" RANK: 4\n",
" CLASSES: 1\n",
" > RECURRENT: 1\n",
" > TRANSIENT: 0\n",
" ERGODIC: YES\n",
" > APERIODIC: YES\n",
" > IRREDUCIBLE: YES\n",
" ABSORBING: NO\n",
" MONOTONE: NO\n",
" REGULAR: YES\n",
" REVERSIBLE: NO\n",
" SYMMETRIC: NO\n",
"\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAe8AAAL6CAYAAAAfet54AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/OQEPoAAAACXBIWXMAAFxGAABcRgEUlENBAAB9a0lEQVR4nO3dd1hU17oG8HeGXgSUJogKiooo9h57JUZFiWLsMbEmMZocNbFFSSwxlpgYjb3FXoOFaCyIFYkFAVER7NJR+gADM/cPjtxwRGkzs2cz7+95eO51Zs9aH8Tjy1p77bUkSqUSREREJB5SoQsgIiKismF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGQY3kRERCLD8CYiIhIZhjcREZHIMLyJiIhEhuFNREQkMgxvIiIikWF4ExERiQzDm4iISGT0VdyeUsXtEdHbSYQugIiEwZE3ERGRyDC8iYiIRIbhTUREJDKqvudNlVR+fj7i4+MRHx+PlJQU5OfnIz09HXl5eTA1NYWRkRFMTExgZWUFBwcHVKtWTeiSiYgqLYY3FSGTyfDPP/8gNDQU4eHhCA0LR3R0NJKTEpGfn1/qdoyMjOFYowYaujWAh4cHGjVqhBYtWsDd3R0SCddZERFVhESpVOkCca42FxmFQoFr167B398f5wICcP2f68jNzYGZhRXsa7nCumZdWNdwRpWqtqhSzRZmVtYwqWIJiUQKIxMzSPX0IM/JRp48F3nyHMjSU5H+MhEZrxKRmhSHpGfRSH7+EPFPo5Enl8PaxgadO3VG9+7dMGDAANSqVUvoH4GY8bcgIh3F8NZRly9fxq5du3D4yJ+Ij4uFrWMt1GzUCrUbtYJz41awtHVQaX+K/HzEPbqHJ3du4Mmd63h65zpkmRlo1rwFfIYMxujRo+Ho6KjSPnUAw5tIRzG8dUhGRgZ27NiBtWt/x5074XCs0wAN2vWEW7sesK9dT6O15OfJ8Sj0Gu4FncW9oLOQZaajf7/++OyzyejVq5dGaxExhjeRjmJ464CMjAxs3rwZixYvQUpKCuq37oqWfQajTtN2QpcGoCDI710LQMjpg4gKCUKjxo3x3bx5GDx4MO+
"text/plain": [
"<Figure size 242x425.7 with 1 Axes>"
]
},
"execution_count": 43,
"metadata": {
"image/png": {
"height": 381,
"width": 247
},
"needs_background": "light"
},
"output_type": "execute_result"
}
],
"source": [
"p2 = [[1/3, 1/3, 1/3, 0], [1/3, 0, 1/3, 1/3], [0, 1/2, 0, 1/2], [1/2, 0, 0, 1/2]]\n",
"mc2 = pydtmc.MarkovChain(p2, ['A', 'B', 'C', 'D'])\n",
"print(mc2)\n",
"pydtmc.plot_graph(mc2, dpi=300)"
]
},
{
"cell_type": "markdown",
"id": "408b93",
"metadata": {
"collapsed": false
},
"source": [
"Tym razem jest to łańcuch ergodyczny, a zatem nieokresowy i nierozkładalny. Wszystkie jego stany należą do jednej klasy, bo z każdego stanu jesteśmy w stanie przejść do każdego innego w skończonej liczbie kroków z dodatnim prawdopodobieństwem."
]
},
{
"cell_type": "markdown",
"id": "10850f",
"metadata": {
"collapsed": false
},
"source": [
"## Błądzenie klasyczne na grafie\n",
"\n",
"Jednym z ważniejszych przykładów łańcuchów Markowa jest **błądzenie klasyczne cząsteczki na grafie** zwane też czasem **spacerem losowym na grafie** (*ang. random walk*) . W tym eksperymencie losowym cząsteczka przemieszcza się z jednego wierzchołka grafu na drugi, za każdym razem wybierając sąsiada wierzchołka, w którym się aktualnie znajduje w sposób jednostajny, tzn. każdego z sąsiadów wybiera z równym prawdopodobieństwem. Zbiorem stanów tego łańcucha jest zbiór wierzchołków, a macierz przejścia zależna jest tylko i wyłącznie od stopni poszczególnych wierzchołków. Z wykładu wiemy, że takie własności jak nierozkładalność czy nieokresowość w przypadków błądzenia losowego na grafie zależą tylko i wyłącznie od struktury grafu, a dokładniej:\n",
" - łańcuch jest nierozkładalny, jeśli graf po którym błądzimy jest spójny,\n",
" - łańcuch jest nieokresowy, jeśli graf po którym błądzimy nie jest grafem dwudzielnym.\n",
" \n",
"Co więcej, jednym z rozkładów stacjonarnych błądzenia klasycznego na $n$-wierzchołkowym grafie $G$ jest na pewno znormalizowany wektor zadany przez ciąg stopni, czyli wektor\n",
"$$\\left(\\frac{d(v_1)}{2e(G)}, \\frac{d(v_2)}{e(G)}, \\ldots, \\frac{d(v_n)}{2e(G)} \\right),$$\n",
"gdzie $d(v)$ oznacza stopień wierzchołka $v$, a $e(G)$ to liczba krawędzi grafu $G$. W tym wypadku normalizacja polega na podzieleniu wektora ciągu stopni przez podwojoną liczbę krawędzi tak, aby suma wyrazów w wektorze była równa $1$ (bo oczywiście z kursu Matematyki dyskretnej pamiętamy, że $\\sum_{v\\in V(G)} d(v) = 2e(G)$).\n",
"\n",
"**Przykład 5 (błądzenie na cyklu $C_6$)**\n",
"\n",
"Rozważmy błądzenie losowe na cyklu na sześciu wierzchołkach. Macierz przejścia dla tego błądzenia wygląda następująco\n",
"$$ \\Pi= \\left[\n",
" \\begin{array}{cccccc}\n",
" 0 & \\frac12 & 0 & 0 & 0 & \\frac12 \\\\\n",
" \\frac12 & 0 & \\frac12 & 0 & 0 & 0 \\\\\n",
" 0 & \\frac12 & 0 & \\frac12 & 0 & 0 \\\\\n",
" 0 & 0 & \\frac12 & 0 & \\frac12 & 0 \\\\\n",
" 0 & 0 & 0 & \\frac12 & 0 & \\frac12 \\\\\n",
" \\frac12 & 0 & 0 & 0 & \\frac12 & 0\n",
" \\end{array}\n",
" \\right]\\,. $$\n",
" \n",
"Przyjmijmy, że błądzenie losowe rozpoczynamy w wierzchołku nr $1$, co możemy zasymulować przyjmując jako rozkład początkowy rozkład $\\bar{\\rho}^0 = (1, 0, 0, 0, 0, 0, 0)$.\n"
]
},
{
"cell_type": "code",
"execution_count": 27,
"id": "b217f0",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"DISCRETE-TIME MARKOV CHAIN\n",
" SIZE: 6\n",
" RANK: 6\n",
" CLASSES: 1\n",
" > RECURRENT: 1\n",
" > TRANSIENT: 0\n",
" ERGODIC: NO\n",
" > APERIODIC: NO (2)\n",
" > IRREDUCIBLE: YES\n",
" ABSORBING: NO\n",
" MONOTONE: NO\n",
" REGULAR: NO\n",
" REVERSIBLE: YES\n",
" SYMMETRIC: YES\n",
"\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAiAAAARkCAYAAABLkK9cAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/OQEPoAAAACXBIWXMAAFxGAABcRgEUlENBAACh8klEQVR4nOzdd3hU1fr28XvSQ0ICBAi9916lSK8qJTTpAoIUj+0cOYLloKBYsFcEFVCkiAUIAtJ7BwVCQkd6SSBAIKQn8/7BD14pAcSZtZOZ7+e65jqwZ1jPsxMPuVl77bVtdrtdAAAAJnlY3QAAAHA/BBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAAYRwABAADGEUAAAIBxBBAAAGAcAQQAABhHAAEAAMYRQAAAgHEEEAAAYBwBBAAAGEcAAQAAxhFAAACAcQQQAABgHAEEAAA
"text/plain": [
"<Figure size 273.9x665.5 with 1 Axes>"
]
},
"execution_count": 27,
"metadata": {
"image/png": {
"height": 562,
"width": 272
},
"needs_background": "light"
},
"output_type": "execute_result"
}
],
"source": [
"p3 = [[0, 0.5, 0, 0, 0, 0.5], [0.5, 0, 0.5, 0, 0, 0], [0, 0.5, 0, 0.5, 0, 0], [0, 0, 0.5, 0, 0.5, 0], [0, 0, 0, 0.5, 0, 0.5], [0.5, 0, 0, 0, 0.5, 0]]\n",
"c6_rw = pydtmc.MarkovChain(p3, ['v1', 'v2', 'v3', 'v4', 'v5', 'v6'])\n",
"print(c6_rw)\n",
"pydtmc.plot_graph(c6_rw, dpi=300)"
]
},
{
"cell_type": "markdown",
"id": "c841e4",
"metadata": {
"collapsed": false
},
"source": [
"Co możemy powiedzieć o tym łańcuchu Markowa? Jest on na pewno łańcuchem okresowym, a okres tego łańcucha wynosi $2$."
]
},
{
"cell_type": "code",
"execution_count": 32,
"id": "f23ef3",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Okres łańcucha: 2\n"
]
}
],
"source": [
"print(\"Okres łańcucha:\", c6_rw.period)"
]
},
{
"cell_type": "markdown",
"id": "2852ef",
"metadata": {
"collapsed": false
},
"source": [
"Spróbujemy teraz wyznaczyć jego rozkład stacjonarny poprzez wyznaczenie rozkładu po $k$ krokach startując od rozkładu początkowego $\\bar{\\rho}^0 = (1, 0, 0, 0, 0, 0, 0)$."
]
},
{
"cell_type": "code",
"execution_count": 37,
"id": "1e3268",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Rozkład po 1 krokach: [0. 0.5 0. 0. 0. 0.5]\n",
"Rozkład po 2 krokach: [0.5 0. 0.25 0. 0.25 0. ]\n",
"Rozkład po 3 krokach: [0. 0.375 0. 0.25 0. 0.375]\n",
"Rozkład po 4 krokach: [0.375 0. 0.3125 0. 0.3125 0. ]\n",
"Rozkład po 5 krokach: [0. 0.34375 0. 0.3125 0. 0.34375]\n",
"Rozkład po 6 krokach: [0.34375 0. 0.328125 0. 0.328125 0. ]\n",
"Rozkład po 7 krokach: [0. 0.3359375 0. 0.328125 0. 0.3359375]\n",
"Rozkład po 8 krokach: [0.3359375 0. 0.33203125 0. 0.33203125 0. ]\n",
"Rozkład po 9 krokach: [0. 0.33398438 0. 0.33203125 0. 0.33398438]\n",
"Rozkład po 10 krokach: [0.33398438 0. 0.33300781 0. 0.33300781 0. ]\n",
"Rozkład po 11 krokach: [0. 0.33349609 0. 0.33300781 0. 0.33349609]\n",
"Rozkład po 12 krokach: [0.33349609 0. 0.33325195 0. 0.33325195 0. ]\n",
"Rozkład po 13 krokach: [0. 0.33337402 0. 0.33325195 0. 0.33337402]\n",
"Rozkład po 14 krokach: [0.33337402 0. 0.33331299 0. 0.33331299 0. ]\n",
"Rozkład po 15 krokach: [0. 0.33334351 0. 0.33331299 0. 0.33334351]\n",
"Rozkład po 16 krokach: [0.33334351 0. 0.33332825 0. 0.33332825 0. ]\n",
"Rozkład po 17 krokach: [0. 0.33333588 0. 0.33332825 0. 0.33333588]\n",
"Rozkład po 18 krokach: [0.33333588 0. 0.33333206 0. 0.33333206 0. ]\n",
"Rozkład po 19 krokach: [0. 0.33333397 0. 0.33333206 0. 0.33333397]\n",
"Rozkład po 20 krokach: [0.33333397 0. 0.33333302 0. 0.33333302 0. ]\n",
"Rozkład po 21 krokach: [0. 0.33333349 0. 0.33333302 0. 0.33333349]\n",
"Rozkład po 22 krokach: [0.33333349 0. 0.33333325 0. 0.33333325 0. ]\n",
"Rozkład po 23 krokach: [0. 0.33333337 0. 0.33333325 0. 0.33333337]\n",
"Rozkład po 24 krokach: [0.33333337 0. 0.33333331 0. 0.33333331 0. ]\n",
"Rozkład po 25 krokach: [0. 0.33333334 0. 0.33333331 0. 0.33333334]\n",
"Rozkład po 26 krokach: [0.33333334 0. 0.33333333 0. 0.33333333 0. ]\n",
"Rozkład po 27 krokach: [0. 0.33333334 0. 0.33333333 0. 0.33333334]\n",
"Rozkład po 28 krokach: [0.33333334 0. 0.33333333 0. 0.33333333 0. ]\n",
"Rozkład po 29 krokach: [0. 0.33333333 0. 0.33333333 0. 0.33333333]\n",
"Rozkład po 30 krokach: [0.33333333 0. 0.33333333 0. 0.33333333 0. ]\n"
]
}
],
"source": [
"rho_0 = np.array([1, 0, 0, 0, 0, 0])\n",
"\n",
"rho_k = rho_0\n",
"for k in range(30):\n",
" rho_k = rho_k.dot(p3)\n",
" print(\"Rozkład po\", k+1, \"krokach:\", rho_k)"
]
},
{
"cell_type": "markdown",
"id": "f22163",
"metadata": {
"collapsed": false
},
"source": [
"Jak widać w tym przypadku rozkład po $k$ krokach nie stabilizuje się, natomiast możemy zaobserwować cykliczne zachowanie, gdzie na przemian rozkład jest skupiony na wierzchołkach $v_1, v_3, v_5$ i $v_2, v_4, v_6$. Wynika to z okresowości naszego łańcucha. Co się stanie jeśli wystartujemy z innego rozkładu stacjonarnego?"
]
},
{
"cell_type": "code",
"execution_count": 38,
"id": "5a0562",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Rozkład po 1 krokach: [0.25 0.25 0.25 0. 0. 0.25]\n",
"Rozkład po 2 krokach: [0.25 0.25 0.125 0.125 0.125 0.125]\n",
"Rozkład po 3 krokach: [0.1875 0.1875 0.1875 0.125 0.125 0.1875]\n",
"Rozkład po 4 krokach: [0.1875 0.1875 0.15625 0.15625 0.15625 0.15625]\n",
"Rozkład po 5 krokach: [0.171875 0.171875 0.171875 0.15625 0.15625 0.171875]\n",
"Rozkład po 6 krokach: [0.171875 0.171875 0.1640625 0.1640625 0.1640625 0.1640625]\n",
"Rozkład po 7 krokach: [0.16796875 0.16796875 0.16796875 0.1640625 0.1640625 0.16796875]\n",
"Rozkład po 8 krokach: [0.16796875 0.16796875 0.16601562 0.16601562 0.16601562 0.16601562]\n",
"Rozkład po 9 krokach: [0.16699219 0.16699219 0.16699219 0.16601562 0.16601562 0.16699219]\n",
"Rozkład po 10 krokach: [0.16699219 0.16699219 0.16650391 0.16650391 0.16650391 0.16650391]\n",
"Rozkład po 11 krokach: [0.16674805 0.16674805 0.16674805 0.16650391 0.16650391 0.16674805]\n",
"Rozkład po 12 krokach: [0.16674805 0.16674805 0.16662598 0.16662598 0.16662598 0.16662598]\n",
"Rozkład po 13 krokach: [0.16668701 0.16668701 0.16668701 0.16662598 0.16662598 0.16668701]\n",
"Rozkład po 14 krokach: [0.16668701 0.16668701 0.16665649 0.16665649 0.16665649 0.16665649]\n",
"Rozkład po 15 krokach: [0.16667175 0.16667175 0.16667175 0.16665649 0.16665649 0.16667175]\n",
"Rozkład po 16 krokach: [0.16667175 0.16667175 0.16666412 0.16666412 0.16666412 0.16666412]\n",
"Rozkład po 17 krokach: [0.16666794 0.16666794 0.16666794 0.16666412 0.16666412 0.16666794]\n",
"Rozkład po 18 krokach: [0.16666794 0.16666794 0.16666603 0.16666603 0.16666603 0.16666603]\n",
"Rozkład po 19 krokach: [0.16666698 0.16666698 0.16666698 0.16666603 0.16666603 0.16666698]\n",
"Rozkład po 20 krokach: [0.16666698 0.16666698 0.16666651 0.16666651 0.16666651 0.16666651]\n",
"Rozkład po 21 krokach: [0.16666675 0.16666675 0.16666675 0.16666651 0.16666651 0.16666675]\n",
"Rozkład po 22 krokach: [0.16666675 0.16666675 0.16666663 0.16666663 0.16666663 0.16666663]\n",
"Rozkład po 23 krokach: [0.16666669 0.16666669 0.16666669 0.16666663 0.16666663 0.16666669]\n",
"Rozkład po 24 krokach: [0.16666669 0.16666669 0.16666666 0.16666666 0.16666666 0.16666666]\n",
"Rozkład po 25 krokach: [0.16666667 0.16666667 0.16666667 0.16666666 0.16666666 0.16666667]\n",
"Rozkład po 26 krokach: [0.16666667 0.16666667 0.16666666 0.16666666 0.16666666 0.16666666]\n",
"Rozkład po 27 krokach: [0.16666667 0.16666667 0.16666667 0.16666666 0.16666666 0.16666667]\n",
"Rozkład po 28 krokach: [0.16666667 0.16666667 0.16666667 0.16666667 0.16666667 0.16666667]\n",
"Rozkład po 29 krokach: [0.16666667 0.16666667 0.16666667 0.16666667 0.16666667 0.16666667]\n",
"Rozkład po 30 krokach: [0.16666667 0.16666667 0.16666667 0.16666667 0.16666667 0.16666667]\n"
]
}
],
"source": [
"rho_0 = np.array([1/2, 1/2, 0, 0, 0, 0])\n",
"\n",
"rho_k = rho_0\n",
"for k in range(30):\n",
" rho_k = rho_k.dot(p3)\n",
" print(\"Rozkład po\", k+1, \"krokach:\", rho_k)"
]
},
{
"cell_type": "markdown",
"id": "820c8c",
"metadata": {
"collapsed": false
},
"source": [
"Tym razem dość szybko dochodzimy do rozkładu stacjonarnego $\\left(\\frac16, \\frac16, \\frac16, \\frac16, \\frac16, \\frac16\\right)$, który jest dokładnie rozkładem otrzymanym z ciągu stopni. Zobaczmy jeszcze jakie rozkłady stacjonarne wyznaczy nam polecenie z PyDTMC."
]
},
{
"cell_type": "code",
"execution_count": 41,
"id": "3e528d",
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Rozkłady stacjonarne dla błądzenia klasycznego na cyklu C6: [array([0.16666667, 0.16666667, 0.16666667, 0.16666667, 0.16666667,\n",
" 0.16666667])]\n"
]
}
],
"source": [
"print(\"Rozkłady stacjonarne dla błądzenia klasycznego na cyklu C6:\", c6_rw.pi)"
]
},
{
"cell_type": "markdown",
"id": "1b9ede",
"metadata": {
"collapsed": false
},
"source": [
"## Bibliografia\n",
"\n",
"Dokumentację dotyczącą omawianego pakietu można znaleźć na stronie [PyDTMC](https://pydtmc.readthedocs.io/)."
]
}
],
"metadata": {
"kernelspec": {
"argv": [
"/usr/bin/python3",
"-m",
"ipykernel",
"--HistoryManager.enabled=False",
"--matplotlib=inline",
"-c",
"%config InlineBackend.figure_formats = set(['retina'])\nimport matplotlib; matplotlib.rcParams['figure.figsize'] = (12, 7)",
"-f",
"{connection_file}"
],
"display_name": "Python 3 (system-wide)",
"env": {
},
"language": "python",
"metadata": {
"cocalc": {
"description": "Python 3 programming language",
"priority": 100,
"url": "https://www.python.org/"
}
},
"name": "python3",
"resource_dir": "/ext/jupyter/kernels/python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.12"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Reference in New Issue Copy Permalink