Stochastic Processes

I. 확률 및 기본 분포 (Probability and Basic Distributions)

1. 확률 변수 (Random Variables) 및 분포 함수

개념	정의 및 특성	공식
이산 확률 변수	동전 던지기, 주사위 던지기와 같이 셀 수 있는 값을 가지며, pmf (Probability Mass Function, 확률 질량 함수)로 정의됨.	pmf: $P(X = x) = p(x)$. $\sum p(x) = 1$ 및 $p(x) \ge 0$.
연속 확률 변수	균일 분포, 정규 분포와 같이 연속적인 값을 가지며, pdf (Probability Density Function, 확률 밀도 함수)로 정의됨.	pdf: $P(a \le X \le b) = \int_a^b f(x)dx$. $\int f(x)dx = 1$ 및 $f(x) \ge 0$.
누적 분포 함수 (cdf)	확률 변수 $X$가 $x$보다 작거나 같을 확률 함수.	이산: $F(x) = \sum_{y \le x} p(y)$. 연속: $F(x) = \int_{-\infty}^x f(y)dy$.
기댓값 (Expectation)	확률 변수 $X$의 평균값.	이산: $\mathbf{E}X = \sum x p(x)$,. 연속: $\mathbf{E}X = \int_{-\infty}^\infty x f(x)dx$,.
분산 (Variance)	$X$가 기댓값에서 얼마나 퍼져있는지를 나타내는 척도.	$\mathbf{V}ar(X) = \mathbf{E}X^2 - (\mathbf{E}X)^2 = \mathbf{E}(X - \mathbf{E}X)^2$.

2. 주요 분포 및 속성

분포	기호	확률 밀도 함수 (pdf/pmf)	주요 속성 및 공식
균일 분포 (Uniform)	$X \sim U(a, b)$	$f(x) = \frac{1}{b-a}$ (단, $a \le x \le b$일 때, 아니면 0).	cdf $F(x) = \frac{x-a}{b-a}$ (단, $a \le x \le b$일 때).
지수 분포 (Exponential)	$X \sim exp(\lambda)$	$f(x) = \lambda e^{-\lambda x}$ (단, $x \ge 0$일 때, 아니면 0).	기댓값: $\mathbf{E}X = 1/\lambda$. 분산: $\mathbf{V}ar(X) = 1/\lambda^2$,. 무기억 속성: $P(X > s+t
포아송 분포 (Poisson)	$X \sim Poi(\lambda)$	$P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}$ (단, $k = 0, 1, 2, ...$).	$\mathbf{E}X = \mathbf{V}ar(X) = \lambda$,.

3. 확률 및 조건부 확률

• 확률의 기본 성질: 어떤 사건 $E$에 대해 $0 \le P(E) \le 1$이며, 전 공간 $S$에 대해 $P(S)=1$이다.
• 합의 법칙: $E_1 \cap E_2 = \emptyset$ (배반 사건)이면 $P(E_1 \cup E_2) = P(E_1) + P(E_2)$ 이다,. 일반적인 경우 $P(E_1 \cup E_2) = P(E_1) + P(E_2) - P(E_1 \cap E_2)$이다.
• 조건부 확률 (Conditional Probability): 사건 $F$가 발생했을 때 사건 $E$가 발생할 확률.
  $P(E|F) = \frac{P(E \cap F)}{P(F)}$
• 베이즈 법칙 (Bayes' Rule): $\{F_1, ..., F_n\}$이 수학적 분할(Partition)일 때 (상호 배타적이며 전체 확률이 1일 때):
  $P(E) = \sum_{i=1}^n P(E \cap F_i) = \sum_{i=1}^n P(E|F_i)P(F_i)$

---

II. 뉴스벤더 모델 (Newsvendor Model)

1. 핵심 개념 및 비용

개념	정의	수학적 표현 (준비량 $X$, 수요 $D$)	단위 비용 (Unit Cost)
판매량 (Sales)	수요와 재고 중 작은 값.	$min(X, D)$,.	-
초과 재고 (Overstock)	재고가 수요를 초과했을 때.	$(X-D)^+$,.	$c_o = (\text{재료 비용}) - (\text{잔존 가치})$ (또는 폐기 비용 고려),.
재고 부족 (Understock)	수요가 재고를 초과했을 때.	$(D-X)^+$,.	$c_u = (\text{소매가}) - (\text{재료 비용})$ (기회 비용),.

• 뉴스벤더 모델의 목표: 초과 재고 비용 $c_o$와 재고 부족 비용 $c_u$의 균형을 맞추는 것.
• 최적 주문량 공식: 총 기대 경제적 비용을 최소화하는 $x^*$를 찾는다.
  $x^* = \text{argmin}_X \{ c_o \mathbf{E}[(X - D)^+] + c_u \mathbf{E}[(D - X)^+] \}$
• 최적 주문량 계산 (Critical Fraction):
  • 연속 분포: $F(y) = \frac{c_u}{c_o + c_u}$를 만족하는 $y$.
  • 이산 분포: $F(y) \ge \frac{c_u}{c_o + c_u}$를 만족하는 가장 작은 $y$,.

2. (S, s) 정책 (고정 주문 비용 포함)

• $S$ (Order-up-to level): 기본 뉴스벤더 모델에서 도출된 최적 주문 수준 $y$와 같다,.
• $s$ (Reorder point, 임계 임계값): 현재 재고 수준 $x$가 $s$보다 낮을 경우에만 $S$까지 주문을 시작하게 되는 임계값,.
  • $s$를 찾으려면, 재고 수준 $x=s$일 때, "S까지 주문하는 총 예상 비용"과 "아무것도 주문하지 않는 총 예상 비용"이 같아지는 지점을 해(solve)해야 한다,.

---

III. 대기 행렬 이론 (Queuing Theory)

1. 기본 요소 및 안정성

• 켄달 표기법 (Kendall's Notation): (도착 시간 분포 / 서비스 시간 분포 / 서버 수 / 대기열 크기).
  • M: 지수 분포 (Markovian/Exponential), D: 결정적/상수 (Deterministic), G: 일반 분포 (General Distribution).
• 교통 강도 (Traffic Intensity): $\rho = \frac{\text{Demand}}{\text{Capacity}}$.
  • $M/M/1/\infty$의 경우: $\rho = \frac{\lambda}{\mu} = \frac{1/\mathbf{E}(U)}{1/\mathbf{E}(V)}$ ($\lambda$: 도착률, $\mu$: 서비스율, $U$: 도착 간격 시간, $V$: 서비스 시간).
• 안정성 (Stability): 무한 대기 공간에서 $\mathbf{\rho < 1}$일 경우 시스템은 안정적이며, $\rho \ge 1$이면 불안정하다 (무한대로 발산),.
• 서버 활용도 (Utilization): 서버가 바쁜 시간의 비율 $u = min(1, \rho)$ (단일 서버),.
• 처리율 (Throughput, TH): 시스템의 유출률. 안정적인 시스템에서 $\text{TH} = \lambda$이다.
  • 단일 서버: $\text{TH} = min(\lambda, \mu)$.
  • 직렬 시스템: $\text{TH} = min(\lambda, \mu_1, \mu_2, ..., \mu_n)$ (가장 느린 서버가 병목).

2. 주요 공식

• 리틀의 법칙 (Little's Law): 시스템 내 고객 수 ($L$)는 도착률 ($\lambda$)과 시스템 내 체류 시간 ($W$)의 곱과 같다.
  $\mathbf{L = \lambda W}$
  • 대기열에서: $L_q = \lambda W_q$.
  • 시스템에서: $L_{sys} = \lambda W_{sys}$.
• 킹맨의 고부하 근사 공식 (Kingman’s approximation, $\rho < 1$): 장기 평균 대기 시간 $W_q$,.
  $\mathbf{E}W_q \approx \mathbf{E}V \left( \frac{\rho}{1-\rho} \right) \left( \frac{c_a^2 + c_s^2}{2} \right)$
  • $c_a^2$: 도착 간격 시간의 변동 계수 제곱. $c_s^2$: 서비스 시간의 변동 계수 제곱.
• M/M/1/$\infty$ 큐잉 모델 (안정적일 때, $\rho < 1$):
  • 시스템 내 평균 고객 수: $L_{sys} = \frac{\rho}{1-\rho}$.
  • 시스템 내 평균 체류 시간: $W_{sys} = \frac{1}{\mu(1-\rho)}$.
  • 대기열 내 평균 고객 수: $L_q = L_{sys} - \rho$ (출처에 명시된 형태는 아니지만 유도됨).
  • 대기열 내 평균 체류 시간: $W_q = \frac{\rho}{\mu(1-\rho)}$.

---

IV. 마르코프 연쇄 (Markov Chain)

1. 이산 시간 마르코프 연쇄 (DTMC)

• 마르코프 속성 (Markov Property): 미래 상태 $X_{n+1}$는 현재 상태 $X_n$에만 의존하며, 과거 이력에는 독립적이다.
  $P(X_{n+1} = j | X_0=i_0, ..., X_n=i) = P(X_{n+1} = j | X_n=i)$
• 전이 확률 행렬 ($P$): $P = [p_{ij}]$이며, $p_{ij} = P(X_{n+1}=j | X_n=i)$이다. $P$는 확률 행렬 (Stochastic matrix)이다 (모든 행의 합이 1),.
• n-단계 전이: $n$단계 후의 상태 분포 $\mathbf{a}_n$은 초기 분포 $\mathbf{a}_0$와 $P$의 $n$제곱을 이용하여 구한다.
  $\mathbf{a}_n = \mathbf{a}_0 P^n$,
• 정상 분포 ($\pi$, Stationary Distribution): 시간이 지나도 분포가 변하지 않는 상태.
  $\mathbf{\pi = \pi P}$ (단, $\sum \pi_i = 1, \pi_i \ge 0$)
  • 이는 유입 균형 방정식 (Flow Balance Equation)과 같다.
• 수렴 정리 (Irreducible + Aperiodic): 유한 상태 DTMC가 기약적(Irreducible)이고 비주기적(Aperiodic)이면, 극한 확률 $lim_{n\to\infty} P^n_{ij} = \pi_j$가 존재하고, 이 값은 유일한 정상 분포 $\pi$와 같다.

2. 연속 시간 마르코프 연쇄 (CTMC)

• CTMC의 정의: 연속 시간 상에서 마르코프 속성을 만족하는 확률 과정.
• 특징: 상태 전이까지의 시간은 지수 분포를 따른다,.
• 레이트 행렬 ($G$, Generator Matrix):
  • $G$ 행렬의 각 행의 합은 0이다.
  • $G$ 행렬의 비대각 원소 $g_{ij}$ ($i \ne j$)는 상태 $i$에서 $j$로의 전이율이다.
• 정상 분포 ($\pi$): $\pi G = 0$을 만족하고 $\sum \pi_i = 1$인 분포.
• CTMC 전이 행렬 $P(t)$: $t$시간 후 상태 $i$에서 $j$로의 전이 확률을 담고 있으며, 다음과 같이 계산된다,.
  $P(t) = e^{tG}$

---

V. 포아송 과정 (Poisson Process, PP)

개념	정의 및 공식
포아송 과정 $PP(\lambda)$	$N(t)$는 계수 과정이며, 겹치지 않는 구간에서의 증가는 독립이며, $N(t_2) - N(t_1)$은 $\lambda(t_2 - t_1)$을 매개변수로 하는 포아송 분포 $Poi(\lambda(t_2-t_1))$를 따른다,.
도착 간격 시간	첫 도착 시간 $T_1$뿐만 아니라 연속적인 도착 간격 시간 $T_n$ 모두 $exp(\lambda)$ 분포를 따른다,. (지수 분포의 무기억 속성에 기인함).
병합 (Merging)	독립적인 $PP(\lambda_A)$와 $PP(\lambda_B)$가 합쳐지면, $PP(\lambda_A + \lambda_B)$가 된다.
세분화 (Thinning)	$PP(\lambda)$에서 각 도착이 확률 $p$로 $A$를 선택하면, $A$의 도착은 $PP(p\lambda)$가 된다.
비균질 포아송 과정 (NHPP)	도착률 $\lambda$가 시간에 따라 변하는 $\lambda(t)$ 함수를 사용하는 경우,.
NHPP 확률 계산	구간 $[s, t+s]$ 동안의 도착 횟수는 다음을 매개변수로 하는 포아송 분포를 따른다.
	$N(t+s) - N(s) \sim Poi\left(\int_{s}^{t+s} \lambda(u)du\right)$