simple_example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "impressive-arrival",
   "metadata": {},
   "source": [
    "## Markov Chain: simple example\n",
    "\n",
    "https://medium.com/@balamurali_m/markov-chain-simple-example-with-python-985d33b14d19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "pharmaceutical-robin",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import scipy.linalg as la"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "outdoor-alberta",
   "metadata": {},
   "source": [
    "A Markov Chain has a set of states and some process that can switch these states to one another based on a transition model.\n",
    "\n",
    "To understand the concept well, let us look at a very simple example: 2-state Markov Chain. Assume you have 2 shirts — white and blue. Wearing white shirt is represented by W and wearing blue shirt is represented by B.\n",
    "\n",
    "\n",
    "\n",
    "We can define the State Space S as {W, B}. Let us assume the probability of you wearing a white shirt and continue wearing the white shirt is 0.7, probability of changing the white shirt to blue shirt is 0.3. Once you are wearing a blue shirt, the probability of you continue wearing the blue shirt is 0.4 and the probability of changing the blue shirt to white shirt is 0.6.\n",
    "\n",
    "This can be encoded in the transition matrix: $Q = [[P_{ww}, P_{wb}], [P_{bw}, P_{bb}]]$ where $P_{ij}$ is the probability of transitioning from state $i$ to $j$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "extensive-individual",
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = np.matrix([[0.7, 0.3], [0.6, 0.4]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cooperative-lafayette",
   "metadata": {},
   "source": [
    "Suppose you repeat this same process every hour — i.e deciding on which shirt to wear and changing your shirt accordingly. Lets say, at the start you already decided that you will wear a white shirt, so the current state can be defined  as: $X = [1,0]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "reduced-stationery",
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.matrix([1, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "essential-mystery",
   "metadata": {},
   "source": [
    "Assuming the transition matrix does not change, we will check the probabilities of you wearing white or blue shirt at the end of 1st, 2nd and 3rd hours"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "determined-simpson",
   "metadata": {},
   "source": [
    "The calculations for finding out the probabilities are\n",
    "\n",
    "a) At the end of 1 st hour: H1 = I x T\n",
    "\n",
    "b) At the end of 2 hours: H2 = H1 x T\n",
    "\n",
    "c) At the end of 3 hours: H3 = H2 X T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ongoing-porter",
   "metadata": {},
   "outputs": [],
   "source": [
    "H1 = X * Q \n",
    "H2 = H1 * Q \n",
    "H3 = H2 * Q "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "composite-healthcare",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "after 1 hour: [[0.7 0.3]]\n",
      "after 2 hours: [[0.67 0.33]]\n",
      "after 3 hours: [[0.667 0.333]]\n"
     ]
    }
   ],
   "source": [
    "print('after 1 hour:', H1)\n",
    "print('after 2 hours:', H2)\n",
    "print('after 3 hours:', H3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "failing-feeding",
   "metadata": {},
   "source": [
    "### Stationary state\n",
    "\n",
    "1. Repeated Matrix Multiplication"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "studied-negotiation",
   "metadata": {},
   "outputs": [],
   "source": [
    "events = 100\n",
    "H = X * Q \n",
    "for i in range(events):\n",
    "    H *= Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "soviet-sapphire",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "after 100 hours: [[0.66666667 0.33333333]]\n"
     ]
    }
   ],
   "source": [
    "print('after 100 hours:', H)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sustained-austin",
   "metadata": {},
   "source": [
    "2.  Matrix method: $$lim_{n\\rightarrow \\infty} Q^n$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "russian-minnesota",
   "metadata": {},
   "outputs": [],
   "source": [
    "events = 100\n",
    "Qn = np.linalg.matrix_power(Q, events)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "assisted-prize",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Probability of wearing White after a long time: 0.6666666666666629\n",
      "Probability of wearing Blue after a long time: 0.33333333333333154\n"
     ]
    }
   ],
   "source": [
    "print('Probability of wearing White after a long time:', Qn.item(0,0))\n",
    "print('Probability of wearing Blue after a long time:', Qn.item(0,1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "wrapped-bunch",
   "metadata": {},
   "source": [
    "3. Left Eigen Vectors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "sophisticated-compact",
   "metadata": {},
   "outputs": [],
   "source": [
    "values, left = la.eig(Q, right = False, left = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "smaller-creature",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "left eigen vectors = \n",
      " [[ 0.89442719 -0.70710678]\n",
      " [ 0.4472136   0.70710678]] \n",
      "\n",
      "eigen values = \n",
      " [1. +0.j 0.1+0.j]\n"
     ]
    }
   ],
   "source": [
    "print(\"left eigen vectors = \\n\", left, \"\\n\")\n",
    "print(\"eigen values = \\n\", values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "detected-accommodation",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.6666666666666667, 0.3333333333333333]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V = left[:,0]\n",
    "V_normalized = [(x/np.sum(V)).real for x in V]\n",
    "V_normalized"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "earlier-pressure",
   "metadata": {},
   "source": [
    "## Random Walk on Marcov Chain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "solid-injury",
   "metadata": {},
   "outputs": [],
   "source": [
    "state = {0: 'white', 1: 'blue'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "broke-midwest",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial state: white\n"
     ]
    }
   ],
   "source": [
    "nstep = 6\n",
    "start_state = 0\n",
    "curr_state = start_state\n",
    "print('Initial state:', state[curr_state])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "worse-drawing",
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = np.asarray(Q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "statutory-secretariat",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "blue ---> blue ---> white ---> white ---> white ---> stop\n"
     ]
    }
   ],
   "source": [
    "while nstep-1:\n",
    "    curr_state = np.random.choice([0, 1], p=Q[curr_state])\n",
    "    print(state[curr_state], \"--->\", end=\" \")\n",
    "    nstep-=1\n",
    "print(\"stop\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "comfortable-poetry",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}