Pinsky Ch03 Markov Chain

업데이트:

3. Markov Chains: Introduction

3.1 Definition

Markov Process ${X_t}$란 ${X_t}$가 주어졌을 때, $s > t$인 ${X_s}$가 $u < t$인 ${X_u}$에 영향을 받지 않는 stochastic process 를 뜻합니다. 즉, 미래 상태 값은 현재 상태에만 영향을 받고, 현재 이전의 과거 상태에는 영향을 받지 않는다는 뜻입니다. 이를 수식을 나타내면 아래와 같습니다.

\[\begin{align} P(X_{n+1} = j | X_{0} = i_0, ... , X_{n-1}=i_{n-1}, X_{n} = i) \\ \quad = P(X_{n+1}=j|X_{n}=i) \end{align}\]

one-step transition probability : $P_{ij}^{n, n+1}$

$ P_{ij}^{n, n+1} = P(X_{n+1}=j X_{n} = i) $

one-step transition probability가 시간변수 n에 독립일 때, stationary transition probabilities 라고 말하고

$ P_{ij}^{n, n+1} = P_{ij} $

라고 씁니다.

\[\textbf{P} = \begin{pmatrix} P_{00} & P_{01} & P_{02} & P_{03} & \cdots \\ P_{10} & P_{11} & P_{12} & P_{13} & \cdots \\ P_{20} & P_{21} & P_{22} & P_{23} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ P_{i0} & P_{i1} & P_{i2} & P_{i3} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots \end{pmatrix}\]

위와 같은 행렬을 Markov Matrix 또는 transition probability matrix라고 부른다. Markov Matrix 의 각 요소는 아래와 같은 성질을 가집니다.

\[\begin{align} P_{ij} \geq 0 \quad \text{for} \; i,j = 0,1,2, \cdots, \\ \displaystyle\sum_{j=0}^{\infty}P_{ij} = 1 \quad \text{for} \; i=0, 1, 2, \cdots \end{align}\]

3.2 Transition Probability Matrices of a Markov Chain

Markov Chain을 정의하는 것은 두 가지 입니다. 하나는 one-step transition probability matrix이고, 다른 하나는 time 0에서의, 즉 초기 상태의 확률 분포 입니다. Markov Chain에서 관심분야는 각 프로세스의 현실 가능성에 대한 확률을 구하는 것입니다.

$ \textbf{P}^{(n)} = \parallel P_{ij}^{(n)} \parallel $

그리고

$ P_{ij}^{(n)} = P(X_{m+n} = j X_{m} = i) $

n-step transition probability of a Markov chain

\(\begin{align} P_{ij}^{(n)} = \displaystyle\sum_{k=0}^{\infty} P_{ik}P_{kj}^{(n-1)}, \\ \end{align}\) where we define, \(P_{ij}^{(0)} = \begin{cases} 1 & \quad \text{if } i=j, \\ 0 & \quad \text{if } i \neq j \end{cases}\)

3.3 Some Markov Chain Models

3.3.1 An Inventory Model

3.3.2 The Ehrenfest Urn Model

3.3.3 Markov Chains in Genetics

3.3.4 A Discrete Queueing Markov Chain

3.4 First Step Analysis

3.4.1 Simple First Step Analyses