Mid

Random Variable¶

The result of experiments (random events)

Markov's Inequality¶

for $X \geq 0$ and $a > 0$

\begin{matrix} P (X \geq a) \leq \frac{E [X]}{a} \end{matrix}

Proof¶

Define a lower bound r.v. $Y$ . That is

Y = {\begin{cases} a & if X \geq a \\ 0 & if 0 < X < a \end{cases}

thus,

\begin{matrix} Y \leq X \end{matrix}

then,

\begin{matrix} E [X] \geq E [Y] = a P (X \geq a) \\ ⟹ P (X \geq a) \leq \frac{E [X]}{a} \end{matrix}

Chebyshev's Inequality¶

for $X$ is r.v. having mean $μ$ and variance $σ^{2}$ , then for $k > 0$ ,

\begin{matrix} P (| X - μ | \geq k σ) \leq \frac{1}{k^{2}} \end{matrix}

Proof¶

\begin{matrix} P (| X - μ | \geq k σ) = P ((X - μ)^{2} \geq k^{2} σ^{2}) \end{matrix}

and by Markov's inequality, we now have,

\begin{matrix} P (| X - μ | \geq k σ) = P ((X - μ)^{2} \geq k^{2} σ^{2}) \leq \frac{E [(X - μ)^{2}]}{k^{2} σ^{2}} = \frac{1}{k^{2}} \end{matrix}

Law of Large Number¶

Weak Law of Large Number¶

Let $\bar{X} = \frac{1}{n} \sum X_{i}$ , and $X_{i}$ are i.i.d., and for any $ϵ > 0$

\begin{matrix} P (| \bar{X} - μ | \geq ϵ) \to 0, when n \to \infty \end{matrix}

Proof¶

First of all,

\begin{matrix} E [\bar{X}] = μ \\ Var (\bar{X}) = \frac{1}{n^{2}} \sum_{i} Var (X_{i}) = \frac{σ^{2}}{n} \end{matrix}

since i.i.d., $Cov (X_{i}, X_{j}) = 0$

then by Chebyshev's inequality,

\begin{matrix} P (| \bar{X} \geq μ | \geq k \frac{σ}{\sqrt{n}}) \leq \frac{1}{k^{2}} \\ ⟹ P (| \bar{X} \geq μ | \geq ϵ) \leq \frac{σ^{2}}{n ϵ^{2}} \end{matrix}

Central Limit Theorem¶

The sum of samples is also an normal distribution when $n \to \infty$ .
The sample mean is normal distributed.

Let $X_{1}, X_{2}, \dots$ be a sequence of i.i.d. random variables with mean $μ$ and variance $σ^{2}$ . Then,

\begin{matrix} lim_{n \to \infty} P (\frac{\sum X_{i} - n μ}{σ \sqrt{n}} < x) = Φ (x) \end{matrix}

in which $Φ (x)$ is cdf of standard normal distribution.

Monte Carlo Approach¶

\begin{aligned} θ & = \int_{0}^{1} g (x) d x \\ = E [g (U)] \\ = lim_{n \to \infty} \frac{\sum^{n} g (U_{i})}{n} \end{aligned}

Acceptance-Rejection Method¶

required

\begin{matrix} \frac{f (y)}{c g (y)} \leq 1 \end{matrix}

To solve $c$ , find the maximum of $\frac{f (y)}{g (y)}$ . Then find $y^{*}$ such that

\begin{matrix} y^{*} = \arg max_{y} \frac{f (y)}{g (y)} \\ c \geq \frac{f (y^{*})}{g (y^{*})} \end{matrix}

Normally, we hope $c$ as small as possible (to make the rejection rate lower). Thus we could let

\begin{matrix} c = \frac{f (y^{*})}{g (y^{*})} \end{matrix}

Standard Normal R.V. Example

absolute value of Z

\begin{matrix} f (x) = \frac{2}{\sqrt{2 π}} e^{- x^{2} / 2} 0 < x < \infty \end{matrix}

and let say $Y$ be exponential random variable with $λ = 1$

\begin{matrix} g (x) = e^{- x} \end{matrix}

then,

\begin{matrix} \frac{d}{d x} \frac{f (x)}{g (x)} = 0 \\ ⟹ (- x + 1) \exp (- \frac{x^{2}}{2} + x) = 0 \end{matrix}

thus

\begin{matrix} c = \frac{f (1)}{g (1)} = \frac{\sqrt{2 e}}{\sqrt{π}} \end{matrix}

MM1 queue¶

First of all, with the entering rate $λ$ and exiting rate $μ$ , we have the server utilization $ρ$

\begin{matrix} ρ = \frac{λ}{μ} \end{matrix}

and the server would be stable iff $λ < μ$ so that the $ρ < 1$

graph LR
s0((0))
s1((1))
s2((2))
sn-1((n-1))
sn((n))
sn+1((n+1))
s0 --"&lambda;"--> s1
s1 --"&lambda;"--> s2
s1 --"&mu;"--> s0
s2 --"&mu;"--> s1

sn-1 --"&lambda;"--> sn
sn --"&lambda;"--> sn+1
sn --"&mu;"--> sn-1
sn+1 --"&mu;"--> sn

The states transition graph have to follow the rule that the outgoing probability must be equal to ingoing probability. Thus it yields the following equations

{\begin{matrix} λ p_{0} = μ p_{1} \\ (λ + μ) p_{n} = λ p_{n - 1} + μ p_{n + 1} \end{matrix}

in which $n \in ℕ$ , and then we can get $p_{2}$ as

\begin{matrix} (λ + μ) p_{1} = λ p_{0} + μ p_{2} \\ ⟹ λ p_{1} = μ p_{2} \end{matrix}

Recursively, we would have

\begin{matrix} p_{n} = ρ p_{n - 1} \end{matrix}

and since we known that $\sum_{i} p_{i} = 1$ ,

\begin{matrix} \sum_{i} p_{i} = p_{0} \sum_{i} ρ^{i} = p_{0} \frac{1}{1 - ρ} = 1 \\ ⟹ p_{0} = 1 - ρ \\ ⟹ p_{n} = (1 - ρ) ρ^{n} \end{matrix}

and thus we know that the stable state probability of number of customers $n$ waiting in queue is a geometric random variable with failure times $n$ .

Number of Customers in System¶

\begin{aligned} E [N] & = \sum_{n} n \cdot p_{n} \\ = (1 - ρ) \sum n ρ^{n} \\ = (1 - ρ) \sum_{i = 0}^{\infty} \sum_{j = i}^{\infty} ρ^{j} \\ = (1 - ρ) \frac{ρ}{(1 - ρ)^{2}} \\ = \frac{ρ}{1 - ρ} \end{aligned}

Average Departure Rate¶

\begin{matrix} E [N_{D}] = μ ρ = λ \end{matrix}

Waiting Time¶

overall time spent in system $W$

\begin{aligned} E [W] & = \frac{E [N]}{E [N_{D}]} \\ = \frac{E [N]}{λ} \\ = \frac{E [N] / μ}{ρ} \\ = \frac{1}{μ (1 - ρ)} \end{aligned}

time wait in queue $W_{q}$

\begin{aligned} E [W_{q}] & = E [W] - \frac{1}{μ} \\ = \frac{1}{μ (1 - ρ)} - \frac{(1 - ρ)}{μ (1 - ρ)} \\ = \frac{ρ}{μ (1 - ρ)} \end{aligned}

Sample Stats.¶

Sample Mean¶

denotation
- $θ$ – popluation mean
- $σ^{2}$ – population variance
- $\bar{X}$ – sample mean

\begin{aligned} θ & = E [X_{i}] \\ σ^{2} & = Var (X_{i}) \\ \bar{X} & \equiv \sum_{i = 1}^{n} \frac{X_{i}}{n} \\ E [\bar{X}] & = E [\sum_{i = 1}^{n} \frac{X_{i}}{n}] \\ = \frac{1}{n} E [\sum_{i = 1}^{n} X_{i}] \\ = \frac{1}{n} n θ = θ \end{aligned}

\begin{aligned} E [{(\bar{X} - θ)}^{2}] & = Var (\bar{X}) \\ = Var (\sum_{i = 1}^{n} \frac{X_{i}}{n}) \\ = \frac{1}{n^{2}} Var (\sum_{i = 1}^{n} X_{i}) \\ = \frac{1}{n^{2}} n σ^{2} = \frac{σ^{2}}{n} \end{aligned}

Binomial and Negative Binomial¶

Binomial Distribution¶

distribution of number of success $r$ given number of trails $n$

\begin{matrix} P (X = r) = (\binom{n}{r}) p^{r} (1 - p)^{n - r} \end{matrix}

Negative Binomial Distribution¶

distribution of number of trails $n$ given number of success $r$
- namely, distribution of number of failures $k$ given number of success $r$

\begin{matrix} P (X = n) = (\binom{n - 1}{r - 1}) p^{r} (1 - p)^{n - r} \end{matrix}

Geometric Distribution¶

number of trails $n$ until success

\begin{matrix} P (X = n) = p (1 - p)^{n - 1} \end{matrix}

Generation Method¶

CMF

\begin{matrix} F (i) = \sum_{n = 1}^{i} p q^{n - 1} = p \frac{1 - q^{i - 1}}{1 - q} = 1 - q^{i - 1} \end{matrix}

let

\begin{matrix} U = G (i) = 1 - F (i) = q^{i - 1} \end{matrix}

thus

\begin{matrix} i - 1 = \log_{q} U \\ ⟹ G^{- 1} (U) = ⌊ \log_{q} U ⌋ + 1 \end{matrix}

Poisson Distribution¶

$Pois (λ)$
Considering events occur with rate $r$ , with time interval $t$ , there would be average number of events $r t$ per interval.
- say that $λ = r t$ , expected rate of occurrences
- Split the time interval $t$ in to $N$ pieces and make the sub-interval $t^{'}$ very small(i.e. $N$ very large).
- $t^{'} = t / N where N \to \infty then r t^{'} ≪ 1$
- if $r t^{'} ≪ 1$ , it approximates to do one Bernoulli trails in each time interval $t^{'}$ .
- $Pois (λ) \equiv B (n = N, p = r t^{'} = λ / N) \equiv B (n \to \infty, p \to 0)$
$E_{X \sim P o i s} [X] = λ = n p = r t$
$X \sim Pois (λ)$ , indicates $X$ is the number of events occurs in unit time interval (and the event rate is $λ$ ).

\begin{aligned} P {X = i} & = (\binom{n}{i}) p^{i} (1 - p)^{n - i} \\ = (\binom{\cancel n}{i}) \frac{λ^{i}}{\cancel n^{i}} (1 - p)^{n - i} \\ = \frac{λ^{i}}{i!} (1 - p)^{n - i} \\ = \frac{λ^{i}}{i!} (e^{- p})^{n} \\ = \frac{λ^{i}}{i!} e^{- λ} \end{aligned}

hint

\begin{array}{r} lim_{x \to 0} e^{x} = e^{0} (1 + \frac{x}{1!} + \frac{x^{2}}{2!}) \approx 1 + x \end{array}

Generation Method¶

Generate several exponential random variable $E_{i} \sim Exp (λ)$
until $E_{1} + E_{2} + \dots + E_{i} \geq 1 > E_{1} + E_{2} + \dots + E_{i - 1}$

Exponential Distribution¶

time between events in Poisson process
continuous analogue of the geometric distribution.
CDF
- take $Y \sim Pois (λ)$
- split unit time interval to $1 / N$ , where $N$ is large
- then $p = λ / N$

\begin{matrix} P (X \geq k) = (1 - p)^{k N} = e^{- k N p} = e^{- λ k} \\ F (x) = 1 - P (X \geq x) = 1 - e^{- λ x} \end{matrix}

PDF

\begin{matrix} f (x) = F^{'} (x) = e^{- λ x} \end{matrix}

Generation Method¶

Since,

\begin{matrix} F (x) = 1 - e^{- λ x} \\ ⟹ F^{- 1} (U) = \frac{\ln (1 - U)}{- λ} \end{matrix}

identically,

\begin{matrix} F^{- 1} (U) = F^{- 1} (1 - U) = - \frac{1}{λ} \ln U \end{matrix}