Probability & Queuing Theory & Fourier Transform

이번 포스트에서는 확률, Queuing Theory, Fourier Transform에 대해 다룬다.

무선 시스템 성능에 영향을 주는 요소

• 사용자 밀도, 셀 크기(항상 유동적임), 사용자의 이동 방향과 속도, 통화율, 지속 시간, 인터페이스

=> 이러한 요소를 수학적으로 모델링하기 위해 확률, 통계 이론과 트래픽 패턴이 활용

Probability(확률)

Probability Theory & Statistics

Random Variables (RVs)

• 확률 변수
• 실험 E에 대한 표본공간 S에서 정의
• 실수 값을 갖는 함수 X: S → ℝ

X : sample point 를 real에 mapping 하는 과정

• 두 종류:
  • Discrete → 확률질량함수(PMF)
  • Continuous → 확률밀도함수(PDF)

PMF (Probability Mass Function) : 확률질량함수

• 이산형 변수 X에 대해 정의된 함수 p(k) = P(X = k)

  • p(k)는 0부터 1 사이

  • \[\sum_{k} p(k) = 1\]

PDF (Probability Denisy Funtion) : 확률밀도함수

• 연속형 변수 X에 대해 정의된 함수 f(x)

• 조건:

  • f(x) ≥ 0
  • ∫ f(x) dx = 1

CDF (Cumulative Distribution Function) : 누적분포함수

• F(x) = P(X ≤ x)
• 모든 확률변수에 적용 가능하고, PDF는 CDF의 미분

기대값, 모멘트, 분산

• 기대값:
  • 이산형 확률 변수
  \[\mathbb{E}[X] = \sum_{x} x \cdot p(x)\]
  • 연속형 확률 변수 \(\mathbb{E}[X] = \int_{-\infty}^{\infty} x \cdot f(x)\, dx\)
• 분산: \(\mathrm{Var}(X) = \mathbb{E}[(X - \mathbb{E}[X])^2]\)

---

중요 확률분포

이산 확률분포

1. Poisson distribution (포아송 분포)

정의 : 단위 시간/공간당 평균 \lambda번 사건이 발생할 때, 실제로 발생하는 사건의 수 X의 분포번 사건이 발생할 때, 실제로 발생하는 사건의 수 X의 분포

• 확률 질량 함수

\[P(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}, \quad k = 0, 1, 2, \dots\]

• 기대값과 분산

\[\mathbb{E}[X] = \lambda,\quad \mathrm{Var}(X) = \lambda\]

2. Geometric Distribution (기하 분포)

정의 : 성공 확률이 p일 때, 처음 성공하기까지 걸린 시행 횟수 X의 분포

• 확률 질량 함수

\[P(X = k) = (1 - p)^{k - 1} p, \quad k = 1, 2, 3, \dots\]

• 기댓값과 분산

\[\mathbb{E}[X] = \frac{1}{p},\quad \mathrm{Var}(X) = \frac{1 - p}{p^2}\]

3. Binomial Distribution (이항 분포)

정의 : 고정된 시행 횟수 n중, 특정 사건이 성공할 확률이 p일 때, 성공 횟수 X의 분포

• 확률 질량 함수

\[P(X = k) = \binom{n}{k} p^k (1 - p)^{n - k}, \quad k = 0, 1, \dots, n\]

• 기댓값과 분산

\[\mathbb{E}[X] = np,\quad \mathrm{Var}(X) = np(1 - p)\]

연속 확률분포

1. Normal Distribution (정규 분포)

정의 : 평균을 중심으로 종 모양을 갖는 대칭 분포

• 확률 밀도 함수

\[f(x) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left( -\frac{(x - \mu)^2}{2\sigma^2} \right), \quad -\infty < x < \infty\]

• 기댓값과 분산

\[\mathbb{E}[X] = \mu, \quad \mathrm{Var}(X) = \sigma^2\]

2. Uniform Distribution (균등 분포)

정의 : 주어진 구간 [a,b] 내에서 모든 값이 동일한 확률을 갖는 분포

• 확률 밀도 함수

\[f(x) = \begin{cases} \frac{1}{b - a} & \text{if } a \le x \le b \\ 0 & \text{otherwise} \end{cases}\]

• 기댓값과 분산

\[\mathbb{E}[X] = \frac{a + b}{2}, \quad \mathrm{Var}(X) = \frac{(b - a)^2}{12}\]

3. Exponential Distribution (지수 분포)

정의 : 사건이 일어날 때까지의 대기 시간을 모델링

• 확률 밀도 함수

\[f(x) = \begin{cases} \lambda e^{-\lambda x} & \text{if } x \ge 0 \\ 0 & \text{otherwise} \end{cases}\]

• 기댓값과 분산

\[\mathbb{E}[X] = \frac{1}{\lambda}, \quad \mathrm{Var}(X) = \frac{1}{\lambda^2}\]

---

다중 확률변수

정의 : 둘 이상의 확률 변수를 동시에 다루는 개념

1. Joint Probability (결합 확률 분포)

• 이산형

\[P(X = x, Y = y) = p(x, y)\]

• 연속형

\[\int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f_{X,Y}(x, y) \, dx \, dy = 1\]

2. Independence (사건의 독립)

정의 : 두 확률 변수가 서로 영향을 주지 않는 경우 \(P(X = x, Y = y) = P(X = x) \cdot P(Y = y) \quad \text{또는} \quad f_{X,Y}(x, y) = f_X(x) f_Y(y)\)

3. Conditional Probability (조건부 확률)

정의 : 어떤 조건 하에서의 확률 분포를 의미

• 이산형

\[P(X = x \mid Y = y) = \frac{P(X = x, Y = y)}{P(Y = y)}\]

• 연속형

\[f_{X \mid Y}(x \mid y) = \frac{f_{X,Y}(x, y)}{f_Y(y)}\]

• Bayes’ Theorem (베이즈 정리)

정의 : 어떤 사건이 발생했을 때, 그 원인이 되었을 확률을 조건부 확률을 통해서 역으로 추론하는 수학적 공식 \(P(A \mid B) = \frac{P(B \mid A) \cdot P(A)}{P(B)}\)

---

확률변수의 성질

1. 선형성 (Linearity of Expectation)

\[\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]\]

• 두 확률 변수 X와 Y가 독립인지 아닌지 상관없이 항상 성립

1. 곱의 기대값 (독립인 경우에만 성립)

\[\mathbb{E}[XY] = \mathbb{E}[X] \cdot \mathbb{E}[Y] \quad \text{(if \(X, Y\) are independent)}\]

1. 분산의 합 (마찬가지로 독립일 경우)

\[\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y) \quad \text{(if \(X, Y\) are independent)}\]

---

중심극한정리 (Central Limit Theorem)

정의 : 어떤 분포를 따르는 모집단이든, 표본 크기 n이 충분히 크면 그 표본평균의 분포는 정규분포를 따른다.

• 수식

\[\bar{X}_n \xrightarrow{d} \mathcal{N}(\mu, \frac{\sigma^2}{n}) \quad \text{as } n \to \infty\] \[Z = \frac{\bar{X}_n - \mu}{\sigma / \sqrt{n}} \xrightarrow{d} \mathcal{N}(0, 1)\]

문제 정리

1. 광부는 세 개의 문 중 하나를 무작위 (1/3 확률) 로 선택

• 각 문의 결과는 다음과 같음.

문 번호	결과	소요 시간
1번 문	탈출 성공	2시간
2번 문	다시 광산	3시간
3번 문	다시 광산	5시간

sol)

우리가 구할 값: 광부가 처음으로 탈출하기까지 걸리는 기대 시간 = E

• 문1을 고를 확률: 1/3 → 즉시 2시간
• 문2를 고를 확률: 1/3 → 3시간 + 다시 E만큼 걸림
• 문3을 고를 확률: 1/3 → 5시간 + 다시 E만큼 걸림

\[E = \frac{1}{3}(2) + \frac{1}{3}(3 + E) + \frac{1}{3}(5 + E)\] \[E = \frac{2}{3} + \frac{1}{3}(3 + E) + \frac{1}{3}(5 + E) = \frac{2}{3} + \frac{3}{3} + \frac{E}{3} + \frac{5}{3} + \frac{E}{3} = \frac{10}{3} + \frac{2E}{3}\] \[3E = 10 + 2E \Rightarrow E = 10\]

=> 광부가 탈출할 때까지의 기대 소요시간은 10시간이다.

---

Queueing Theory

Poisson Arrival Model

• 랜덤한 시간 간격으로 사건 발생.

• 도착률 λ: 단위 시간당 평균 발생 수

  • 특징

    • 시간 t 동안 n개의 도착 확률
    \[P(N(t) = n) = \frac{(\lambda t)^n e^{-\lambda t}}{n!}\]

    • (Interarrival Time)

      • T₁, T₂, T₃,… → 서로 독립
      \[f_T(t) = \begin{cases} \lambda e^{-\lambda t}, & t \geq 0 \\ 0, & t < 0 \end{cases}\]
      • 평균
      \[E[T] = \frac{1}{\lambda}\]

    • **Memoryless Property (중요) **

      • 어떤 시간이 일어나기까지 기다리는 시간이 이미 일정 시간만큼 경과했더라도, 앞에 기다린 시간과 관계없이 앞으로 기다릴 시간의 분포는 변하지 않는다는 성질
      \[P(T > s + t \mid T > s) = P(T > t)\]
      • 예시 ) 버스 기다리는 시간이 지수 분포를 따른다고 할 때, 이미 10분을 기다렸어도, 앞으로 버스가 도착할 때까지의 시간분포는 여전히 같다. (앞의 10분은 아무 영향을 주지 않는다.)

    • Merging Property (중요)

      • 서로 독립적인 두 개 이상의 Possion Process가 있을 때, 이들을 합친(merged) 과정도 Possion Process가 된다는 성질 \(\lambda = \sum_{i=1}^n \lambda_i\)

• Merging, Splittting 도 다 가능

---

Basic Queueing System

• Queue란?
  • 작업이나 고객이 서비스를 받기 위해 기다리는 줄로, 자료구조적 관점에서 먼저 들어온 데이터가 먼저 나가는 구조를 말한다.
  • FIFO(First-In, First-Out)
• Basic Queueing Theory의 3가지 section

1. Traffic Flow

• 사람, 차량, 데이터 패킷 등이 시스템에 들어와서 서비스를 기다리는 흐름을 모델링 한 것
• 주로 도로나 통신망, 공항, 웹서버처럼 대량의 흐름을 다루는 시스템에 사용

2. Scheduling

• 제한된 자원을 효율적으로 배분하여 작업 대기 시간을 최소화하는 데 중점
• 처리하는 관점

**3. Facility Design and Employee Allocation **

• 대기 시간 단축, 혼합 방지, 작업 효율 향상을 목표로 무리적인 공간 배치와 인력 수 조정을 설계

Kendall’s Notation

• A/B/C/D/E:

  • A: 도착 분포 (M=Poisson)
  • B: 서비스 시간 분포

  A와 B는 M, D, Ek, Hk, G에 대한 타입을 가질 수 있음.

  • M : Exponential distribution or Memory
  • D : Degenerate (or Deterministic) distribution
  • Ek : Erlang distribution
  • Hk : Hyper exponential with parameter k
  • G : General distribution

  • C: 서버 수
  • D: 시스템 용량 (몇 바이트까지 : Buffer의 관점)
  • E: 고객 수 제한 (for 시뮬레이션)

예시)

• M / M / 1

=> 도착과 서비스가 모두 지수분포이며, 서버 1개인 시스템

• M / D / 2

=> 도착은 지수분포, 서비스는 고정시간, 서버가 2개인 시스템

• M / M / 1 / 5

=> 최대 고객 수 5명까지 허용되는 단일 서버 큐 (초과 시에 입장을 못함)

Little’s Law

\[L = \lambda \cdot W\]

• N: 평균 시스템 내 고객 수
• λ: 도착률
• T: 체류 시간

=> 얼마나 자주 손님이 오는지 X 얼마나 오래 머무는지로 계산이 가능함.

Markov Process

• 현재 상태가 주어졌을 때, 미래의 상태는 과거와 무관하다는 성질을 가지는 확률 과정
• 즉 현재 상태에만 영향을 준다. (current state)

\[P(X_{n+1} = x_{n+1} \mid X_n = x_n, X_{n-1} = x_{n-1}, \ldots, X_0 = x_0) = P(X_{n+1} = x_{n+1} \mid X_n = x_n)\]

Birth-Death Process

• Special Type of Markov Process
• Birth-Death Process는 시스템의 상태가 정수값을 가지며, 시간에 따라 +1 (birth) 또는 –1 (death) 만큼만 변하는 이산 상태, 연속 시간 마르코프 과정입니다.

상태가 정수 0, 1, 2로 표현될 때,

• Birth(출생) : 상태가 i => i + 1로 전이 \(전이율: \lambda_i\)

• Death(사망) : 상태가 i => i - 1로 전이 \(전이율: \mu_i\)

• \[\lambda P_i = \mu P_{i+1}\]
• Jumping은 바로 옆에 있는 state(neighboring state)끼리만 가능

---

M/M/1/∞ & M/M/1 Queueing System

• Poisson 도착: 고객이 평균 λ의 비율로 도착
• 지수분포 서비스 시간: 한 명당 평균 서비스 시간은 1/μ
• 서버 수 1명
• 무한 대기 공간: 고객 수 제한 없음
• FCFS (First Come First Serve) 방식

Equilibrium State Equation

Queueing System의 상태들이 시간이 지남에 따라 더 이상 변하지 않는 확률 분포를 갖게 될 때 만족하는 식

• 어떤 상황에서 사용?
  • 대기열 이론에서 평균 대기시간, 평균 고객 수 등을 구할 때
  • 시스템이 안정적일 조건을 구할 때

• 수식을 만족해야 변하지 않고 안정적으로 유지됨 \(\lambda P_i = \mu P_{i+1}\)

• 균형 조건 \(\lambda P_i = \mu P_{i+1} \quad \text{for all } i \geq 0\)

Traffic Intensity

• 시스템이 얼마나 바쁜지를 수치로 나타낸 값

• 대기열 이론에서 서버가 처리할 수 있는 속도와 도착 속도를 비교하는 지표

• 기본 식 \(\rho = \frac{\lambda}{\mu}\)

  • \lambda: 고객(또는 요청)의 평균 도착률 (단위: 고객/단위시간)
  • \mu: 고객 1명을 처리하는 평균 서비스율 (단위: 고객/단위시간)
  • \rho: Traffic Intensity (트래픽 강도)
• 만약 트래픽 강도가 1을 넘을 때,
  • Will experience infinite service time

Queueing System Metrics

• 대기열 시스템의 효율성과 혼잡도를 수치적으로 평가하기 위한 기본적인 성능 지표
• 대표 성능 지표들

기호	이름	의미
L	Average number in system	시스템 안에 평균 몇 명이 있는지
L_q	Average number in queue	대기열(줄)에서 평균 몇 명이 기다리는지
W	Average time in system	고객 1명이 시스템에 머무는 평균 시간
W_q	Average time in queue	고객 1명이 대기열에서 대기하는 평균 시간

• 수식 정리

  • 평균 시스템 내 고객 수
  \[L_s = \frac{\lambda}{\mu - \lambda}\]
  • 평균 시스템 체류 시간
  \[W_s = \frac{1}{\mu - \lambda}\]
  • 평균 대기 고객 수
  \[L_q = \frac{\lambda^2}{\mu (\mu - \lambda)}\]
  • 평균 대기 시간
  \[W_q = \frac{\lambda}{\mu (\mu - \lambda)}\]

문제 정리

• 이발사 문제의 확률적 모델을 기반으로 하는 Queueing Theory 문제

문제 요약

• 손님 도착: 포아송 프로세스

   ⇒ interarrival time의 pdf \(a(t) = \lambda e^{-\lambda t}\)

• 서비스 시간:

  • Case A: x = c (고정된 상수)

  • Case B: \(x \sim \text{Exponential}(\mu), b(x) = \mu e^{-\mu x}\)

문제 풀이

1) Case A : Service time - constant

p : 두 번째 손님이 기다리지 않을 확률

두 번째 손님이 기다리지 않기 위해서는, 그가 도착하기 전에 첫 번째 손님의 서비스가 끝나야 한다.

즉, 두 번째 손님의 interarrival time T이 > c여야 함.

\[p = P(T > c) = \int_c^\infty \lambda e^{-\lambda t} dt = e^{-\lambda c}\]

w : 두 번째 손님의 평균 대기 시간

조건부 평균 사용

\[w = \mathbb{E}[\text{wait time}] = \int_0^c (c - t) \cdot \lambda e^{-\lambda t} dt\]

해석하면 \(w = c(1 - e^{-\lambda c}) - \frac{1 - e^{-\lambda c}}{\lambda}\)

\[w = \left( c - \frac{1}{\lambda} \right)(1 - e^{-\lambda c})\]

1. Case B : Service time - Exponential

p : 두 번째 손님이 기다리지 않을 확률

서비스 시간 X가 확률 변수이므로

\[p = P(T > X) = \int_0^\infty P(T > x) \cdot b(x) dx\] \[= \int_0^\infty \left( \int_x^\infty \lambda e^{-\lambda t} dt \right) \cdot \mu e^{-\mu x} dx\] \[= \int_0^\infty e^{-\lambda x} \cdot \mu e^{-\mu x} dx = \mu \int_0^\infty e^{-(\lambda + \mu) x} dx = \frac{\mu}{\lambda + \mu}\]

w : 평균 대기 시간

기대 대기 시간은 두 번째 고객이 기다리는 경우에만 생기므로, 아래 같이

\[w = \mathbb{E}[\text{X} - T | T < X]\] \[w = \frac{1}{\mu} \cdot \frac{\lambda}{\lambda + \mu}\]

---

Fourier Transform

정의 : 신호나 함수를 주파수 영역으로 변환하는 수학적 도구

복잡한 신호를 기본적인 주파수 성분(사인파, 코사인파)의 합으로 바꿈

Dirac Delta Function

• 특정 순간에만 값을 갖고 나머지 시간에는 0인 이상적인 함수
• 충격함수 (Impulse Function) 이라고 부르기도 함.
• 수학적 정의

\[\delta(t) = 0 ( t ≠ 0 )\] \[\int_{-\infty}^{\infty} \delta(t) \, dt = 1\]

• 무한히 얇지만, 면적이 1인 그래프
• 샘플링 속성 성질
  • 어떤 함수 f(t)가 있을 때, 델타 함수와 곱해서 적분하면 델타가 있는 위치의 함수 값만 뽑아낸다는 뜻

\[\int_{-\infty}^{\infty} f(x) \cdot \delta(t - t_0) \, dt = f(0)\]

Unit Step Function

• 말 그대로 특정 시점부터 값이 1로 유지되는 계단같은 함수
• 수학적 정의

\[u(t) = \begin{cases} 0, & t < 0 \\ 1, & t \geq 0 \end{cases}\]

Sinc Function

• 심하게 진동하는 함수
• x=0에서 최댓값이 1이고, 이후 점점 진폭이 줄어들며 양음 교차

• 우함수 (중심 대칭)

• 수학적 정의

\[\mathrm{sinc}(x) = \frac{\sin(\pi x)}{\pi x}\]

Rectangular Function

• 시간축에서 일정 구간에만 1이고, 나머지는 0인 함수
• 시간 영역에서 신호의 구간 제한을 나타낼 때 사용
• 수학적 정의

\[\text{rect}(t) = \begin{cases} 1, & |t| \leq \frac{1}{2} \\ 0, & \text{otherwise} \end{cases}\]

Triangular Function

• 가운데서 최대값을 가지며 좌우 대칭적으로 줄어드는 삼각형 모양의 함수
• 수학적 정의

\[\text{tri}(t) = \begin{cases} 1 - |t|, & |t| \leq 1 \\ 0, & \text{otherwise} \end{cases}\]

---

LTI System

• 정의 : LTI (Linear Time-Invariant System)의 약자로, 선형이고 시간에 불변한 시스템

순서를 지켜야하는 시스템이다.

두 가지의 핵심 조건

1. 선형성(Linearity)

• 입력의 선형 결합이 출력에서도 동일하게 적용된다.
• 입력이 겹치면 출력도 겹친다

\[\text{If } x_1(t) \rightarrow y_1(t), \quad x_2(t) \rightarrow y_2(t)\] \[\text{Then } a x_1(t) + b x_2(t) \rightarrow a y_1(t) + b y_2(t)\]

2. 시간 불변성(Time Invariance)

• 시스템의 성능이 시간에 따라 달라지지 않음.
• 입력 신호를 시간만큼 늦추면, 출력도 똑같이 늦춰진다.

\[\text{If } x(t) \rightarrow y(t), \quad \text{then } x(t - t_0) \rightarrow y(t - t_0)\]

LTI 시스템의 수학적 표현

Impulse Response

• 말 그대로 임펄스 입력을 넣을 때, 시스템이 어떻게 반응하는지 나타내는 함수
• **시스템의 전체 동작은 오직 h(t)만 알면 완전히 예측이 가능함.

\[\delta(t) = \begin{cases} \infty & \text{if } t = 0 \\ 0 & \text{elsewhere} \end{cases}, \quad \int_{-\infty}^{\infty} \delta(t) \, dt = 1\]

LTI의 수학적 표현

• 연속 시간

\[y(t) = x(t) * h(t) = \int_{-\infty}^{\infty} x(\tau) h(t - \tau) d\tau\]

• 이산 시간

\[y[n] = x[n] * h[n] = \sum_{k = -\infty}^{\infty} x[k] h[n - k]\]

여기서 h(t) 또는 h[n]은 시스템의 임펄스 응답(impulse response)이고, *는 컨볼루션(convolution) 연산

---

Taylor Series

• 어떤 함수 f(x)를 기준점 a 주변에서 무한한 다항식의 합으로 근사하는 방법

\[f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!}(x - a)^n\]

따라서, 이렇게 표현 가능 \(e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}\)

\[\sin x \sum_{n=0}^{\infty} \frac{(-1)^n x^{2n+1}}{(2n+1)!}\] \[\cos x \sum_{n=0}^{\infty} \frac{(-1)^n x^{2n}}{(2n)!}\]

Euler’s Formula

• 복소 지수 함수를 삼각 함수로 표현한 공식

\[e^{ix} = \cos x + i \sin x\]

Fourier Transform

• 시간 영역의 신호를 주파수 영역으로 변환하는 수학적 도구
• 복잡한 신호도 사실은 여러 개의 정현파(sine/cosine)가 합쳐진 것
• Fourier Transform은 이 정현파들의 진동수(주파수)와 강도(진폭)를 추출해 주는 것.
• 수학적 정의

\[X(f) = \int_{-\infty}^{\infty} x(t) e^{-j2\pi f t} dt\]

• x(t): 시간 영역의 연속 신호
• X(f): 주파수 영역의 표현 (Fourier Transform)
• f : 주파수 (Hz)

• t : time (with unit of seconds)

• Inverse Fourier Transform
• 주파수 영역에서 다시 시간 영역으로 복원이 가능함.

\[x(t) = \int_{-\infty}^{\infty} X(f) e^{j2\pi f t} df\]

Properties of Fourier Transform

1. 선형성 : 선형 결합은 그대로 전달

• 시간 영역

\[a x_1(t) + b x_2(t)\]

• 주파수 영역

\[a X_1(f) + b X_2(f)\]

2. 시간 이동 : 시간 이동 -< 위상 변화

• 시간 영역 \(x(t - t_0)\)

• 주파수 영역

\[X(f) e^{-j2\pi f t_0}\]

3. 주파수 이동(변조) : 주파수 내 위상 변화

• 시간 영역

\[x(t) e^{j2\pi f_0 t}\]

• 주파수 영역

\[X(f - f_0)\]

4. 시간 반전 : 주파수 반전 발생

5. 컨볼루션 : 주파수의 곱셈

• 시간 영역

\[x(t) * h(t)\]

• 주파수 영역

\[X(f) \cdot H(f)\]

---