확률과정06-연속시간형_마르코프과정

Wednesday. May 08, 2019 - 5 mins

Author : Jiwoo Lim

10. 연속시간형 마르코프과정

• 연속시간형 마르코프연쇄=마르코프과정

  • 상태공간은 이산형이나 지수집합은 연속형인 확률과정

  • $P(X(t_{n+1})=i_{n+1}\mid X(t_{n})=i_n,…X(t_{1})=i_{1},X(t_{0})=i_{0})=P(X(t_{n+1})=i_{n+1}\mid X(t_{n})=i_{n})$

• 시간균질성 or 정상전이확률을 갖는 마르코프과정:

  => $P(X(t+s)=j\mid X(s)=i)=P(X(t)=j\mid X(0)=i)$

• 아래 3가지를 정의

  1. $P_{ij}(t)=P(X(t)=j

     X(0)=i)$

  2. $p_i=P(X(0)=i)$

  3. ${P}(t)=[P_{ij}(t)]=\begin{bmatrix} P_{00}(t) &P_{01}(t)&…\ P_{10}(t) & P_{11}(t) & …\ …&…&… \end{bmatrix}$

• 마르코프과정의 성질

  1. $P(X(t)=j)=\Sigma_iP(X(t)=j,X(0)=i)=\sum_ip_iP_{ij}(t)$
  2. ${P}(t+s)={P}(t){P}(s)={P}(s){P}(t)$

• 이산시간 마르코프연쇄에서는 방문횟수/전이횟수 등에 관심이 있었으며 상태에 머무는 시간은 관심대상이 x

  => 각 상태에 머무는 시간은 무시할 수 있었고, 경우에 따라서는 단위시간이라 생각(특정상태에 머문 총시간과 방문횟수가 같게 되므로)

• But 연속시간 마르코프과정에서는 특정상태에 머문 시간도 중요

  • 마르코프과정이 상태 i에 머무는 시간을 $T_i$라 하면 $T_i$는 지수분포 따름(비기억성을 갖는 유일한 연속분포는 지수분포이기 때문)

  • 마르코프과정에서 상태 i에 머무는 시간과 어느 상태로 옮겨가게 될 것인가 하는 문제는 서로 독립적

    (머무는 시간이 다음 상태를 결정하는 데 영향을 준다면 마르코프과정에서 미래의 움직임은 단지 현재 위치에 의해서만 영향을 받는다는 마르코프성질에 모순이 되기 때문)

10.2 생사과정

• 생사과정: 개체들이 시간이 경과함에 따라 새로 생기거나 없어지는 현상을 모형화한 확률과정

• 이를 $X(t)$라 하면 이는 t시점에서의 개체수를 의미

• 포아송과정은 아래와 같이 표현가능

  • $P_{n\,n+1}(h)=\lambda h+o(h), \qquad n\ge0$
  • $P_{nn}(h)=1-\lambda h+o(h), \qquad \mu_0=0,\; n\ge0$
  • $P_{n\,m}(h)=o(h), \qquad m\ne{\,n,\,n+1}$
  • 현재 위치와는 상관없이 항상 일정한 비율로 증가하는 것을 모형화
    • 참고) 8장에서 포아송과정은 아래와 같이 표현가능
      • $P(X(t+h)-X(t)=1\mid X(t)=n)=\lambda h+o(h)$
      • $P(X(t+h)-X(t)=0\mid X(t)=n)=1-\lambda h+o(h)$

• 상태공간 S={0,1,2,…}인 마르코프과정 {$X(t)

  t\ge0$}이 아래 3가지 조건을 만족하면 생사과정이 됨

  • $P_{n\,n+1}(h)=\lambda_nh+o(h), \qquad n\ge0$
  • $P_{n\,n-1}(h)=\mu_nh+o(h), \qquad \mu_0=0,\; n\ge1$

  • $P_{n\,m}(h)=o(h), \qquad m\ne{n-1,\,n,\,n+1}$

  • 현재의 수가 증가율/감소율에 영향을 미치는 일반적인 모형

• 어떠한 시스템 내에 n명이 있는 경우 모수 $\lambda_n$을 갖는 지수분포로 시스템에 도착하고, 모수 $\mu_n$을 갖는 지수분포로 시스템을 이탈하며 도착간격시간과 이탈간격시간은 서로 독립이라고 하자. $Z_n$을 출생간격시간, $Y_n$을 사망간격시간이라 하면, $T_n=min{Z_n,Y_n}$이고, $T_n$은 모수 $\lambda_n+\mu_n$인 지수분포를 따르게 된다.

• 출생과 사망은 서로 독립이므로 다음이 성립한다

  $P_{ii+1}=P(다음상태가i+1\mid 막상태i에 들어감)\ \qquad=P(출생이일어남\mid 막상태i에들어감)\ \qquad=P(출생이먼저일어남\mid 임의의시점에상태i에있음)\ \qquad=P(Z_i<Y_i)\ \qquad=\int_0^{\infty} (1-e^{-\lambda_iy})\mu_ie^{-\mu_iy}dy\ \qquad=\frac{\lambda_i}{\lambda_i+\mu_i}$

  $P_{ii+1}=\frac{\lambda_i}{\lambda_i+\mu_i}$

  $P_{ii-1}=\frac{\mu_i}{\lambda_i+\mu_i}$

  $P_{01}=1$

• 마르코프과정의 적용

  1. 포아송과정
     • 생사과정 {$X_t\mid t\ge0$}에서 모든 n에 대하여 $\lambda_n=\lambda,\quad\mu_n=0$인 경우
     • 즉, 모든 상태에서 사망은 없고 출생률은 동일한 순수출생과정
  2. 율과정
     • 시스템의 각 개체가 동질적인 개체를 생성해낼 수 있고 사망은 없다고 가정
     • 각 개체는 독립이고 한 개체가 새로운 개체를 생산하는 데 걸리는 시간은 모수 $\lambda$인 지수분포를 따른다 가정
     • {$X_t\mid t\ge0$}은 출생률 $\lambda_n=n\lambda$인 순수출생과정
     • 출생비율이 선형함수인 모형
  3. 전염병 모형
     • 전체인구가 N인 지역에 1명의 전염병환자가 발생한 시기를 t=0이라 하자
     • 이 전염병은 불치병이고 전염병에 걸린 사람이 n명일 때 나머지 N-n명 각각이 h시간 동안 전염병에 걸릴 확률이 $n\lambda h+o(h)$라 하자
     • $X_t$를 t 시점에 전염병에 걸린 사람 수라 하면, {$X_t\mid t\ge0$}는 순수출생과정이 되며 이때 $\lambda_n=(N-n)n\lambda$가 된다. 이때 $\lambda_n$은 n의 비선형함수!
  4. 선형증가 모형
     • 시스템 안의 각 개체가 각각 동질적인 개체를 생산해내는 데 걸리는 시간은 모수 $\lambda$인 지수분포를, 각 개체의 수명은 모수 $\mu$인 지수분포를 따른다고 하자
     • {$X_t\mid t\ge0$}는 출생률과 사망률이 각각 $\lambda_n=n\lambda$, $\mu_n=n\mu$인 생사과정
     • 여기서 $\lambda_n=n\lambda+\theta$로 주어지면 이민을 허락하는 선형증가모형이 됨
  5. 이주모형
     • 어느 일정지역에 모수 $\lambda$인 지수분포를 따라 이주해 오고, 각 이주자는 모수 $\mu$인 지수분포를 하는 기간 T 동안 머문다 하자
     • $\lambda_n= \lambda$, $\mu_n=n\mu$
  6. M/M/1 대기행렬모형
     • 미용사가 한명밖에 없는 미장원에 손님은 모수 $\lambda$인 포아송과정으로 도착하고 손님이 서비스를 받기 시작하여 끝날 때까지 걸리는 시간은 모수 $\mu$인 지수분포를 따른다고 하자
     • 손님의 도착간격시간이나 서비스 받는 데 걸리는 시간은 서로 독립이고 손님이 들어왔을 때 아무도 없으면 곧바로 서비스를 받고 서비스를 받고 있는 손님이 있는 경우에는 차례가 올 때까지 기다린다고 하자
     • {$X_t\mid t\ge0$}는 출생비율이 $\lambda_n= \lambda$, 사망비율이 $\mu_n=\mu$인 생사과정
     • 이주모형은 M/M/$\infty$ 모형으로 볼 수 있음
  7. M/M/s 대기행렬모형
     • M/M/I 대기행렬모형 예제에서 미용사가 s명인 경우
     • $X_t=n$이고 $n\le s$이면 s명의 미용사 중 n명만 일하고 있는 경우이므로 손님들이 시스템을 떠날 비율은 $n\mu$이고, $n>s$이면 $s\mu$가 된다.
     • {$X_t\mid t\ge0$}는 출생비율이 $\lambda_n= \lambda$, 사망비율이 $\mu_n=\begin{cases}n\mu,\qquad 1\le{n} \le{s}\ s \mu,\qquad n>s\end{cases}$인 생사과정

10.3 콜모고로프의 미분방정식

• 채프만-콜모고로프의 방정식

  • $P_{ij}(h+t)=\sum_{k\in S}P_{ik}(h)P_{kj}(t)$

  • 위의 식 양변에서 $P_{ij}(t)$를 빼면,

    $P_{ij}(h+t)-P_{ij}(t)=\sum_{k\in S}P_{ik}(h)P_{kj}(t)-P_{ij}(t)\ \hspace{80pt}=\sum_{k\ne i}P_{ik}(h)P_{kj}(t)-(1-P_{ii}(h))P_{ij}(t)$

    여기서 극한과 합의 순서를 바꾸면,

    $\frac{d}{dt}P_{ij}(t)=lim_{h\to0}\frac{P_{ij}(h+t)-P_{ij}(t)}{h}\ \hspace{35pt}=\sum_{k\ne i}[lim_{h\to0}\frac{P_{ik}(h)}{h}]P_{kj}(t)-[lim_{h\to0}\frac{1-P_{ii}(h)}{h}]P_{ij}(t)$

• 마르코프 확률과정에서 상태 i에 머무는 시간 $T_i$는 지수분포를 한다(모수는 $v_i$라 가정). 충분히 작은 시간 h 내에 상태가 2번 이상 변할 확률은 o(h)가 되므로 아래 식이 성립한다

  • $1-P_{ii}(h)=P(T_i<h)=1-e^{-v_ih}=v_ih+o(h)$

  따라서 다음이 성립한다

  • $lim_{h\to 0}\frac {1-P_{ii}(h)} {h}=v_i$

  • $P_{ik}(h),\,(i\ne k)$는 h시간 내에 변환이 일어날 확률 $v_ih+o(h)$과 변환이 상태 k로 옮겨갈 확률 $P_{ik}$의 곱으로 표현 가능

    • $P_{ik}(h)=v_ih*P_{ik}+o(h),\,(i\ne k)$

• 콜모고로프의 후진방정식

  • $\frac{d}{dt}P_{ij}(t)=v_i\sum_{k\ne i}P_{ik}P_{kj}(t)-v_iP_{ij}(t)$
  • $T_i$의 분포와 $P_{ij}$를 이용하여 $P_{ij}(t)$를 구할 수 있음

• 행렬로 표현

  • ${P}(h+t)={P}(h)*{P}(t)$

  • 양변에서 ${P}(t)$를 빼고 h로 나눈 뒤 $h\to0$를 취하면 아래 식이 성립한다

    • ${Q}(전이율행렬)=[q_{ij}]$

      ​ $=lim_{h\to0}\frac{ {P}(h)-I}{h}$

      • $q_{ii}=-v_i,\quad q_{ij}=v_iP_{ij}\quad(i\ne j)$

    • $\frac{d}{dt}{P}(t)={Q}*{P}(t)$

• 콜모고로프의 전진방정식

  • 채프만-콜모고로프의 방정식에서 h와 t의 자리를 바꾸고, 양변에서 $P_{ij}(t)$를 빼고 양변을 h로 나눈 뒤 극한을 취한 방정식
  • $\frac{d}{dt}P_{ij}(t)=\sum_{k\ne j}P_{ik}(t)v_kP_{kj}-v_jP_{ij}(t)$
  • $\frac{d}{dt}{P}(t)={P}(t)*{Q}$

  =>$P_{ij}$와 i 상태에 머무르는 시간 $T_i$의 모수 $v_i$가 주어지면 콜모고로프의 미분방정식을 이용하여 전이행렬 $P_{ij}(t)$를 구할 수 있음!

10.4 극한확률

• 연속시간형 마르코프과정에서의 상태분류는 마르코프연쇄에서의 상태분류와 일치

• 기약마르코프과정은 모든 상태가 동시에 일시적이거나 양재귀이거나 귀무재귀상태

• {$X_t\mid t\ge 0$} 가 기약마르코프과정이면 $\pi_j=lim_{t\to\infty}P_{ij}(t)$ 존재

  • 극한값이 존재하면 미분값 $P’_{ij}(t)$도 수렴하고 그의 극한값도 0이 된다

  • 콜모고로프의 전진방정식에 $t\to\infty$의 극한을 취하고 극한과 합의 순서를 바꾸면,

    $0=lim_{t\to\infty}\frac{d}{dt}P_{ij}(t)=lim_{t\to\infty}[\sum_{k\ne j}v_kP_{kj}P_{ik}(t)-v_jP_{ij}(t)]\ \hspace{85pt}=\sum_{k\ne j}v_kP_{kj}\pi_k-v_j\pi_j$

  • 따라서 모든 j에 대하여 다음이 성립한다

    • $v_j\pi_j=\sum_{k\ne j}v_kP_{kj}\pi_k$

• 초기분포가 극한분포와 같으면, 즉 $p_j=P(X(0)=j)=\pi_j$이면 다음이 성립한다

  • $P(X(t)=j)=\sum_k\pi_kP_{kj}(t)\ \hspace{53pt}=\sum_kP_{kj}(t)lim_{s\to\infty}P_{ik}(s)\ \hspace{53pt}=lim_{s\to\infty}\sum_kP_{kj}(t)P_{ik}(s)=lim_{s\to\infty}P_{ij}(t+s)\ \hspace{53pt}=\pi_j$

  • 극한확률분포 $\pi_j$를 불변초기분포 혹은 정상분포라 부름
  • 극한확률분포 $\pi_j$는 $t\to\infty$일 때 확률과정 $X(t)$가 상태 j에 머무르는 시간의 비율을 나타냄
  • $v_j\pi_j=\sum_{k\ne j}v_kP_{kj}\pi_k$의 왼쪽 항은 상태 j를 떠날 비율, 오른쪽 항은 상태 j에 도착하는 비율을 의미하므로 이 식을 균형방정식이라 부름

• 출생률과 사망률이 각각 $\lambda_n,\mu_n$인 생사과정을 생각해보자

  • $v_n=\lambda_n+\mu_n$
  • $P_{n,n+1}=\frac{\lambda_n}{\lambda_n+\mu_n}$
  • $P_{n,n-1}=\frac{\mu_n}{\lambda_n+\mu_n}$

  상태	떠날비율=도착비율
  0	$\lambda_0\pi_0=\mu_1\pi_1$
  1	$(\lambda_1+\mu_1)\pi_1=\lambda_0\pi_0+\mu_2\pi_2$
  2	$(\lambda_2+\mu_2)\pi_2=\lambda_1\pi_1+\mu_3\pi_3$
  …
  $n\ge1$	$(\lambda_n+\mu_n)\pi_n=\lambda_{n-1}\pi_{n-1}+\mu_{n+1}\pi_{n+1}$

  => $\lambda_n\pi_n=\mu_{n+1}\pi_{n+1}$

  • 위의 식으로부터

    $\pi_1=\frac{\lambda_0}{\mu_1}\pi_0$

    $\pi_2=\frac{\lambda_1}{\mu_2}\pi_1=\frac{\lambda_1\lambda_0}{\mu_2\mu_1}\pi_0$

    …

    $\pi_n=\frac{\lambda_n-1}{\mu_n}\pi_{n-1}=\frac{\lambda_{n-1}\lambda_{n-2}…\lambda_1\lambda_0}{\mu_n\mu_{n-1}…\mu_2\mu_1}\pi_0$

    => $\pi_0=\frac{1}{1+\sum_{n=1}^{\infty}(\lambda_{n-1}\lambda_{n-2}..\lambda_0)/(\mu_n\mu_{n-1}…\mu_1)}$

    => $\pi_0$ 값을 위 식들에 대입함으로써 각각의 $\pi_n$ 구할 수 있음!

Tweet Share

comments powered by Disqus