Markov Diagrams - Revision history

Melinda Caroline at 17:38, 17 October 2016

2016-10-17T17:38:13Z

← Older revision		Revision as of 17:38, 17 October 2016
Line 1:		Line 1:
	~~{{Template:InProgress}}~~
	{{Template:bsbook\|11}}		{{Template:bsbook\|11}}
	The term "Markov Chain," invented by Russian mathematician Andrey Markov, is used across many applications to represent a stochastic process made up of a sequence of random variables representing the evolution of a system. Events are "chained" or "linked" serially together though memoryless transitions from one state to another. The term "memoryless" is used because past events are forgotten, as they are irrelevant; an event or state is dependent only on the state or event that immediately preceded it.		The term "Markov Chain," invented by Russian mathematician Andrey Markov, is used across many applications to represent a stochastic process made up of a sequence of random variables representing the evolution of a system. Events are "chained" or "linked" serially together though memoryless transitions from one state to another. The term "memoryless" is used because past events are forgotten, as they are irrelevant; an event or state is dependent only on the state or event that immediately preceded it.

Nicolette Young: /* Discrete Markov Chains */

2016-02-12T16:41:41Z

Discrete Markov Chains

← Older revision		Revision as of 16:41, 12 February 2016
Line 38:		Line 38:
	This will give us the state probability vector after the first step, <math>\underline{X}(1)\,\!</math>.		This will give us the state probability vector after the first step, <math>\underline{X}(1)\,\!</math>.

	If one wants to determine the probabilities of the system being in a particular state after <math>n\,\!</math> steps, the Chapman-Kolmogorov equation can be used. This equation states that the probabilities of being in a state after <math>n\,\!</math> steps can be calculated by taking the initial state vector and multiplying by the transition matrix to the <math>n~~^{th}~~\,\!</math> power, or:		If one wants to determine the probabilities of the system being in a particular state after <math>n\,\!</math> steps, the Chapman-Kolmogorov equation can be used. This equation states that the probabilities of being in a state after <math>n\,\!</math> steps can be calculated by taking the initial state vector and multiplying by the transition matrix to the <math>n\,\!</math>th power, or:

	::<math>\underline{X}(n)=\underline{X}(0) \cdot \underline{P}^n\,\!</math>		::<math>\underline{X}(n)=\underline{X}(0) \cdot \underline{P}^n\,\!</math>

Nicolette Young: /* Discrete Markov Chains */

2016-02-12T16:41:11Z

Discrete Markov Chains

← Older revision		Revision as of 16:41, 12 February 2016
Line 38:		Line 38:
	This will give us the state probability vector after the first step, <math>\underline{X}(1)\,\!</math>.		This will give us the state probability vector after the first step, <math>\underline{X}(1)\,\!</math>.

	If one wants to determine the probabilities of the system being in a particular state after <math>n\,\!</math> steps, the Chapman-Kolmogorov equation can be used. This equation states that the probabilities of being in a state after <math>n\,\!</math> steps can be calculated by taking the initial state vector and multiplying by the transition matrix to the <math>n\,\!</math>th power, or:		If one wants to determine the probabilities of the system being in a particular state after <math>n\,\!</math> steps, the Chapman-Kolmogorov equation can be used. This equation states that the probabilities of being in a state after <math>n\,\!</math> steps can be calculated by taking the initial state vector and multiplying by the transition matrix to the <math>n^{th}\,\!</math> power, or:

	::<math>\underline{X}(n)=\underline{X}(0) \cdot \underline{P}^n\,\!</math>		::<math>\underline{X}(n)=\underline{X}(0) \cdot \underline{P}^n\,\!</math>

Nicolette Young: /* Discrete Markov Chains */

2016-02-12T16:40:23Z

Discrete Markov Chains

← Older revision		Revision as of 16:40, 12 February 2016
Line 34:		Line 34:
	To determine the probability of the system being in a particular state after the first step, we have to multiply the initial state probability vector <math>\underline{X}(0)\,\!</math> with the transition matrix <math>\underline{P}\,\!</math>:		To determine the probability of the system being in a particular state after the first step, we have to multiply the initial state probability vector <math>\underline{X}(0)\,\!</math> with the transition matrix <math>\underline{P}\,\!</math>:

	::<math>\underline{X}(n)=\underline{X}(0) \cdot \underline{P^n}\,\!</math>		::<math>\underline{X}(1)=\underline{X}(0) \cdot \underline{P}\,\!</math>

	This will give us the state probability vector after the first step, ▁X(1).		This will give us the state probability vector after the first step, <math>\underline{X}(1)\,\!</math>.

	If one wants to determine the probabilities of the system being in a particular state after n steps, the Chapman-Kolmogorov equation can be used. This equation states that the probabilities of being in a state after n steps can be calculated by taking the initial state vector and multiplying by the transition matrix to the ~~nth~~ power, or:		If one wants to determine the probabilities of the system being in a particular state after <math>n\,\!</math> steps, the Chapman-Kolmogorov equation can be used. This equation states that the probabilities of being in a state after <math>n\,\!</math> steps can be calculated by taking the initial state vector and multiplying by the transition matrix to the <math>n\,\!</math>th power, or:

	::<math>\underline{X}(0)=\~~begin~~{~~pmatrix~~} 0 ~~& 1 & 0~~ \~~end~~{~~pmatrix~~}\,\!</math>		::<math>\underline{X}(n)=\underline{X}(0) \cdot \underline{P}^n\,\!</math>

	==Example==		==Example==

Nicolette Young: /* Continuous Markov Chains */

2016-02-12T16:36:01Z

Continuous Markov Chains

← Older revision		Revision as of 16:36, 12 February 2016
Line 102:		Line 102:
	*<math>P_j\,\!</math> is the probability of being in state <math>j\,\!</math>		*<math>P_j\,\!</math> is the probability of being in state <math>j\,\!</math>
	*<math>P_l\,\!</math> is the probability of being in state <math>l\,\!</math>		*<math>P_l\,\!</math> is the probability of being in state <math>l\,\!</math>
	*<math>\lambda_{lj}\,\!</math> transition rate from state l to state <math>j\,\!</math>		*<math>\lambda_{lj}\,\!</math> transition rate from state <math>l\,\!</math> to state <math>j\,\!</math>
	*<math>\lambda_{jl}\,\!</math> transition rate from state j to state <math>l\,\!</math>		*<math>\lambda_{jl}\,\!</math> transition rate from state <math>j\,\!</math> to state <math>l\,\!</math>

	Our initial conditions to solve the differential equations are our initial probabilities for each state.		Our initial conditions to solve the differential equations are our initial probabilities for each state.

Melinda Caroline: /* Continuous Markov Chains */

2016-02-12T16:20:34Z

Continuous Markov Chains

← Older revision		Revision as of 16:20, 12 February 2016
Line 159:		Line 159:
	*<math>\lambda_{lj}\,\!</math> is the transition rate from state <math>l\,\!</math> to state <math>j\,\!</math>		*<math>\lambda_{lj}\,\!</math> is the transition rate from state <math>l\,\!</math> to state <math>j\,\!</math>
	*<math>\lambda_{jl}\,\!</math> is the transition rate from state <math>j\,\!</math> to state <math>l\,\!</math>		*<math>\lambda_{jl}\,\!</math> is the transition rate from state <math>j\,\!</math> to state <math>l\,\!</math>
	*<math>f_j\,\!</math> is the change in the probability of being in state <math>P_j\,\!</math> (~~Note~~ that <math>f_j\,\!</math> is not a function of time for constant transition rate Markov chains)		*<math>f_j\,\!</math> is the change in the probability of being in state <math>P_j\,\!</math> (note that <math>f_j\,\!</math> is not a function of time for constant transition rate Markov chains)
	*<math>h\,\!</math> is the time step size		*<math>h\,\!</math> is the time step size
	*<math>t_i\,\!</math> is the time at <math>i\,\!</math>		*<math>t_i\,\!</math> is the time at <math>i\,\!</math>

Melinda Caroline: /* Continuous Markov Chains */

2016-02-12T16:19:47Z

Continuous Markov Chains

← Older revision		Revision as of 16:19, 12 February 2016
Line 157:		Line 157:
	*<math>P_j\,\!</math> is the probability of being in state <math>j\,\!</math>		*<math>P_j\,\!</math> is the probability of being in state <math>j\,\!</math>
	*<math>P_{l,i}\,\!</math> is the probability of being in state <math>l\,\!</math> at time <math>i\,\!</math>		*<math>P_{l,i}\,\!</math> is the probability of being in state <math>l\,\!</math> at time <math>i\,\!</math>
	*<math>\lambda_{lj}\,\!</math> transition rate from state <math>l\,\!</math> to state <math>j\,\!</math>		*<math>\lambda_{lj}\,\!</math> is the transition rate from state <math>l\,\!</math> to state <math>j\,\!</math>
	*<math>\lambda_{jl}\,\!</math> transition rate from state <math>j\,\!</math> to state <math>l\,\!</math>		*<math>\lambda_{jl}\,\!</math> is the transition rate from state <math>j\,\!</math> to state <math>l\,\!</math>
	*<math>f_j\,\!</math> is the change in the probability of being in state <math>P_j\,\!</math> (Note that <math>f_j\,\!</math> is not a function of time for constant transition rate Markov chains)		*<math>f_j\,\!</math> is the change in the probability of being in state <math>P_j\,\!</math> (Note that <math>f_j\,\!</math> is not a function of time for constant transition rate Markov chains)
	*<math>h\,\!</math> is the time step size		*<math>h\,\!</math> is the time step size

Melinda Caroline: /* Continuous Markov Chains */

2016-02-12T16:19:07Z

Continuous Markov Chains

← Older revision		Revision as of 16:19, 12 February 2016
Line 151:		Line 151:
	::<math>\delta=0.84\Big(\frac{\epsilon}{R}\Big)^{\frac{1}{4}}\,\!</math>		::<math>\delta=0.84\Big(\frac{\epsilon}{R}\Big)^{\frac{1}{4}}\,\!</math>

	If <math>R\leq\epsilon\,\!</math> then keep <math>P_{i+1}\,\!</math> as the current solution, and move to next step with step size <math>\delta{h}\,\!</math>.		If <math>R\leq\epsilon\,\!</math> then keep <math>P_{i+1}\,\!</math> as the current solution, and move to next step with step size <math>\delta{h}\,\!</math>; if <math>R>\epsilon\,\!</math> then recalculate the current step with step size <math>\delta{h}\,\!</math>

	If <math>R>\epsilon\,\!</math> then recalculate the current step with step size <math>\delta{h}\,\!</math>

	where:		where:

Melinda Caroline: /* Continuous Markov Chains */

2016-02-12T16:18:08Z

Continuous Markov Chains

← Older revision		Revision as of 16:18, 12 February 2016
Line 151:		Line 151:
	::<math>\delta=0.84\Big(\frac{\epsilon}{R}\Big)^{\frac{1}{4}}\,\!</math>		::<math>\delta=0.84\Big(\frac{\epsilon}{R}\Big)^{\frac{1}{4}}\,\!</math>

	if <math>R\leq\epsilon\,\!</math> keep <math>P_{i+1}\,\!</math> as the current solution, and move to next step with step size <math>\delta{h}\,\!</math>.		If <math>R\leq\epsilon\,\!</math> then keep <math>P_{i+1}\,\!</math> as the current solution, and move to next step with step size <math>\delta{h}\,\!</math>.

	if <math>R>\epsilon\,\!</math> recalculate the current step with step size <math>\delta{h}\,\!</math>.		If <math>R>\epsilon\,\!</math> then recalculate the current step with step size <math>\delta{h}\,\!</math>

	where:		where:

Melinda Caroline: /* Discrete Markov Chains */

2016-02-12T16:08:34Z

Discrete Markov Chains

← Older revision		Revision as of 16:08, 12 February 2016
Line 11:		Line 11:
	A discrete Markov chain can be viewed as a Markov chain where at the end of a step, the system will transition to another state (or remain in the current state), based on fixed probabilities. It is common to use discrete Markov chains when analyzing problems involving general probabilities, genetics, physics, etc.		A discrete Markov chain can be viewed as a Markov chain where at the end of a step, the system will transition to another state (or remain in the current state), based on fixed probabilities. It is common to use discrete Markov chains when analyzing problems involving general probabilities, genetics, physics, etc.
	To represent all the states that the system can occupy, we can use a vector <math>\underline{X}\,\!</math>:		To represent all the states that the system can occupy, we can use a vector <math>\underline{X}\,\!</math>:


	::<math>\underline{X}(0)= (X_1 X_2 \cdot\cdot\cdot X_i) \,\!</math>		::<math>\underline{X}(0)= (X_1 X_2 \cdot\cdot\cdot X_i) \,\!</math>


	where the term <math>X_i\,\!</math> represents the probability of the system being in state <math>i\,\!</math> and with:		where the term <math>X_i\,\!</math> represents the probability of the system being in state <math>i\,\!</math> and with:


	::<math>\sum_{i=1}^{n}X_{i}=1\,\!</math>		::<math>\sum_{i=1}^{n}X_{i}=1\,\!</math>


	The transitions between the states can be represented by a matrix <math>\underline{P}\,\!</math>:		The transitions between the states can be represented by a matrix <math>\underline{P}\,\!</math>:


	::<math> \underline{P} =		::<math> \underline{P} =
Line 32:		Line 27:
	P_{i1} & P_{i2} & \cdots & P_{ii}		P_{i1} & P_{i2} & \cdots & P_{ii}
	\end{pmatrix}\,\!</math>		\end{pmatrix}\,\!</math>


	where, for example, the term <math>P_{12}\,\!</math> is the transition probability from state 1 to state 2, and for any row <math>m\,\!</math> with <math>i\,\!</math> states:		where, for example, the term <math>P_{12}\,\!</math> is the transition probability from state 1 to state 2, and for any row <math>m\,\!</math> with <math>i\,\!</math> states:


	::<math>\sum_{j=1}^{i}P_{mj}=1\,\!</math>		::<math>\sum_{j=1}^{i}P_{mj}=1\,\!</math>


	To determine the probability of the system being in a particular state after the first step, we have to multiply the initial state probability vector <math>\underline{X}(0)\,\!</math> with the transition matrix <math>\underline{P}\,\!</math>:		To determine the probability of the system being in a particular state after the first step, we have to multiply the initial state probability vector <math>\underline{X}(0)\,\!</math> with the transition matrix <math>\underline{P}\,\!</math>:


	::<math>\underline{X}(n)=\underline{X}(0) \cdot \underline{P^n}\,\!</math>		::<math>\underline{X}(n)=\underline{X}(0) \cdot \underline{P^n}\,\!</math>


	This will give us the state probability vector after the first step, ▁X(1).		This will give us the state probability vector after the first step, ▁X(1).

	If one wants to determine the probabilities of the system being in a particular state after n steps, the Chapman-Kolmogorov equation can be used. This equation states that the probabilities of being in a state after n steps can be calculated by taking the initial state vector and multiplying by the transition matrix to the nth power, or:		If one wants to determine the probabilities of the system being in a particular state after n steps, the Chapman-Kolmogorov equation can be used. This equation states that the probabilities of being in a state after n steps can be calculated by taking the initial state vector and multiplying by the transition matrix to the nth power, or:


	::<math>\underline{X}(0)=\begin{pmatrix} 0 & 1 & 0 \end{pmatrix}\,\!</math>		::<math>\underline{X}(0)=\begin{pmatrix} 0 & 1 & 0 \end{pmatrix}\,\!</math>