Poisson processes

Find the Erlang density $f_{S_n}(t)$ by convolving $f_X(x) = \lambda \mathrm{exp}\left(-\lambda x\right)$ with itself $n$ times.

Find the moment generating function (MGF) of $X$ (or find the Laplace transform of $f_X(x)$), and use this to find the moment generating function (or Laplace transform) of $S_n = X_1+X_2+\cdots +X_n$. Invert your result to find $f_{S_n}(t)$.

Find the Erlang density by starting with (2.15) and then calculating the marginal density for $S_n$.

Find the mean, variance, and MGF of $N(t)$, as given by (2.17).

Show by discrete convolution that the sum of two independent Poisson rv's is again Poisson.

Show by using the properties of the Poisson process that the sum of two independent Poisson rv's must be Poisson.

Find the conditional probability $\mathbb {P}\left(N(t) = n \mid S_n = \tau \right)$ for all $\tau \leq t$.

Using the Erlang density for $S_n$, use (a) to find $\mathbb {P}\left(N(t) = n\right)$.

Show that $\mathbb {P}\left(X_1 > x\right) = e^{-\lambda x}$.

Let $S_{n-1}$ be the epoch of the $(n-1)$th arrival. Show that $\mathbb {P}\left(X_n > x \mid S_{n-1} = \tau \right) = e^{-\lambda x}$.

For each $n > 1$, show that $\mathbb {P}\left(X_n > x\right) = e^{-\lambda x}$ and that $X_n$ is independent of $S_{n-1}$.

Argue that $X_n$ is independent of $X_1, X_2, \ldots , X_{n-1}$.

Show that for integer $k > 0$, $h(k) = kc$.

Show that for integer $j > 0$, $h(1/j) = c/j$.

Show that for all integer $k, j$, $h(k/j) = ck/j$.

The above parts show that $h(x)$ is linear in positive rational numbers. For very picky mathematicians, this does not guarantee that $h(x)$ is linear in positive real numbers. Show that if $h(x)$ is also monotonic in $x$, then $h(x)$ is linear in $x > 0$.

Let $F_0(\tau ) = \mathbb {P}\left(N(\tau ) = 0\right)$ and show that $dF_0(\tau )/d\tau = -\lambda F_0(\tau )$.

Show that $X_1$, the time of the first arrival, is exponential with parameter $\lambda$.

Let $F_n^c(\tau ) = \mathbb {P}\left(\widetilde{N}(t, t+\tau ) = 0 \mid S_{n-1} = t\right)$ and show that $dF_n^c(\tau )/d\tau = -\lambda F_n^c(\tau )$.

Argue that $X_n$ is exponential with parameter $\lambda$ and independent of earlier arrival times.

Given that $N(t) = n$, explain why $Z_m = X_{m+n}$ for $m > 1$ and $Z_1 = X_{n+1}-t+S_n$.

Conditional on $N(t) = n$ and $S_n = \tau$, show that $Z_1, Z_2, \ldots$ are IID.

Show that $Z_1, Z_2, \ldots$ are IID.

Show that

Let $t = m\delta$, and let $t$ be fixed for the remainder of the exercise. Explain why

where the limit on the left-hand side is taken over values of $\delta$ that divide $t$.

Derive the following two equalities:

Conclude from this that for every $t$ and every $n$, $\lim_{\delta \to 0} \mathbb {P}\left(N_\delta (t) = n\right) = \mathbb {P}\left(N(t) = n\right)$, where $\left\{ N(t); t > 0\right\}$ is a Poisson process of rate $\lambda$.

Find the joint probability mass function (PMF) of $N(t), N(t+s)$ for $s > 0$.

Find $\mathbb {E}\left[N(t) \cdot N(t+s)\right]$ for $s > 0$.

Find $\mathbb {E}\left[\widetilde{N}(t_1, t_3) \cdot \widetilde{N}(t_2, t_4)\right]$, where $\widetilde{N}(t, \tau )$ is the number of arrivals in $(t, \tau ]$ and $t_1 < t_2 < t_3 < t_4$.

Let $N_k$ denote the number of elementary experiments performed for which the output is $a_k$. Find the PMF for $N_k$ ($1 \leq k \leq K$).

Find the PMF for $N_1+N_2$.

Find the conditional PMF for $N_1$ given that $N = n$.

Find the conditional PMF for $N_1+N_2$ given that $N = n$.

Find the conditional PMF for $N$ given that $N_1 = n_1$.

Find the PMF for the number of customers entering a bus (more specifically, for any given $m$, find the PMF for the number of customers entering the $m$th bus).

Find the PMF for the number of customers entering the $m$th bus given that the interarrival interval between bus $m-1$ and bus $m$ is $x$.

Given that a bus arrives at time 10:30 pm, find the PMF for the number of customers entering the next bus.

Given that a bus arrives at time 10:30 pm and no bus arrives between 10:30 and 11 pm, find the PMF for the number of customers on the next bus.

Find the PMF for the number of customers waiting at some given time, say 2:30 pm (assume that the processes started infinitely far in the past).

Find the PMF for the number of customers getting on the next bus to arrive after 2:30 pm.

Given that I arrive to wait for a bus at 2:30 pm, find the PMF for the number of customers getting on the next bus.

Show that the arrival epochs of a Poisson process satisfy

Contrast this with the result of Theorem 2.5.1.

Let $\left\{ N_1(t); t>0\right\}$ be the counting process of the epochs at which single arrivals occur. Find the PMF of $N_1(t)$ as a function of $t$. Similarly, let $\left\{ N_2(t); t \geq 0\right\}$ be the counting process of the epochs at which double arrivals occur. Find the PMF of $N_2(t)$ as a function of $t$.

Let $\left\{ N_B(t); t \geq 0\right\}$ be the counting process of the total number of arrivals. Give an expression for the PMF of $N_B(t)$ as a function of $t$.

For a Poisson counting process of rate $\lambda$, find the joint probability density of $S_1, S_2, \ldots , S_{n-1}$ conditional on $S_n = t$.

Find $\mathbb {P}\left(X_1 > \tau \mid S_n=t\right)$.

Find $\mathbb {P}\left(X_i > \tau \mid S_n=t\right)$ for $1 \leq i \leq n$.

Find the density $f_{S_i \mid S_n}(s_i \mid t)$ for $1 \leq i \leq n-1$.

Give an explanation for the striking similarity between the condition $N(t) = n-1$ and the condition $S_n = t$.

For a Poisson process of rate $\lambda$, find $\mathbb {P}\left(N(t)=n \mid S_1=\tau \right)$ for $t > \tau$ and $n \geq 1$.

Using this, find $f_{S_1}(\tau \mid N(t)=n)$.

Check your answer against (2.41).

What is $\mathbb {P}\left(N(t)=n \mid \Lambda =\lambda \right)$, where $N(t)$ is the number of arrivals in the interval $(0, t]$ for some given $t > 0$?

Show that $\mathbb {P}\left(N(t)=n\right)$, the unconditional PMF for $N(t)$, is given by

Find $f_\Lambda (\lambda \mid N(t)=n)$, the density of $\lambda$ conditional on $N(t)=n$.

Find $\mathbb {E}\left[\Lambda \mid N(t)=n\right]$ and interpret your result for very small $t$ with $n = 0$ and for very large $t$ with $n$ large.

Find $\mathbb {E}\left[\Lambda \mid N(t)=n, S_1, S_2, \ldots , S_n\right]$. Find $\mathbb {E}\left[\Lambda \mid N(t)=n, N(\tau )=m\right]$ for some $\tau < t$.

Use Equation (2.42) -- $f_{S_i \mid N(t)}(s_i \mid n) = \frac{s_i^{i-1}}{(i-1)!} \frac{(t-s_i)^{n-i}}{(n-i)!} \frac{n!}{t^n}$ for $n \geq i$ -- to find $\mathbb {E}\left[S_i \mid N(t)=n\right]$.

Find the second moment and the variance of $S_i$ conditional on $N(t)=n$.

Assume that $n$ is odd, and consider $i = (n+1)/2$. What is the relationship between $S_i$, conditional on $N(t)=n$, and the sample median of $n$ IID uniform rv's.

Give a weak law of large numbers (WLLN) for the above median.

Let $N(\tau )$ be the number of customers in the system at time $\tau$. Find the mean, $m(\tau )$, of $N(\tau )$ and find $\mathbb {P}\left(N(\tau ) = n\right)$.

Let $D(\tau )$ be the number of customers that have departed from the system by time $\tau$. Find the mean, $\mathbb {E}\left[D(\tau )\right]$, and find $\mathbb {P}\left(D(\tau ) = d\right)$.

Find $\mathbb {P}\left(N(\tau ) = n, D(\tau ) = d\right)$.

Let $A(\tau )$ be the total number of arrivals up to time $\tau$. Find $\mathbb {P}\left(N(\tau ) = n \mid A(\tau ) = a\right)$.

Find $\mathbb {P}\left(D(\tau +\epsilon )-D(\tau ) = d\right)$.

Conditional on 1000 voters arriving during the first 10 hours of voting, find the probability that candidate $A$ receives $n$ of those votes.

Again conditional on 1000 voters during the first 10 hours, find the probability that candidate $A$ receives $n$ votes in the first 4 hours of voting.

Let $T$ be the epoch of the arrival of the first voter voting for candidate $A$. Find the density of $T$.

Find the PMF of the number of voters for candidate $B$ who arrive before the first voter for $A$.

Define the $n$th voter as a reversal if the $n$th voter votes for a different candidate than the $(n-1)$th. For example, in the sequence of votes $AABAABB$, the third, fourth, and sixth voters are reversals; the third and sixth are $A$ to $B$ reversals and the fourth is a $B$ to $A$ reversal. Let $N(t)$ be the number of reversals up to time $t$ ($t$ in hours). Is $\left\{ N(t); t > 0\right\}$ a Poisson process? Explain.

Find the expected time (in hours) between reversals.

Find the probability density of the time between reversals.

Find the density of the time from one $A$ to $B$ reversal to the next $A$ to $B$ reversal.

Find the PMF for the number of arrivals of the first process, $\left\{ N_1(t); t > 0\right\}$, during the $n$th period when the switch is on.

Given that the first arrival for the second process occurs at epoch $\tau$, find the conditional PMF for the number of arrivals of the first process up to $\tau$.

Given that the number of arrivals of the first process, up to the first arrival for the second process, is $n$, find the density for the epoch of the first arrival from the second process.

Find the density of the interarrival time for $\left\{ N_A(t); t \geq 0\right\}$.

Find the distribution of time, from the beginning of the match, until the completion of the first game that is won (i.e., that is not a draw). Characterize the process of the number $\left\{ N(t); t > 0\right\}$ of games won up to and including time $t$. Characterize the process of the number $\left\{ N_F(t); t \geq 0\right\}$ of games won by Fisher and the number $\left\{ N_S(t); t \geq 0\right\}$ won by Spassky.

For the remainder of the problem, assume that the probability of a draw is zero, i.e., that $p+q = 1$. How many of the first $2n-1$ games must be won by Fisher in order to win the match?

What is the probability that Fisher wins the match? Your answer should not involve any integrals.

Let $T$ be the epoch at which the match is completed (i.e., either Fisher or Spassky wins). Find the CDF of $T$.

Find the probability that Fisher wins and that $T$ lies in the interval $(t, t+\delta )$ for arbitrarily small $\delta$.

For $1 \leq i < n$, find the conditional density of $S_{i+1}$, conditional on $N(t) = n$ and $S_i = s_i$.

Use (a) to find the joint density of $S_1, \ldots , S_n$ conditional on $N(t) = n$. Verify that your answer agrees with (2.38).

$\mathbb {P}\left(X > t\right) = \mathrm{exp}\left(-\lambda \pi t^2\right)$;

$\mathbb {E}\left[X\right] = 1/(2\sqrt{\lambda })$.

Consider $S_n$, the time of the $n$th arrival, for $n = 10^{12}$. With high probability, $S_n$ will lie within three standard deviations of its mean. Find and compare this mean and the $3\sigma$ range.

Let $V_n$ be the total amount of time during which the server is busy with these $n$ arrivals (i.e., the sum of $10^{12}$ service times). Find the mean and $3\sigma$ range of $V_n$.

Find the mean and $3\sigma$ range of $I_n$, the total amount of time the server is idle up until $S_n$ (take $I_n$ as $S_n-V_n$, thus ignoring any service time after $S_n$).

An idle period starts when the server completes a service and there are no waiting arrivals; it ends on the next arrival. Find the mean and variance of an idle period. Are successive idle periods IID?

Combine (c) and (d) to estimate the total number of idle periods up to time $S_n$. Use this to estimate the total number of busy periods.

Combine (e) and (b) to estimate the expected length of a busy period.

Let the CDF of the $i$th interarrival interval for an arrival process be $F_{X_i}(x_i) = 1-\mathrm{exp}\left(-\alpha^{-i} x_i\right)$ for some fixed $\alpha \in (0,1)$. Let $S_n = X_1+\cdots +X_n$ and show that

Sketch a `reasonable' sample path for $N(t)$.

Use the Markov inequality on $\mathbb {P}\left(S_n \geq t\right)$ to find an upper bound on $\mathbb {P}\left(N(t) < n\right)$ that is smaller than 1 for all $n$ and for large enough $t$. Use this to show that $N(t)$ is defective for large enough $t$.

(For those looking for a challenge) Show that $N(t)$ is defective for all $t > 0$.