안녕

n개의 비트 중에서 k개의 비트는 1, 나머지 n - k개의 비트는 0을 가지는 모든 조합의 수는? k = 0부터 시작하여 n개까지를 뽑을 수 있으므로, \(\sum_{k = 0}^{n}\binom{n}{k} = \sum_{k = 0}^{n}\binom{n}{k}1^n1^{n-k} = (1 + 1)^n = 2^n\) 만약 모든 비트가 0이 아닌 경우의 수를 구하고 싶다면 1을 빼면 된다. 참고로 1을 빼는 것은 \(\binom{n}{0}\)을 빼는 것이다. 추가적으로 \(\sum_{i = 0}^{n}(-1)^i\binom{n}{i} = 0\)임을 증명하면, \(\sum_{i = 0}^{n}(-1)^i\binom{n}{i} = \sum_{i = 0}^{n}(-1)^i1^{n - i}\binom{n}{i}\..

\((x + y)^n\) = \(\sum_{k = 0}^{n}\binom{n}{k}x^ky^{n-k}\) 해당 수식을 귀납법을 통해 증명할 수 있습니다. 1. n = 1 일 때 \((x + y)^1 = \binom{1}{0}x^1y^0 + \binom{0}{1}x^0y^1\)이므로 n = 1 일 때는 수식이 맞음을 알 수 있습니다. 2. 증명 n - 1 일 때 맞다고 가정하고, n을 증명합니다. \((x + y)^n\) = \((x+y)(x+y)^{n-1}\)입니다. 이때 n - 1 일 때는 맞다고 가정했으므로, 위의 수식은 \((x + y)\sum_{k = 0}^{n - 1}\binom{n-1}{k}x^ky^{(n-1)-k}\)입니다. 앞의 x + y가 거슬리므로 뒤에 곱해서 식을 전개해봅니다. \(\..

1. Slotted ALOHA Protocol이란? S-ALOHA(Slotted ALOHA Protocol)는 ALOHA의 안 좋은 Performance를 보완하기 위해 만든 프로토콜입니다. 기존의 ALOHA는 너무 성능이 안 좋았고, 추가로 보내는 패킷 수가 0.5개일 때 최고의 성능인데, 이 마저도 0.184밖에 안 됐습니다. Slotted ALOHA는 아래의 그림과 같은 프로토콜입니다. 만약 T라는 시간 조각 '안'에 생성이 된다면, 다음 T 시간에 전송됩니다. 쉽게 말해서 1초마다 전송이 된다고 가정할 때, 0.5초에 패킷이 생성되면, 1초에 패킷을 전송합니다. 만약 0.1초에 생성되어도 1초에 전송이 되고, 0.99초에 생성이 되어도 1초에 전송됩니다. 따라서 0~1초 안에만 다른 패킷이 생성되..

1. ALOHA Protocol이란? ALOHA는 Additive Links On-line Hawaii Area의 준말입니다. 1970년대 하와이 대학교에서 개발한 컴퓨터 네트워킹 시스템입니다. 여러 섬에 분산된 컴퓨터 간 무선 통신으로 데이터를 교환할 때 사용하는 프로토콜입니다. 이때 확률과 통계를 이용해서 ALOHA Protocol의 성능을 측정해보겠습니다. 2. ALOHA Protocol의 원리 기존의 복잡한 통신 시스템에 비해 다른 기본적인 가정이 있습니다. 시간이 정해져 있지 않음 패킷은 즉시 도착한다 별도의 채널이나 동일한 채널에서 ACK를 기다림 (정상 도착했다는 신호) 만약 충돌이 일어나면 Time-Out 혹은 NAK 신호를 받음 충돌이 일어난다면 재전송 단순한 구조입니다. 패킷이 생성되면..

1. The Lognormal Distribution Lognormal에서는 \(X \sim N(\mu, \sigma^2)\)를 따를 때, Y = ln(X) ~ \(N(\mu, \sigma^2)\)로 정의합니다. 그냥 기존의 normal distribution의 pdf에서 x를 ln(x)로 바꾼 게 끝입니다.. 그게 아니라 Random Variable X를 ln(X)로 표현한 형태입니다. 그리고 ln(X)로 바꾼 것을 Y라고 칭합니다. pdf는 \(f(x) = \frac{1}{\sqrt{2\pi}\sigma x}^{-\frac{(ln(x)-\mu)^2}{2\sigma^2}}\)입니다. 정규 분포의 pdf는 \(f(x) = \frac{1}{\sqrt{2\pi}\sigma}^{-\frac{(x-\mu)^2}..

정규 분포의 유용한 특성 중 하나는 바로 다른 분포의 확률에 대한 근삿값을 구할 수 있다는 점입니다. 가장 흔한 예시는 normal distribution을 이용하여 binomial distribution에 대한 근삿값을 구하는 것입니다. 이항 분포가 있을 때, 시행 횟수 n이 커질수록 계산하기 힘듭니다. 하지만 정규 분포로 이러한 이항 분포의 근사값을 쉽게 구할 수 있습니다. 1. Central Limit Theorem central limit theorem, 중심 극한 정리는 간단히 말해서 확률 변수 각각 개인의 분포와는 상관없이, 그 분포의 평균들의 표본 분포가 정규 분포에 근사한다는 이론입니다. 쉽게 말해서 어떤 확률 분포던 상관하지 않고, 그 확률 분포에서 n개를 뽑는다고 가정했을 때, n이 무..

정규 확률 변수의 선형 결합에는 다양한 형태가 있습니다. Y = aX + b와 같은 형태 두 개의 독립 정규 확률 변수의 덧셈 독립적인 정규 확률들의 선형 결합 독립적인 정규 확률 변수의 평균 정도가 있습니다. 우선 Y = aX + b와 같은 형태를 보겠습니다. 1. Y = aX + b random variable X~N(\(\mu, \sigma^2\))가 있다고 했을 때, 또 다른 random variable Y = aX + b을 가정합시다. 그러면 이전에 설명한 random variable의 선형 결합에 따라 Y~N(\(a\mu + b, a^2\sigma^2\))가 됩니다. 만약에 \(a=\frac{1}{\sigma}\)이고, \(b=-\frac{\mu}{b}\)라면 Y~N(0, 1)이 됩니다. 따라..

1. Critical Point : z_a \(z_a\)는 표준 정규 분포의 critical point라고 합니다. 남은 면적을 a로 만드는 값을 \(z_a\)라고 합니다. 이때 \(z_a\)는 (1-a) * 100 percentile를 만드는 값이라고도 볼 수 있습니다. (이때 a < 0.5) 또한 \(\Phi(z_a) = 1 - a\)입니다. 마지막으로 가장 중요한 특징이 있는데, 이는 정규 분포의 대칭성을 활용한 특징입니다. \(P(|Z| \leq z_{a/2}) = P(-z_{a/2} \leq Z \leq z_{a/2}) = \Phi(z_{a/2}) - \Phi(-z_{a/2}) = (1 - a/2) - a/2 = 1-a\) 위의 식은 같은 면적을 이분할해서 대칭으로 만들어서 해결한 특징입니다. ..

1. Normal Distribution이란? 정규 분포란 좌우가 대칭인 분포를 말합니다. 이때 평균이 \(\mu\)이고, 분산이 \(\sigma^2\)인 정규 분포의 pdf는 아래와 같습니다. \(f(x) = \frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}, for -\infty \leq x \leq \infty\)이고, 이때 X~N(\(\mu, \sigma^2\))라고 합니다. 만약 분산이 커지면 정규 분포는 완만하고 낮은 곡선을 가지게 됩니다. (옆으로 넓게 퍼진 형태) 2. Standard Normal Distribution Standard Normal Distribution이란 평균이 0이고 분산이 1인 정규 분포를 말합니다. X~N(..

1. Gamma Distribution이란? 감마 분포는 지수 분포의 정규화된 분포입니다. 확률 변수 X는 k개의 이벤트가 걸리는 시간을 정의합니다. 이때 시간은 항상 0보다 큽니다. 감마 분포의 pdf를 보겠습니다. \(f(x) = \frac{\lambda^kx^{k-1}e^{-\lambda x}}{\Gamma(k)}\), x >= 0일 때 입니다. 만약 x < 0이라면 f(x) = 0입니다. 이때 r(k)는 감마 함수라고 하는 특별한 함수이고, 감마 함수는 아래와 같습니다. \(\Gamma (k) = \int_{0}^{\infty } x^{k-1}e^{-x} dx\) 이때, \(\Gamma(1) = 1, \Gamma(1/2) = \sqrt{\pi}\)라고 정의하고, 일반적으로 \(\Gamma(k) =..