2017年1月4日 星期三

馬可夫鏈 (Markov Chain)

1) Random Variable X

2) Random Process (Stochastic Process) {X(t), t>=0} , 是一個Random Variable 的集合, (t可以是discrete time or continuous time)

3) Markov Process, 也是 Random Process,此Random Process {Xi,i=0,1,2....}是在描述狀態轉移的過程 (所有你會有一群狀態序列Chain), 但此系統的行為是chain中的節點，只和相鄰的節點有關，即你下一個狀態是什麼只取決你上一個狀態有關,而和先前的狀態無關 (此行為是是Markov property, 即Memory-less)

a discrete-time  Markov Process-->  Markov chain(DTMC)
a continuous-time Markov process--> Markov chain (CTMC)

4) Renewal process : is a counting process in which the inter-arrival times are an iid random sequence

在講時間，事件發生的間隔時間為一個隨機變數Ti , 若Ti 彼'此為iid 則此counting process為renewal process。 (只看時間，不看狀態)

5) Markov Renewal Process

Consider a state space  Consider a set of random variables , where  are the jump times and  are the associated states in the Markov chain (see Figure). Let the inter-arrival time, . Then the sequence  is called a Markov renewal process if

6) Semi-Markov process

1. If we define a new stochastic process  for , then the process  is called a semi-Markov processNote the main difference between an MRP and a semi-Markov process is that the former is defined as a two-tuple of states and times, whereas the latter is the actual random process that evolves over time and any realisation of the process has a defined state for any given time. The entire process is not Markovian, i.e., memoryless, as happens in a continuous time Markov chain/process (CTMC). Instead the process is Markovian only at the specified jump instants. This is the rationale behind the name, Semi-Markov.[1][2][3] (See also: hidden semi-Markov model.)

Semi-Markov process 和Markov process的差異是,

會進入到某一個狀態 Xn ,只會發生在特定的時間區間,而不是發生在所有的時間點，因此，Semi-Markov Process 其Markovian 特性 (即memory-less的特性), 只會在特定時間而已 ，而非任意時間區間) 。即在Xn狀態只有和上一個狀態有關。而會落在上一個狀態其時間點也是特定的。

(defined in the above bullet point) where all the holding times are exponentially distributed is called a CTMC
Ergodic

random process is ergodic if its time average is the same as its average over the probability space,

Markov Model  ( 所有狀能已知)

A Markov chain is a stochastic process with the Markov property. The term "Markov chain" refers to the sequence of random variables such a process moves through, with the Markov property"memorylessness"). defining serial dependence only between adjacent periods (as in a "chain").

It can thus be used for describing systems that follow a chain of linked events, where what happens next depends only on the current state of the system.

已定義所有的狀態, 並有定義好從狀態 i 到各個狀態 j 的機率, 若共有N個狀態, 這就有一個矩陣描述每一個狀態彼此間的轉移的機率, ,這就狀態轉移機率矩陣 (State Transition probability matrix)

1. 我們也許想知道, 原本在S0 狀態，經過T步後, 會落在那一個狀態? ( 這會需要知道 Pij : 狀態i 到 j 的機率)
2. S0-->S1-->S2, 一開始在S0走2步後, 出現在S2的機率為何?

Relation to other stochastic processes

1. A semi-Markov process (defined in the above bullet point) where all the holding times are exponentially distributed is called a CTMC. In other words, if the inter-arrival times are exponentially distributed and if the waiting time in a state and the next state reached are independent, we have a CTMC.
${\displaystyle \Pr(\tau _{n+1}\leq t,X_{n+1}=j|(X_{0},T_{0}),(X_{1},T_{1}),\ldots ,(X_{n}=i,T_{n}))=\Pr(\tau _{n+1}\leq t,X_{n+1}=j|X_{n}=i)}$
${\displaystyle =\Pr(X_{n+1}=j|X_{n}=i)(1-e^{-\lambda _{i}t}),{\text{ for all }}n\geq 1,t\geq 0,i,j\in \mathrm {S} }$
2. The sequence ${\displaystyle X_{n}}$ in the MRP is a discrete-time Markov chain. In other words, if the time variables are ignored in the MRP equation, we end up with a DTMC.
${\displaystyle \Pr(X_{n+1}=j|X_{0},X_{1},\ldots ,X_{n}=i)=\Pr(X_{n+1}=j|X_{n}=i)\,\forall n\geq 1,i,j\in \mathrm {S} }$
3. If the sequence of ${\displaystyle \tau }$s are independent and identically distributed, and if their distribution does not depend on the state ${\displaystyle X_{n}}$, then the process is a renewal process. So, if the states are ignored and we have a chain of iid times, then we have a renewal process.
${\displaystyle \Pr(\tau _{n+1}\leq t|T_{0},T_{1},\ldots ,T_{n})=\Pr(\tau _{n+1}\leq t)\,\forall n\geq 1,\forall t\geq 0}$
事件發生的時間和狀態都無關(不論狀態是過去,現在或未來的狀態)

Hidden Markov Model  (存在未知狀態)

 圖來源: http://www.csie.ntnu.edu.tw/~u91029/HiddenMarkovModel.html#1

HMM讓我們可以利用「看得到的」連 續現象去探究、預測另一個「看不到的」連續現象。

References:

1 則留言 :

1. Thanks for sharing, nice post!

Tìm hiểu loại siro vitamin tổng hợp cho bé tốt nhất hiện nay là gì hay trẻ 1 tuổi biếng ăn phải làm sao và để tìm giải pháp trẻ biếng ăn nên cho uống thuốc gì và mẹ nên bổ sung loại vitamin và khoáng chất giúp trẻ phát triển như thế nào và loại thuốc bổ dành cho trẻ biếng ăn tốt nhất hiện nay là gì hay địa chỉ bán máy đưa võng giá rẻ uy tín nhất hiện nay cũng như lựa chọn máy đưa võng nào tốt nhất hiện nay.