Markov Chain

A Markov chain, named after Andrey Markov is a mathematical system that experiences transitions from one state to another, between a finite or countable number of possible states. Markov chain is a random process usually characterized as memoryless: the next state depends only on the current state and not on the sequence of events that preceded it. This specific kind of memorylessness is called the Markov property. Markov chains have many applications as statistical models of real-world processes.

If the random variables $X_{n-1}$ and $X_n$ take the values $X_{n-1}=i$ and $X_n=j$, then the system has made a transition $S_i \rightarrow S_j$, that is, a transition from state $S_i$ to state $S_j$ at the $n$th trial. Note that $i$ can equal $j$, so transitions within the same state may be possible. We need to assign probabilities to the transitions $S_i \rightarrow S_j$. Generally in the chain, the probability that $X_n=j$ will depend on the whole sequence of random variables starting with the initial value $X_0$.

The Markov chain has the characteristic property that the probability that $X_n=j$ depends only on the immediately previous state of the system. This means that we need no further information at each step other than for each $i$ and $j$,  \[P\{X_n=j|X_{n-1}=i\}\]
which means the probability that $X_n=j$ given that $X_{n-1}=i$: this probability is independent of the values of $X_{n-2},X_{n-3},\cdots, X_0$.

Let us have a set of states $S=\{s_1,s_2,\cdots,s_n\}$. The process starts in one of these states and moves successively from one state to another. Each move is called a step. If the chain is currently in state $s_i$ then it moves to state $s_j$ at the next step with a probability denoted by $p_{ij}$ (transition probability) and this probability does not depend upon which states the chain was in before the current state. The probabilities $p_{ij}$ are called transition probabilities ($s_i  \xrightarrow[]{p_{ij}} s_j$ ). The process can remain in its state, and this occurs in probability $p_{ii}$.

An initial probability distribution, defined on $S$ specifies the starting state. Usually, this is done by specifying a particular state as the starting state.

A Markov chain is a sequence of random variables $X_1, X_2,\cdots,$ with the Markov property that, given the present state, the future and past state are independent. Thus
\[P(X_n=x|X_1=x_1,X_2=x_2\cdots X_{n-1}=x_{n-1})\]
\[\quad=P(X_n=x|X_{n-1}=x_{n-1})\]
Or
\[P(X_n=j|X_{n-1}=i)\]

Example: Markov Chain

A Markov chain $X$ on $S=\{0,1\}$ is determined by the initial distribution given by $p_0=P(X_0=0), \; p_1=P(X_0=1)$ and the one-step transition probability given by $p_{00}=P(x_{n+1}=0|X_n=0)$, $p_{10}=P(x_{n+1}=0|X_n=1)$, $p_{01}=1-p_{00}$ and $p_{11}=1-p_{10}$, so one-step transition probability in matrix form is $P=\begin{pmatrix}p_{00}&p_{10}\\p_{01}&p_{11}\end{pmatrix}$

Markov Chain

References:

  • https://en.wikipedia.org/wiki/Markov_chain
  • http://people.virginia.edu/~rlc9s/sys6005/SYS_6005_Intro_to_MC.pdf
  • http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf

Computer MCQs Online Test

Learn R Programming

Simple Random Walk (Unrestricted Random Walk)

A simple random walk (or unrestricted random walk) on a line or in one dimension occurs with probability $p$ when the walker steps forward (+1) and/or has probability $q=1-p$ if the walker steps back ($-1$). For ith step, the modified Bernoulli random variable $W_i$ (takes the value $+1$ or $-1$ instead of {0,1}) is observed and the position of the walk at the nth step can be found by
\begin{align}
X_n&=X_0+W_1+W_2+\cdots+W_n\nonumber\\
&=X_0+\sum_{i=1}^nW_i\nonumber\\
&=X_{n-1}+W_n
\end{align}
In the gambler’s ruin problems X0=k, but here we assume (without loss of generality) that walks start from the origin so that $X_0=0$.

Simple Random Walk

Several derived results for random walks are restricted by boundaries. We consider here random walks without boundaries called unrestricted random walks. We are interested in

  1. The position of the walk after a number of steps and
  2. The probability of a return to the origin, the start of the walker.

From equation (1) the position of the walker at step n simply depends on the position at $(n-1)$th step, because the simple random walk possesses the Markov property (the current state of the walk depends on its immediate previous state, not on the history of the walks up to the present state)

Furthermore, $X_n=X_{n-1}\pm 1$

and the transition probabilities from one position to another is $P(X_n=j | X_{n-1}=j-1)=p$, and $P(X_n=j|X_{n-1}=j+1)=q$ is independent of the number of plays in the game or steps is represented by n.

The mean and Variance of $X_n$ can be calculated as:
\begin{align*}
E(X_n)&=E\left(X_0+\sum_{i=1}^n W_i\right)\\
&=E\left(\sum_{i=1}^n W_i\right)=nW_n\\
V(X_n)&=V\left(\sum_{i=1}^n W_i\right)=nV(W)
\end{align*}
Since $W_i$ are independent and identically distributed (iid) random variables and where $W$ is the common or typical Bernoulli random variable in the sequence$\{W_i\}$. Thus
\begin{align*}
E(W)&=1.p+(-1)q=p-q\\
V(W)&=E(W^2)-[E(W)]^2\\
&=1^2p+(-1)^2q-(p-q)^2\\
&=p+q-(p^2+q^2-2pq)\\
&=1-p^2-q^2+2pq\\
&=1-p^2-(1-p)^2+2pq\\
&=1-p^2-(1+p^2-2p)+2pq\\
&=1-p^2-1-p^2+2p+2pq\\
&=-2p^2+2p+2pq\\
&=2p(1-p)+2pq=4pq
\end{align*}
So the probability distribution of the position of the random walk at stage $n$ has to mean $E(X_n)=n(p-q)$ and $V(X_n)=4npq$ and variance.

For the symmetric random walk (where $p=½$) after n steps, the expected position is the origin, and it yields the maximum value of $V(X_n)=4npq=4np(1-p)$.

If $p>\frac{1}{2}$ then drift is expected away from the origin in a positive direction and if $p<\frac{1}{2}$ it would be expected that the drift would be in the negative direction.

Since $V(X_n)$ is proportional to $n$, it grows with increasing n, and we would be increasingly uncertain about the position of the walker as $n$ increases.
i.e.
\begin{align*}
\frac{\partial V(X_n)}{\partial p}&=\frac{\partial}{\partial p} {4npq}\\
&=\frac{\partial}{\partial p} \{4np-4np^2 \}=4n-8np \quad \Rightarrow p=\frac{1}{2}
\end{align*}
Just knowing the mean and standard deviation of a random variable does not enable us to identify its probability distribution. But for large $n$, we can apply the CLT.
\[Z_n=\frac{X_n-n(p-q)}{\sqrt{4npq}}\thickapprox N(0,1)\]
Applying continuity correction, approximate probabilities may be obtained for the position of the walk.

Example : Consider unrestricted random walk with $n=100, p=0.6$ then
\begin{align*}
E(X_n)&=E(X_{100})=nE(W)=n(p-q)\\
&=100(0.6-0.4)=20\\
V(X_n)&=4npq=4\times 100\times 0.6 \times 0.4=96
\end{align*}
The position of the walk at the 100th step between 15 and 25 pace/steps from the origin is
\[P(15\leq X_{100}\leq30)\thickapprox P(14.5<X_{100}<25.5)\]
\[-\frac{5.5}{\sqrt{96}}<Z_{100}=\frac{X_{100}-20}{\sqrt{96}}<\frac{5.5}{96}\]
hence
\[P(-0.5613<Z_{100}<0.5613)=\phi(0.5613)-\phi(-0.5613)=0.43\]
where $\phi(Z)$ is the standard normal distribution function.

Simple Random Walk

Read more about Simple Random Walk: Random Walks Model

References

  1. http://www.encyclopediaofmath.org/index.php/Random_walk
  2. http://mathworld.wolfram.com/RandomWalk1-Dimensional.html

Stochastic Processes Introduction

Before starting the introduction of Stochastic Processes, let us start with some important definitions related to statistics and stochastic processes.

Experiment: Any activity or situation having an uncertain outcome.

Sample Space:  The set of all possible outcomes is called sample space and every element $\omega$ of $\Omega$ is called sample point. In the Stochastic process, we will call it state space.

Event and Event Space:  An event is a subset of the sample space. The class of all events associated with a given experiment is defined to be the event space.

An event will always be a subset of the sample space, but for sufficiently large sample spaces, not all subsets will be events. Thus the class of all subsets of the sample space will not necessarily correspond to the event space.

Random Variable:
A random variable is a mapping function that assigns outcomes of a random experiment to real numbers. The occurrence of the outcome follows a certain probability distribution. Therefore, a random variable is completely characterized by its probability density function (PDF). Or

A random variable is a map $X:\Omega \rightarrow R$ such that $F\{X \le x\} = \{\omega \in \Omega:x(\omega)\le x\} \in F$ for all $x \in R$.

Probability Space:  A probability space consists of $(\Omega, \mathfrak{F}, P)$ of three parts, sample space, a collection of events, and a probability measure.

Cumulative Distribution Function (CDF): Probability distribution function for the random variable $X$ such that $F(a) = P\{X \le a\}$.

time line

Time: A point of time either discrete or continuous

State: It describes the attribute of a system at some point in time $S=(s_1, s_2, \cdots, s_t)$.

It is convenient to assign some unique non-negative integer as an index to each possible value of the state vector $S$.

Activity: Something that takes some amount of time (duration) to occur. The activity culminates in an event.

Transition (movement from one state to another) Stochastic Processes

Transition:  Transition is caused by an event and it results in some movement from one state to another state.

Probability Measure:  A probability measure intends to be a function defined for all subsets of $\Omega$.

What is a Stochastic Process?

The word stochastic is derived from the Greek word “stoΩ’kæstIk” meaning “to aim at a target”. Stochastic processes involve a state which changes randomly.
Given a probability space $(\Omega, \mathfrak{F}, P)$  stochastic process $\{X(t), t\in T\}$ is a family of random variables, where the index set $T may be discrete $(T=\{0,1,2,\cdots,\})$ or continuous $(T=[0, \infty))$. The set of possible values which random variables $\{X(t), t\in T\}$ may assume is called the state space of the process, and denoted by $S$.

A continuous time stochastic process $\{X(t), t \in T\}; (T=[0, \infty))$ is said to have an independent increment of for all choices of $\{t_1,t_2, \cdots, t_n\}$, the $n$ random variables $X(t_1) – X(t_0), X(t_2) – X(t_1), \cdots, X(t_n)-X(t_{n-1})$ are independent. Using discrete time the state of the process at time $n+1$ depends only on its state at time $n$.

It is often used to represent the evolution of some random value or system over time.

Examples of Stochastic Processes

Examples of processes modeled as stochastic time series include stock market and exchange rate fluctuations, signals such as speech, audio, and video, medical data such as a patient’s EKG, EEG, blood pressure or temperature, random movement such as Brownian motion or random walks, counting process, Renewal process, Poisson process and Markov process.

Introduction to the Random Walks Model

Generate Random Numbers in R Language

Online MCQs about Computer Science and Information Technology