{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Topic 5: Markovian (and Deterministic) Dynamic System\n", "\n", "Group Members: Xiaomeng Cai, Shibo Ma, Gaoyu Lu, Ruiling Chen, Yang Len\n", "\n", "The link of video: https://youtu.be/9WpuBwX-Q8Q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction\n", "## Definition\n", "Markov chain is the simplest Markov model. It is a time series analysis method, it predicts the state of an event and development trend by using state-transition matrices." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us take the traffic light system as an example. Considered such a traffic light in practice, there are red, green and yellow. Three different colours run in a designed subsequence, red firstly, then green and yellow lastly. Then, this sequence can be seen as a state machine, each time of a colour appearing only depends on the last colour. Described in mathematics notation, $x_{1}$ = red, $x_{2}$ = green, $x_{3}$ = yellow, $x_{4}$ = red again, the state $x_{i}$ is a deterministic pattern, with each state only determined by the last state.\n", "\n", "Thus, we can deduce a linear dynamical system that is a simple model for a sequence $x_{1}, x_{2}, \\ldots$ in which each $x_{t+1}$ is a linear function of $x_{t}$: " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$x_{t+1}=A_{t}x_{t}, \\quad t = 1, 2, \\ldots$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The $n \\times n$ matrices $A_{t}$ are called the dynamics matrices. The equation above is called the dynamics or update equation.\n", "\n", "This linear dynamical system is sometimes called a Markov model (after the mathematician Andrey Markov). Markov studied systems assumed that future states depend only on the current state, i.e. $x_{t+1}$ depends only on $x_{t}$, and not additionally on $x_{t-1}, x_{t-2}, \\ldots$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Transition matrix\n", "In the example above there are three states for the system. Define $X_{i}$ to be the probability of the system to be in state $t$ after it was in state $t-1$ ( at any observation ). The matrix $A = X$ is called the Transition matrix of the Markov Chain.\n", "\n", "Let us consider the transition matrix of traffic lights. Presume the sequence of the traffic lights starting from green, then yellow, and red. Here we can have a simple transition state table to show three different situations as below, in which each row represents the initial state of traffic lights and each column is the state after transiting." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{array}{c|lcr}\n", " & \\text{Green} & \\text{Yellow} & \\text{Red} \\\\\n", "\\hline\n", "Green & 0 & 0 & 1 \\\\\n", "Yellow & 1 & 0 & 0 \\\\\n", "Red & 0 & 1 & 0\n", "\\end{array}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It can also be shown as a $3\\times 3$ marix $p =\n", "\\big(\n", " \\begin{smallmatrix}\n", " 0 & 0 & 1 \\\\\n", " 1 & 0 & 0 \\\\\n", " 0 & 1 & 0\n", " \\end{smallmatrix}\n", " \\big).$ Take the $1$ in the first row as an example. It means the green light will be on after the red is off." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here we assume $y$ as the state of each traffic light. If the red light is on, then we have \n", "$$y_{t} = \\left [\n", "\\begin{array}{c|c}\n", "Green & 0 \\\\\n", "Yellow & 0 \\\\\n", "Red & 1\n", "\\end{array}\n", "\\right ].$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Therefore, the sequence for which light will be on can be expressed as below,\n", "$$\n", "y_{t+1} = p\\cdot y_{t} = \n", "\\left [\n", "\\begin{array}{c|c}\n", "Green & 1 \\\\\n", "Yellow & 0 \\\\\n", "Red & 0\n", "\\end{array}\n", "\\right ].\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "All the states thus can have the expression\n", "$\n", "y_{t} = p^t\\cdot y_{0} .\n", "$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Property\n", "\n", "Indenpency\n", "\n", "A state $S_{t}$ is Markov if and only if\n", "$$P[S_{t+1}|S_{t}] = P[S_{t+1}|S_{1} ,\\cdots, S_{t}],$$\n", "which means the memoryless attributes of the stochastic process. This process will own the attribute of Markov, if the conditional probability distrbution of this process's future state only depends on the current state, rather than the former sequence. Thus, these two events are independent from each other." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# State Transition Matrix\n", "\n", "For a Markov state $s$ and successor state $s'$, the state transition probability is defined by\n", "$$P_{ss'} = P[S_{t+1}=s'|S_{t}=s].$$\n", "State transition matrxi P defines transition probabilities from all states s to all successor states $s'$,\n", "$$P = \\begin{bmatrix}\n", "P_{11} & \\cdots & P_{1n} \\\\\n", "\\vdots & \\ddots & \\vdots \\\\\n", "P_{n1} & \\cdots & P_{nn}\n", "\\end{bmatrix},$$\n", "where each row of the matrix sums to 1." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Application\n", "\n", "Take the weather obeservation data of Shanghai as an example, during which the Markov model will be deployed to forecast local weather.\n", "\n", "Firstly, we will introduce the data that has been preprocessed throughout Python, in which the state 1 represents the sunny day, 2 is the cloudy day and 3 means rainy days. In the meantime, we choose the last day as the test set to verify the model. " ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " ymd weather degree Unnamed: 3 Unnamed: 4 Unnamed: 5\n", "0 2017/10/16 rain 3 NaN NaN sunny 1\n", "1 2017/10/17 cloudy 2 NaN NaN cloudy 2\n", "2 2017/10/18 cloudy 2 NaN NaN rain 3\n", "3 2017/10/19 rain 3 NaN NaN NaN\n", "4 2017/10/20 cloudy 2 NaN NaN NaN\n", "5 2017/10/21 sunny 1 NaN NaN NaN\n", "6 2017/10/22 sunny 1 NaN NaN NaN\n", "7 2017/10/23 cloudy 2 NaN NaN NaN\n", "8 2017/10/24 sunny 1 NaN NaN NaN\n", "9 2017/10/25 sunny 1 NaN NaN NaN\n", "10 2017/10/26 cloudy 2 NaN NaN NaN\n", "11 2017/10/27 sunny 1 NaN NaN NaN\n", "12 2017/10/28 cloudy 2 NaN NaN NaN\n", "13 2017/10/29 sunny 1 NaN NaN NaN\n", "14 2017/10/30 cloudy 2 NaN NaN NaN\n", "15 2017/10/31 cloudy 2 NaN NaN NaN\n", "16 2017/11/1 sunny 1 NaN NaN NaN\n", "17 2017/11/2 cloudy 2 NaN NaN NaN\n", "18 2017/11/3 cloudy 2 NaN NaN NaN\n", "19 2017/11/4 cloudy 2 NaN NaN NaN\n", "20 2017/11/5 cloudy 2 NaN NaN NaN\n", "21 2017/11/6 cloudy 2 NaN NaN NaN\n", "22 2017/11/7 cloudy 2 NaN NaN NaN\n", "23 2017/11/8 sunny 1 NaN NaN NaN\n", "24 2017/11/9 cloudy 2 NaN NaN NaN\n", "25 2017/11/10 cloudy 2 NaN NaN NaN\n", "26 2017/11/11 cloudy 2 NaN NaN NaN\n", "27 2017/11/12 cloudy 2 NaN NaN NaN\n", "28 2017/11/13 rain 3 NaN NaN NaN\n", "29 2017/11/14 rain 3 NaN NaN NaN\n", ".. ... ... ... ... ... ...\n", "47 2017/12/2 cloudy 2 NaN NaN NaN\n", "48 2017/12/3 cloudy 2 NaN NaN NaN\n", "49 2017/12/4 cloudy 2 NaN NaN NaN\n", "50 2017/12/5 sunny 1 NaN NaN NaN\n", "51 2017/12/6 sunny 1 NaN NaN NaN\n", "52 2017/12/7 cloudy 2 NaN NaN NaN\n", "53 2017/12/8 cloudy 2 NaN NaN NaN\n", "54 2017/12/9 cloudy 2 NaN NaN NaN\n", "55 2017/12/10 sunny 1 NaN NaN NaN\n", "56 2017/12/11 sunny 1 NaN NaN NaN\n", "57 2017/12/12 cloudy 2 NaN NaN NaN\n", "58 2017/12/13 cloudy 2 NaN NaN NaN\n", "59 2017/12/14 cloudy 2 NaN NaN NaN\n", "60 2017/12/15 rain 3 NaN NaN NaN\n", "61 2017/12/16 sunny 1 NaN NaN NaN\n", "62 2017/12/17 sunny 1 NaN NaN NaN\n", "63 2017/12/18 sunny 1 NaN NaN NaN\n", "64 2017/12/19 sunny 1 NaN NaN NaN\n", "65 2017/12/20 sunny 1 NaN NaN NaN\n", "66 2017/12/21 sunny 1 NaN NaN NaN\n", "67 2017/12/22 sunny 1 NaN NaN NaN\n", "68 2017/12/23 cloudy 2 NaN NaN NaN\n", "69 2017/12/24 sunny 1 NaN NaN NaN\n", "70 2017/12/25 cloudy 2 NaN NaN NaN\n", "71 2017/12/26 sunny 1 NaN NaN NaN\n", "72 2017/12/27 cloudy 2 NaN NaN NaN\n", "73 2017/12/28 rain 3 NaN NaN NaN\n", "74 2017/12/29 cloudy 2 NaN NaN NaN\n", "75 2017/12/30 cloudy 2 NaN NaN NaN\n", "76 2017/12/31 sunny 1 NaN NaN NaN\n", "\n", "[77 rows x 6 columns]\n" ] } ], "source": [ "import numpy as np\n", "import pandas as pd\n", "sh_weather = pd.read_csv(\"weather.csv\")\n", "print(sh_weather)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0 3\n", "1 2\n", "2 2\n", "3 3\n", "4 2\n", "5 1\n", "6 1\n", "7 2\n", "8 1\n", "9 1\n", "10 2\n", "11 1\n", "12 2\n", "13 1\n", "14 2\n", "15 2\n", "16 1\n", "17 2\n", "18 2\n", "19 2\n", "20 2\n", "21 2\n", "22 2\n", "23 1\n", "24 2\n", "25 2\n", "26 2\n", "27 2\n", "28 3\n", "29 3\n", " ..\n", "46 2\n", "47 2\n", "48 2\n", "49 2\n", "50 1\n", "51 1\n", "52 2\n", "53 2\n", "54 2\n", "55 1\n", "56 1\n", "57 2\n", "58 2\n", "59 2\n", "60 3\n", "61 1\n", "62 1\n", "63 1\n", "64 1\n", "65 1\n", "66 1\n", "67 1\n", "68 2\n", "69 1\n", "70 2\n", "71 1\n", "72 2\n", "73 3\n", "74 2\n", "75 2\n", "Name: degree, Length: 76, dtype: int64" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# There are totally 77 rows of data.\n", "# Here, 76 of 77 rows are picked to train the model, with the last one remaining as the test set.\n", "state = sh_weather.loc[0:75,'degree']\n", "state" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[3,\n", " 2,\n", " 2,\n", " 3,\n", " 2,\n", " 1,\n", " 1,\n", " 2,\n", " 1,\n", " 1,\n", " 2,\n", " 1,\n", " 2,\n", " 1,\n", " 2,\n", " 2,\n", " 1,\n", " 2,\n", " 2,\n", " 2,\n", " 2,\n", " 2,\n", " 2,\n", " 1,\n", " 2,\n", " 2,\n", " 2,\n", " 2,\n", " 3,\n", " 3,\n", " 2,\n", " 3,\n", " 2,\n", " 2,\n", " 3,\n", " 2,\n", " 3,\n", " 2,\n", " 2,\n", " 2,\n", " 2,\n", " 1,\n", " 1,\n", " 3,\n", " 3,\n", " 2,\n", " 2,\n", " 2,\n", " 2,\n", " 2,\n", " 1,\n", " 1,\n", " 2,\n", " 2,\n", " 2,\n", " 1,\n", " 1,\n", " 2,\n", " 2,\n", " 2,\n", " 3,\n", " 1,\n", " 1,\n", " 1,\n", " 1,\n", " 1,\n", " 1,\n", " 1,\n", " 2,\n", " 1,\n", " 2,\n", " 1,\n", " 2,\n", " 3,\n", " 2,\n", " 2]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Train and extract each data.\n", "State=[]\n", "for i in range(76):\n", " State.append(state[i])\n", "State" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "R=[[0,0,0],[0,0,0],[0,0,0]]" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "# Here we define two functions to calculate state transition matrix.\n", "def Pijm(i,j,m):\n", " a=0\n", " for n in range(len(State)): \n", " if State[n]==i:\n", " try:\n", " if State[n+m]==j:\n", " a=a+1\n", " except:\n", " pass \n", " return a/(State[0:len(State)-m].count(i))\n", "\n", "def Rm(m):\n", " for i in range(1,4):\n", " for j in range(1,4):\n", " R[i-1][j-1]=Pijm(i,j,m) \n", " return R" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Hypothesis test of independency\n", "\n", "The Markov chain refers that the probability distribution of the next state can only be determined by the current state, and the events before it in the time series are irrelevant. This means changes of each state are independent from each other. Thereofre, hypothesis test of independence is necessary. Then, we have\n", "\n", "$H_{0}$: The conditions of daily weather are independent.\n", "\n", "The frequency of daily weather conditions\n", "$$\n", "\\begin{array}\n", "11 & 11 & 1 \\\\\n", "11 & 23 & 7 \\\\\n", "1 & 7 & 2\n", "\\end{array}\n", "$$\n", "After the calculation, we have $\\chi^{2}_{4}=6.495, p-value=0.165.$ Hence, this is not evidence against $H_{0}$. We can get state transition matrices as below." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "These Markov matrices, with $m=1$ and $m=2$, are the first and second order Markov tranision probability matrices, and they respectively predict tomorrow and the day after tomorrow's weather conditions, in which each rows from the top to the bottom mean sunny days, cloudy days and rainy days, with each columns representing the probability of next states of sunny days, cloudy days and rainy days." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "matrix([[0.47826087, 0.47826087, 0.04347826],\n", " [0.26829268, 0.56097561, 0.17073171],\n", " [0.09090909, 0.72727273, 0.18181818]])" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m=1\n", "R1=np.matrix(Rm(m)) \n", "R1" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "matrix([[0.43478261, 0.43478261, 0.13043478],\n", " [0.275 , 0.6 , 0.125 ],\n", " [0.18181818, 0.63636364, 0.18181818]])" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m=2\n", "R2=np.matrix(Rm(m)) \n", "R2" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "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.6.5" } }, "nbformat": 4, "nbformat_minor": 4 }