필기용 블로그

○Poisson process {N(t), t ≥ 0}

 ▶다음 조건들을 만족하는 Counting Process (주어진 시간 내에 일어난 사건의 수)

  ▷N(0) = 0

  ▷{N(t), t ≥ 0}

  ▷P(N(t + h) - N(t) = 1} = λh + o(h) (h : 작은 시간 / o(h) : 매우 작은 값들 - 무시 가능)

  ▷P(N(t + h) - N(t) ≥ 2} = o(h) - 2번이상 일어날 가능성 거의 없음.

 ▶N(t), t≥0이 Poisson process라면 (rate λ ＞ 0)

  ▷주어진 간격 t 내의 사건의 수 (N(t + h) - N(t))는 Poisson random variable이다. (mean = λt)

 ▶Interarrival and Waiting time distribution

  ▷T_n : (n-1)번째 사건과 n번째 사건 사이의 간격 (sequence of interarrival times)

  ▷T_n ~ Exp(λ) (mean 1/λ)

  ▷Waiting time S_n ~ Gamma(n, λ)

○Exponential distribution

 ▶Exponential Variable

 ▷Exponential은 Memoryless하다.

  ▷𝑃{𝑋 > 𝑠 + 𝑡 | 𝑋 > 𝑡} = 𝑃{𝑋 > 𝑠}

 ◎주문량에 따른 이익 비교

  ▷X : 고객의 요구 량, EXP(λ)

  ▷t : 재료 주문량

  ▷c : 재료 구입 비용 (c×t) / s : 판매가 (s×t)

 ▶Gamma(n, λ)

  ▷X₁, ...., X_n이 독립적이고 동일한 distrubuted exponential (평균 : 1/λ) 일때

  ▷X₁ + ... + X_n ~ Gamma(n, λ)가 성립한다.

  ▷증명

 ▶P{X₁ < X₂}

  ▷X₁ ~ Exp(λ₁) / X₂ ~ Exp(λ₂)

  ▷P{X₁ < X₂} = λ₁ / λ₁+λ₂

  ▷증명

 ▶P{min(X₁, ..., X_n) > x}

  ▷ = P{X_i > x (모든 i에 대해)}

  ▷ = e^∑_i (λ_i x)

  ◎Greedy Algorithm for the Assignment Problem

   ▷C_i,j : i사람을 j직업에 배치하는데 드는 비용

   ▷여러 사람이 같은 직업을 가질 수는 없다.

   ▷각 비용은 Exponential(1)을 따른다. (independent)

   ▷n명의 사람에게 n개의 직업을 배치할 때, 비용을 최소로 잡는 Algorithm

   ▶Greedy Algorithm 1

    ▷C_i : i번째 사람에 대한 비용

    ▷C_i1 : n개의 independent exponential의 minimum

    ▷E[C₁] = 1/n, E[C₂] = 1/(n-2), ...

    ▷E[C₁ + C₂ + ... + C_n] = 1/n + 1/(n-1) + ... + 1

   ▶Greedy Algorithm 2

    ▷C_i : 알고리즘으로 뽑은 i번째 사람-직업 짝의 비용

    ▷E[C₁] = 1/n^2 (전체 Matrix에서 최소 비용)

    ▷E[C₂] = E[C₁] + 1/(n-2)^2 (C₁의 행, 렬을 제외하고 최소 비용, 얼마나 더 초과하느냐?)

    ▷E[C_n] = E[C_n-1] + 1

    ▷E[C₁ + C₂ + ... + C_n] = 1/n + 1/(n-1) + ... + 1

○The Gambler's Ruin Problem

 ▷Gambler와 Casino의 확률 계산

 ▶규칙

  ▷Gambler의 돈 i, Casino의 자산 N

  ▷Gambler의 승 (p): i+1 / Casino의 승 (1-p=q): i-1

  ▷Gambler의 돈이 0이 되거나 N이 되면 게임을 더 이상 진행할 수 없음. (1의 확률로 loop)

 ▶확률

  ▷P_i = pPi+1 + qPi-1

   ▷P_i+1 - P_i = q/p (P_i - P_i-1)

   ▷P₀ = 0

  ▷등비수열의 합 공식( a(rⁿ) / (r-1) )에 의해 다음과 같이 정리 가능하다.

○Mean Time Spent in Transient State

 ▷Transient State에서 머무는 시간

 ▶s_ij : State i 에서 시작해서, j에서 머무는 평균 시간

  ▷P_T : Transition -> Transition State으로 이동하는 확률들

  ▷δ_i,j = 1 (i = j) / δ_i,j = 0 (i ≠ j) - 처음에 있는 1번 계산

  ▷S_ij = δ_i,j + Σ_k (P_ik s_kj)

   ▷이를 Martix 계산으로 풀면 다음과 같다.

○Time Reversible Markov Chains

 ▷| (i -> i+1로의 transition 수) - (i+1 -> i로의 transition 수)| ≤ 1

○Chapman-Kolmogorov Equation

 ▷N-step transition probabilities를 구하는 방법.

 ▷P{X_n+k = j | X_k = i} = P_i,j의 transition Matrix의 n승에서 i행 j열의 요소

 ▷Transition matrix의 곱을 이용해 구함.

 ▶증명 (여기서 P_i,j n+m

  ▷transition matrix의 행렬곱과 같다. (P(n) = matrix of n-step tansition probabilities)

   ▷P^n+m = Pⁿ P^m

   ▷P⁽²⁾ = P × P

 ◎4일뒤 비가 올 확률

   ▷traisiion matrix (P)

   ▷P²

   ▷P₀,0⁴ = 0.61*0.61 + 0.39*0.52 = 0.5749

○Long-run Proportions

 ▷만약 Markov chain이 irreducible하고 recurrent하다면, 모든 초기 상태에 대해 πj를 정의 가능하다.

  ▷πj : state j에서의 long-run proportion of time. = 1/mj ( mj = E[Nj | X0 = j] )

  ▷πi P_i,jⁿ : i에 대한 long-run proportion과 n회의 transition이후 j State.

  ▷πj ≥ πi P_i,jⁿ ＞ 0 (포함관계?) - Positive Rucurrent한 경우

 ▷만약 Markov chain이 irreducible하고 positive recurrent하다면, unique solution을 가진다.

  ▷πj = Σi πi Pi,j  (j ≥ 1)

  ▷Σj πj = 1

 ◎Unique solution of Long-run Proportions

  ▷연립 방정식을 통해 구할 수 있다.

○Limiting Probabilities

 ▶period of state i ( d(i) )

  ▷i에서 i로 돌아오는데 걸리는 최소 시간

  ▷aperiodic: d(i) = 1

 ▷ergodic: positive recurrent + aperiodic

  ▷irreducible ergodic Markov Chain에 대해서

  ▷α_j = lim_(n->∞) P(X_n = j)가 존재한다. (어느 한 State로 수렴한다.)

   ▷α_j = Σ_i α_i P_i,j ≥ 1

   ▷Σ_j α_j = 1

○Markov Chains

 ▷미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다.

 ▷State Space (I)

  ▷상태들의 집합. 

 ▷Stochastic Process (X_n = i)

  ▷n번 이후의 상태가 i일 확률.

 ▷Markov Stochastic Process

  ▷미래의 상태 X_n+1이 현재의 상태 X_n에만 영향을 받는 Stochastic process

  ▷Time homogeneous

  ▷P_i,j = 현재 상태가 i일때, 다음 상태가 j일 확률

 ▷Transition Matrix

  ▷Pi,j들을 Transition Matrix로 표현한 것.

 ◎어제와 오늘이 내일의 날씨에 영향을 줄때

  ▷O : 비가 옴, X: 비가 오지 않음

  ▶확률들

   ▷O,O -> O : 0.7

   ▷X,O -> O : 0.5

   ▷O,X -> O : 0.4

   ▷X,X -> O : 0.2

  ▷과거 상태 또한 영향을 주기 때문에, Markov Chain으로 바로 만들 수 없다.

  ▷2일의 날씨를 하나의 상태로 묶는다.

  ▷0: (O,O), 1: (X,O), 2:(O,X), 3:(X,X)

 ◎Random Walk Model

  ▷상태 : 정수집합

  ▷확률 : +1 -> p, -1 -> 1-p

  ▶Gambling Model

   ▷상태 : 자연수 집합

   ▷0 또는 N일때 상태를 전이하지 않는다.

○State Classification

 ▶Accessible (i → j)

  ▷P_i,j⁽ⁿ⁾ > 0인 경우 (어떤 0이상의 n에 대해서)

  ▷i에서 j로 접근가능함.

 ▶Communication (i ↔ j)

  ▷2개의 상태 i, j에 대해 i → j, j → i인경우 (서로 accessible한 경우)

  ▶equivalent relation이다.

   ▷Reflective: i ↔ i

   ▷Symmetric: i ↔ j => j ↔ i

   ▷Transitive: i ↔ j, j ↔ k => i ↔ k

 ▶Irreducible

  ▷Communicative한 상태들은 같은 Class에 있음.

  ▷Markov chain에서 class가 오직 하나인 경우, irreducible함.

 ▶Recurrent (재귀적) vs Transient (일시적)

  ▶Recurrent: 언젠가 제자리를 다시 지날수 있는 State

   ▷i가 Recurrent하다면, i과 Commucative한 다른 State도 Recurrent하다.

   ▷f_i,j = 1이면 recurrent하다.

   ▶Positive Recurrent, Null Recurrent

    ▷N_j: 돌아가는데 걸리는 최소 transition, m_j: N_j의 Expectation 일 때

    ▷m_j < ∞이면 positive recurrent, m_j = ∞이면 null recurrent

    ▷i가 Positive Recurrent하다면, i과 Commucative한 다른 State도 Positive Recurrent하다.

  ▷Transient: 한 번 지난 이후에는 다시 지나지 않는 State

  ※Periodic(주기적): 주기적으로 돌아오는 State