Common used random variables

In this post, I am going to summarize some common used random variables for future references.

Bernoulli Distribution

A Bernoulli distribution is the simplest discrete probability distribution, representing a single trial that has only two possible outcomes: success (usually denoted by 1) or failure (usually denoted by 0). $T_{t}$ has one parameter $p$ , which represents the probability of success.

\begin{array}{r} P (X = 1) = p \\ P (X = 0) = 1 - p \end{array}

Mean and Variance

\begin{array}{r} E (X) = p \\ V a r (X) = p (1 - p) \end{array}

Binomial Distribution

A Binomial distribution represents the number of successes in a fixed number of independent Bernoulli trials, each with the same probability of success. The binomial distribution has parameters $(n, p)$ with $n$ as the number of trails and $p$ is the probability of success of one Bernoulli trail.

The PMF is:

\begin{array}{r} X \sim B i n o m i a l (n, p) \\ p (X = k) = (\binom{n}{k}) p^{k} (1 - p)^{n - k} \end{array}

Mean and Variance

\begin{array}{r} E (X) = n p \\ V a r (X) = n p (1 - p) \end{array}

Poisson Distribution

Poisson is a discrete probability distribution to express the probability of a given number of events occurring in a fixed interval of time (i.e. the number of tasks arriving in queuing systems). These events occur with a known mean rate $(λ)$ and independently of the time since the last event. The Poisson distribution deals with the number of occurrences in a fixed period of time, and the exponential distribution deals with the time between occurrences of successive events as time flows by continuously.

The probability mass function is:

P (X = k) = \frac{λ^{k} e^{- λ}}{k!}

The positive real number $λ$ is equal to the expected value, and the variance of $X$ :

λ = E (X) = V a r (X)

The Poisson distribution can be seen as a limit of the binomial distribution under certain conditions. This is known as the Poisson approximation to the binomial distribution.

The Poisson distribution is a good approximation to the binomial distribution when:

$n$ is large (the number of trials is large).
$p$ is small (the probability of success in each trial is small).
The product $n p = λ$ is moderate (the expected number of successes remains constant).

Additivity: if $X_{i} \sim P o i s s o n (λ_{i})$ , for $i = 1, 2, \dots, n$ , and the $X_{i}$ is independent, then

X_{1} + X_{2} + \dots + X_{n} \sim P o i s s o n (λ_{1} + λ_{2} + \dots + λ_{n})

Poisson distribution as an approximation of Binomial distribution

As a rule of thumb, if $n \geq 100$ and $n p < 10$ , the Poisson distribution (taking $λ = n p$ ) can provide a very good approximation to the binomial distribution.

lim_{n \to \infty} B i n o m i a l (x) = \frac{e^{- λ} λ^{x}}{x!}

One important limit is used to prove the approximation:

lim_{n \to \infty} (1 + \frac{r}{n})^{n} = e^{r} or, lim_{h \to 0} (1 + r h)^{1 / h} = e^{r}

To better see the connection between these two distributions, consider the binomial probability of seeing $x$ successes in $n$ trials, with the aforementioned probability of success, $p$ , as shown below.

P (x) = (\binom{n}{x}) p^{x} (1 - p)^{n - x}

Let denote the expected value of the binomial distribution as $λ = n p$ , which means $p = \frac{λ}{n}$ . Here $λ$ is also the arriving rate of success event of the approximated Poisson distribution.

The probability mass function can be written as follows:

P (x) = (\binom{n}{x}) (\frac{λ}{n})^{x} (1 - \frac{λ}{n})^{n - x}

Using the standard formula for the combinations of $n$ things taken $x$ at a time and some simple properties of exponents, we can further expand things to

P (x) = \frac{n (n - 1) \dots (n - x + 1)}{x!} \cdot \frac{λ^{x}}{n^{x}} (1 - \frac{λ}{n})^{n - x}

Notice that there are exactly x𝑥 factors in the numerator of the first fraction. Let us swap denominators between the first and second fractions, splitting then^x$ all of the factors of the first fraction’s numerator.

P (x) = \frac{n}{n} \cdot \frac{n - 1}{n} \dots \frac{n - x + 1}{n} \cdot \frac{λ^{x}}{x!} (1 - \frac{λ}{n})^{n} \cdot (1 - \frac{λ}{n})^{- x}

Finally, applying the limit to $P (x)$ and keeping $x, λ$ Fiexed:

\begin{array}{r} (1) & lim_{n \to \infty} P (x) = \frac{λ^{x}}{x!} lim_{n \to \infty} (\frac{n}{n} \cdot \frac{n - 1}{n} \dots \frac{n - x + 1}{n}) \cdot (1 - \frac{λ}{n})^{- x} \cdot lim_{n \to \infty} (1 - \frac{λ}{n})^{n} \\ (2) & = \frac{e^{- λ} λ^{x}}{x!} \end{array}

Exponential Distribution

For the continuous version of exponential distribution, the probability density function (PDF):

f (x; λ) = {\begin{cases} λ e^{- λ x} & if x \geq 0 \\ 0 & if x < 0 \end{cases}

Here $λ$ > 0 is the parameter of the distribution, often called the rate parameter. The distribution is supported on the interval [0, $\infty$ ). If a random variable X has this distribution, we write $X \sim E x p (λ)$ .

The cumulative distribution function:

F (x; λ) = {\begin{cases} 1 - e^{- λ x} & if x \geq 0 \\ 0 & if x < 0 \end{cases}

The CDF and PDF are not the actual probability. For continuous probability distribution, we only compute the probability of a given interval instead of one single point. Because the probability $P (a \leq x \leq b)$ is the integral of PDF values in the range of $[a, b]$ and the area under a single point is infinitesimally small. The CDF is the integral of PDF, we can simple compute the probability as:

P (a \leq x \leq b) = F (b) - F (a)

where $F (x)$ is the CDF of $x$ .

Property:

Mean: $\frac{1}{λ}$
Variance: $\frac{1}{λ^{2}}$
Memoryless: The exponential distribution and the geometric distribution are the only memoryless probability distributions.

Poisson Process

Let $λ > 0$ be fixed. The counting process $N (t), t \in [0, \infty)$ is called a Poisson Process with rate $λ$ if all the following conditions hold:

$N (0) = 0$ ;
$N (t)$ has independent increments;
The number of arrivals in any interval of length $τ > 0$ has $P o i s s o n (λ τ)$ distribution.

Note that from the above definition, we conclude that in a Poisson process, the distribution of the number of arrivals in any interval depends only on the length of the interval, and not on the exact location of the interval on the real line. Therefore the Poisson process has stationary increments.

We denote $X_{1}$ as the interval of the first arrival, the $T_{1}$ is the time instant of first arrival.

Arrivals

If $N (t)$ is a Poisson process with rate $λ$ , then the. interarrival times $X_{1}, X_{2}, \dots$ are independent and

X_{i} \sim E x p o n e n t i a l (λ)

$X$ is a memoryless random variable, that is

P (X > x + a | X > a) = P (X > x)

Thinking of the Poisson process, the memoryless property of the interarrival times is consistent with the independent increment property of the Poisson distribution. In some sense, both are implying that the number of arrivals in non-overlapping intervals are independent.

Since the arrival time can be derived by:

$\begin{array}{r} (3) & T_{1} = X_{1} \\ (4) & T_{2} = X_{1} + X_{2} \\ (5) & T_{3} = X_{1} + X_{2} + X_{3} \end{array}$ More specifically, $T_{n}$ is the sum of $n$ independent $E x p o n e n t i a l (λ)$ random variables. Then $T_{n} \sim G a m m a (n, λ)$ . Note that here $n \in N$ . The $G a m m a (n, λ)$ is also called Erlang distribution, i.e, we can write

T_{n} \sim E r l a n g (n, λ) = G a m m a (n, λ)

The PDF of $T_{n}$ , for $n = 1, 2, 3, \dots$ , is given by

f_{T_{n}} (t) = \frac{λ^{n} t^{n - 1} e^{- λ t}}{(n - 1)!}

and

E (T_{n}) = \frac{n}{λ} V a r (T_{n}) = \frac{n}{λ^{2}}

Markov Chain

Given the past states $X_{0}, X_{1}, \dots, X_{n} - 1$ and the current state $X_{n}$ , a Markov chain is a stochastic process, where the conditional distribution of any future state $X_{n + 1}$ is independent of the past states and depends solely on current state. The $P_{i j}$ represents the probability of the process transiting from state $i$ to $j$ , and the one-step transition matrix is a 2D matrix containing all possible probability of states transition. The multiple step transition can be obtained by the Chapman-Kolmogorov Equations:

P_{i j}^{n + m} = \sum_{k = 0}^{\infty} P_{i k}^{n} P_{k j}^{m}

Two states $i$ and $j$ that are accessible to each other are called to communicate. For any state, the process can never change since once entered is an absorbing state. Two states that communicate with each other are said to be in the same class, each state class is separate with another one. The Markov chain is irreducible if there is only one class (i.e., all states communicate with each other).

Limiting Probabilities

For an irreducible ergodic Markov (one class) chain $lim_{n \to \infty} P_{i j}^{n}$ exists and is independent of $i$ . It shows the limiting probability that the process will be in state $j$ at time $n$ , which equals to the long-run proportion of time that the process will be in state $j$ .

Mean Time Spent in Transient States

Considering a finite state Markov chain with states in range $T = 1, 2, \dots, t$ , the transition probabilities matrix is a $t \times t$ matrix $P_{T}$ . We denote the identity matrix as $I$ . For transient state $i, j$ , let $s_{i j}$ denotes the expected number of time periods that the Markov chain is in state $j$ , given it starts from state $i$ . The matrix format for transient state times is $S$ , we have:

S = (I - P_{T})^{- 1}

For each element, we can also compute the transition probability $f_{i j}$ from state $i$ to state $j$ :

f_{i j} = \frac{s_{i j} - δ_{i j}}{s_{j j}}

Where $δ_{i j}$ is the corresponding element in identity matrix.