{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Markov chain\n", "\n", "[**From SUO, YaoJin; PAN, Xiaoming; CHEN, Yaojie**]\n", "\n", "> Briefly, a Markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.\n", "\n", "* [Origin](#origin)\n", "* [Introduction](#intro)\n", "* [Definition](#definition)\n", " - [Discrete-time Markov chain](#discrete-time)\n", " - [Continuous-time Markov chain](#continuous-time)\n", "* [Markov modelling](#markov)\n", "* [Stationary distribution & optimazed modelling](#optimazedmodelling)\n", "* [Application](#application)\n", " - [Pagerank](#pagerank)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### Origin\n", "\n", "Markov named after the Russian mathematician Andrey Markov. He is well-known for his work on stochastic processes. A primary subject of his research later became known as Markov chains and Markov processes.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### Introduction\n", "\n", "At each step of Markov chain, the system can change from one state to another or keep the current state according to the probability distribution. (We have transition matrix to describe the probability.) The change of state is called transition, and the probability related to different state changes is called transition probability. Random walk or Brownian motion is an example of Markov chain. The state of each step in random walk is the point in the graph. Each step can move to any adjacent point. The probability of moving to each point is the same here, no matter what the previous walk path is. (The memorylessness of stochastic process.)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### Definition\n", "\n", "
\n", "\n", "#### Discrete-time Markov chain\n", "\n", "A discrete-time Markov chain is a sequence of random variables $X_{1}, X_{2}, X_{3}, ... $with the Markov property, namely that the probability of moving to the next state depends only on the present state and not on the previous states:\n", "\n", "$$\n", "P\\left(X_{n+1} = x | X_{1} = x_{1}, X_{2} = x_{2}, ...,X_{n} = x_{n}\\right) = P\\left(X_{n+1} = x | X_{n} = x_{n}\\right)\n", "$$
\n", "If both conditional probabilities are well defined, that is, if $P\\left(X_{n+1} = x | X_{1} = x_{1}, X_{2} = x_{2}, ...,X_{n} = x_{n}\\right)>0$ Then, The possible values of $X_{i}$ form a countable set S called the state space of the chain.\n", "\n", "
\n", "\n", "#### Continuous-time Markov chain\n", "\n", "A continuous-time Markov chain $X_{t} ≥ 0$ is defined by a finite or countable state space S, a transition rate matrix Q with dimensions equal to that of the state space and initial probability distribution defined on the state space. For $i ≠ j$, the elements $q_{ij}$ are non-negative and describe the rate of the process transitions from state $i$ to state $j$. The elements qii are chosen such that each row of the transition rate matrix sums to zero, while the row-sums of a probability transition matrix in a (discrete) Markov chain are all equal to one.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### Markov modelling\n", "\n", "Naive method: iterally multiply the transfer matrice and convergence to stationary vector." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0.34375, 0.21875, 0.21875, 0.21875]\n", "[0.335938, 0.221354, 0.221354, 0.221354]\n", "[0.333252, 0.222249, 0.222249, 0.222249]\n", "[0.333333, 0.222222, 0.222222, 0.222222]\n", "[0.333333, 0.222222, 0.222222, 0.222222]\n" ] } ], "source": [ "# transfer_matrix p\n", "p = [0 0.5 1 0; 1/3 0 0 0.5; 1/3 0 0 0.5; 1/3 0.5 0 0]\n", "# It doesn't matter what we choose v\n", "v = [0.25; 0.25; 0.25; 0.25]\n", "function iterally_multiply(v, p, i)\n", " for _ in 1:i\n", " v = p * v\n", " end\n", " return v\n", "end\n", "println(iterally_multiply(v, p, 3)) \n", "println(iterally_multiply(v, p, 5)) \n", "println(iterally_multiply(v, p, 10))\n", "println(iterally_multiply(v, p, 20))\n", "println(iterally_multiply(v, p, 100))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### Stationary distribution & optimazed modelling\n", "\n", "One easy example is that, today is a rainy day and tomorrow is rainy has the probability 0.7 , if today is a sunny day then tomorrow is rainy at the probability of 0.5. From that we can know the probability of Monday rains and Wednesday also rains is 0.64:\n", "We have the transition matrix:\n", "\\begin{equation}\n", "Q=\n", "\\left(\n", "\\begin{array}{ccc}\n", " 0.7 & 0.3\\\\\n", " 0.5 & 0.5\n", "\\end{array}\n", "\\right)\n", " , Q^2\n", "\\left(\n", "\\begin{array}{ccc}\n", "0.64 & 0.36\\\\\n", "0.6 & 0.4\n", "\\end{array}\n", "\\right)\n", "\\end{equation}\n", "\n", "$Q^2_{(11)}$\n", "is the probability (from Monday rainy to Wednesday rainy).\n", "\n", "To extend that: we want to know what the probability that one day is sunny day. That means we need to know what is $Q^k$. And Q is a closed loop, so we know this Markov chain has a stationary distribution $\\pi$, that $\\pi = \\pi Q$, we got: $\\pi = (0.625, 0.375)$, so for a day it is 0.625 to be rainy day and 0.375 to be sunny day.\n", "\n", "From the example we know the Markov chain has a stationary distribution:\n", "A stationary distribution of a Markov chain is a probability distribution that remains unchanged in the Markov chain as time progresses. \n", "In linear algebra may note that the equation $\\pi = \\pi Q$ looks very similar to the column vector equation $Av = \\lambda v$, for eigenvalues and eigenvectors, with $\\lambda=1$. In fact, by transposing the matrices, $(\\pi Q)^T = \\pi^T \\Longrightarrow Q^T\\pi^T = \\pi^T$. In other words, the transposed transition matrix $Q^T$ has eigenvectors with eigenvalue 11 that are stationary distributions expressed as column vectors. Therefore, if the eigenvectors of $Q^T$ are known, then so are the stationary distributions of the Markov chain with transition matrix Q. In short, the stationary distribution is a left eigenvector (as opposed to the usual right eigenvectors) of the transition matrix.\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×1 Array{Float64,2}:\n", " 0.625 \n", " 0.37500000000000006" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using LinearAlgebra\n", "Q = [0.7 0.3; 0.5 0.5]\n", "A = vcat((Q' - I)[1:1,:],ones(2)')\n", "b = [0 1]'\n", "𝜋 = A\\b" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "### Application\n", "\n", "
\n", "\n", "###### Pagerank\n", "\n", "\n", "PageRank was born in 1998 in the hands of Google's founders Larry Page and Sergey Brin. At the end of the last century when commercial search engines were just starting out and were not so convenient. The semantic analysis of the search terms, the web crawl, and the ranking stragtegy together determine the efficiency of information retrieval. Among them, the ranking algorithm is the most important. Markov chain is one of the best measurement that time.\n", "![page_rank](https://pic4.zhimg.com/80/v2-2372589ce0e3ed1a1211f108693c3cc7_hd.jpg)\n", "Assuming that there are four websites in the internet as the figure shown.\n", "The transition matrice M reflects the user transition trend according to external links. $$\n", "M = \\left[\\begin{array}{cccc}{0} & {0.5} & {1} & {0} \\\\ {1/3} & {0} & {0} & {0.5} \\\\ {1/3} & {0} & {0} & {0.5} \\\\ {1/3} & {0.5} & {0} & {0}\\end{array}\\right]\n", "$$\n", "The $V_{N}$ stands for ranking weight.\n", "![page_rank2](https://pic3.zhimg.com/80/v2-714bae6e50e142556b8972658c78677a_hd.jpg)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.0.3", "language": "julia", "name": "julia-1.0" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.0.3" } }, "nbformat": 4, "nbformat_minor": 2 }