The Poisson Distribution

1. Definition of Poisson Random Variable

Def: A Poisson random variable with mean A and probability mass function: $P(X=i) = E^{-A}\frac{A^i}{i!}$

• mean: A
• variance: A

2. Binomial Approximate Poisson

Let $X_i$ be an indicator variable of either 0 or 1. And assume $Pr(X_i = 1) = A/N$ for all i. Then $E[X] = A$.

Based on the assumptions, we have a binomial distribution:

$P(\sum^N_{i=1} X_i = k) = \binom{N}{k}(A/N)^k(1-A/N)^{N-k}$

                                            = $\frac{N!}{(N-k)!k!} (A/N)^k (1-A/N)^{N-k}$

                                            = $e^{-A} A^k/k!$ (A Poisson random variable)

3. Example

$P(X_i =1) =1/365$.
$X = \sum^{400}_{i=1} X_i$ is approximately Poisson with mean 400/365
Then $P(X \geq 2) = 1 - P(X<2) = 1-e^{-A} - Ae^{-A}$

4. Priliminary Definitions

Def : A stochastic process is a collection of random variable (RV) indexed by time $\{X(t), t \in T\}$.

• If T is continuous set, the process is a continuous time stochastic process (e.g., Poisson Process)
• If T is countable, then the process is a discrete time stochastic process (e.g., Markov chain)

Def. A counting process is a stochastic process $\{N(t); t \geq 0\}$ such that

• $N(t) \in \{0,1,\cdots, 2\}$ (that is, N(t) is non-negative integer)
• If $s < t$, the $N(s) \leq N(t)$ ( that is, N(t) is non-decreasing in t)
• For $s<t$, $N(t) - N(s)$ is the number of events occurring in the time interval $(s,t]$.

Def: A counting process has stationary increments if the distribution of the number of events in an interval depends on the length of the interval, but not on the starting point of the interval. That is, $P(N(s+t) - N(s) =  n)$ does not depend on s. Intuitively, the interval can be "slide" around without changing its stochastic nature.

Computing Expectation by Conditioning

• Basic Idea: Compute the expectation or variance of a (complicated)  random variable by conditioning on another random variable.
• In stochastic process, it is often useful to condition on the first event
• Use of the formula
• $E[X] = E[E[X|Y]]$
• $var[X] = var[E[X|Y]] + E[var[X|Y]]$

Example:

Exponential Distribution and Properties

- Stochastic Process course notes

1. Definition

• Probability function: $f(x) = \lambda e^{-\lambda x}$, $x \geq 0$
• Cumulative Distribution Function (CDF): $F(x) = 1-e^{-\lambda x}$, $x \geq 0$
• Complement of the CDF (CCDF): $F^c(x) = e^{-\lambda x}$, $x \geq 0$.

2. Memoryless Property

Def`1: A random variable X has the memoryless property if $Pr\{X>t+s| X>s\} = Pr\{X>t\}$

Def`2: A random variable X has the memoryless property if $Pr\{X>t+s\} = Pr\{X>t\} Pr\{X>s\}$

The exponential distribution is the only distribution that has the memoryless property (Satisfy definition 2)

3. Useful Properties: First occurrence among events

Assume $X_1, X_2, \cdots, X_n$ are exponential variable with rate $\lambda_1, \lambda_2, \cdots, \lambda_n$.
Then what is the probability that $X_1 < X_2$.

More generally

$Pr\{X_i = min[X_1,\cdots, X_n]\} = \frac{\lambda_i}{\lambda_1+\lambda_2+\cdots +\lambda_n}$

4. Distribution of time of first event

This is the CDF of an exponential RV with rate $(\lambda_1 + \lambda_2)$, therefore

$min(X_1, X_2)$ ~ $exp(\lambda_1 + \lambda_2)$

5. Distribution of time of last event (maximum)

Excess Distribution of Renewal Process

Excess Distribution of Renewal Process

- Course notes of Stochastic Process, 2014 Fall

1. Definition

Excess of renewal process is defined as $Y(t) = S_{N(t)+1} -t$ (time until next event)

In the example of average time waiting bus, we drived

$\lim_{t \to \infty} \frac{\int^T_0 Y(u)du}{T} = \frac{E[X_n]}{2} + \frac{car[X_n]}{2E[X_n]}$

Now we are going to derive $Pr(X(t) >x)$ for a random $t$.
Interpretation: You show up "at random". What is the probability that you wait more than x for the next event?

2. Derivation of $Pr(X(t) > x)$

As we want to determine the fraction of time that $Y(t) > x$. 

Let $ I(t) = 1$ if $Y(t) > x$, and let $I(t) = 0$ otherwise.

Interpretation: Fraction of time that $Y(t) > x$ = Fraction of "on" time for $I(t)$

Let $Z_j$ be "on" time during cycle $j$, then $Z_j = max(X_j - x, 0)$

• $Z_j = X_j -x$ if $X_j > x$
• $Z_j = 0$ otherwise

Note: the ON time and OFF time for each cycle are dependent. A longer ON time implies a shorter OFF time.

Then we have

$E[Z_j] = E[max(X_j -x, 0)] = \int^{\infty}_0 Pr(max(X_j- x, 0) > u) du$

                                               = $\int^{\infty}_0 Pr\{X_j - x > u\} du$

                                               = $\int^{\infty}_0 Pr\{X_j > x+ \mu\} d\mu$

                                               = $\int^{\infty}_x Pr\{X_j > \mu\} d\mu$

Since $I(t)$ is an alternating renewal process, fraction of "on" time is

$\frac{E[Z_j]}{E[X_j]} = \frac{1}{E[X_j]} \int^{\infty}_x F^c(u) dy$

This is sometimes called equilibrium distribution,

                                                

3. Example of different distribution of $X(t)$

Example: $X_j$ ~ exp$(\lambda)$

$Pr(Y(t) >x) = \frac{1}{E[X_j} \int^{\infty}_{x} F^c(\mu) d\mu = \frac{1}{\lambda} \int^{\infty}_x e^{-\lambda \mu} d\mu$

                     = $e^{-\lambda x}$

As expected (by memoryless property), excess distribution is an exponential distribution.

Example: Pareto Distribution 

$Pr(X_j > x) = (1+x)^{-\alpha}$

$\alpha$ is also called the tail distribution

Some properties: $E[X_j ] = \frac{1}{\alpha}$ (mean only exist if $\alpha >1$

$Pr(Y(t) > x) = \frac{1}{E[X_j]} \int^{\infty}_x F^c(u) du = (1+x)^{-(\alpha-1)}$

Example: Deterministic $X_j = D$

- Assume $F^c(\mu) = 1$ if $\mu \leq D$, otherwise $F^c(\mu) = 0$.

$Pr(Y(t) \geq x) = \frac{1}{E[X_j]} \int^{\infty}_x F^c(\mu) d\mu $

                            = $\frac{1}{D} \int^{D}_{x} d du$

                            = $1 - \frac{x}{D}$

This is the CCDF of a uniform distribution on $[0,D]$.

Note: the above assume that $x \leq D$, If $x > D$, then the result is 0.

Alternating Renewal Process

Alternating Renewal Process

1. Definition

Consider a process $X(t)$ with "on" periods and "off" periods

• Let $Z_j \equiv$ ON time of cycle j
• Let $Y_j \equiv$ OFF time of cycle j

Then $Z_j$ and $Y_j$ must satisfy the following property in order for $X(t)$ to be regenerative

The pair $(Z_j, Y_j)$ must be i.i.d; in particular, $(Z_j, Y_j)$ independent of $(Z_i, Y_i)$ for $i \neq j$. That is

• $Z_j$ are i.i.d
• $Y_j$ are i.i.d
• However, $Z_j$ and $Y_j$ may be independent for the same j

Cycle time $X_j = Z_j + Y_j$.

Then by the regenerative process, we have

the average "up" time = $\frac{\mbox{average up time in a cycle}}{\mbox{average time of one cycle}} = \frac{E[Z_j]}{E[Z_j] + E[Y_j]}$

2. Example

Cars pass a point on highway according to Poisson process with rate $\lambda = 2/min$. $1/5$ of cars are speeding (>10 mph over the pretend speed limit). Assume time to issue a ticket~UNIF[10,14] minutes(one officer)

Question: What fraction of speeding cars pass when the officer is busy.

Answer: The answer to the question is equivalent to the fraction of time the officer is busy.

• Let $Y_j$ =  time spent waiting to give a ticker
• Let $Z_j$ = time spent giving a ticker

Speeders arrive according to Poisson process with rate $2 \cdot 1/5 = 2/5$ per min.

Fraction of time busy = $\frac{E[Z_j]}{E[Z_j] + E[Y_j]} = \frac{12}{12+5/2} = \frac{12}{14.5}$

Renewal Process

Regenerative Process

Stochastic Process Notes, from Lecture 10

1. Definition

A stochastic process $X(t)$ is a regenerative process if

• Process stochastically starts over at even time $S_1, S_2, \cdots$
• Times between events $X_1, X_2, \cdots$ are i.i.d

2. Regenerative Process v.s. Renewal Process

• A renewal process $N(t)$ counts (increasing over time) and has property 2 shown above.
• A regenerative process $X(t)$ keeps track of something else and starts over.

3. Example

NP Hard Problems and Reduction Example

3 partition http://en.wikipedia.org/wiki/3-partition_problem