Spring 2018, Math 171

Week 9

Miscillaneous Poisson Process Problems
1. Let \(X_1, X_2, \dots\overset{\mathrm{i.i.d}}{\sim} \mathrm{exp}(\lambda)\), and let \(N(t)\) be a poisson process with rate \(\lambda\)
  1. Show the equality \(P(\sum_{i=1}^n X_i \le t) = P(N(t) \ge n)\)
  2. Find an analogous equality for \(P(s \le \sum_{i=1}^n X_i \le t)\)
    - (Answer) \(P(N(s) < n, N(t) \ge n)\)
2. \(n+m\) cars approach \(n\) toll booths \((m < n)\). The time taken for a car to pay its toll is exponentially distributed with rate \(\lambda\). When a toll booth becomes available, the next car in line fills it instantly if there are any cars waiting.
  1. What is the expected time before the first car exits the tolls?
    - (Answer) \(\frac{1}{n\lambda}\)
  2. What is the expected time before the \(m^\mathrm{th}\) car exits the tolls?
    - (Answer) \(\frac{m}{n\lambda}\)
  3. What is the expected time before the last car exits the tollbooths?
    - (Solution)
      - Let \(\tau_1, \tau_2, \dots \tau_{n+m}\) be the times between successive cars exiting any of the tollbooths.
      - Then \(\tau_1\), the time of the first car to exit any of the tolls, is the minimum of \(n\) exponential waiting times (for each of the tolls), and is therefore distributed exponential with parameter \(n\lambda\).
      - Likewise, \(\tau_2, \dots \tau_{m+1}\) are each the minimum of \(n\) exponential waiting times each (since the tolls are all occupied by cars until \(m+1\) cars have passed) and are therefore exponential with parameter \(n\lambda\).
      - After \(m+1\) cars have passed, there are more tollbooths than cars left, so there are no cars occupying some of the tollbooths. For this reason, \(\tau_{m+2}\) is distributed exponentially with parameter \((n-1)\lambda\), \(\tau_{m+3}\) is distributed exponentially with parameter \((n-2)\lambda\), and so on.
      - The quantity of interest is therefore \[\begin{aligned}\mathbb{E}[\tau_1 + \dots + \tau_{m+n}] &= \mathbb{E}[\tau_1] + \dots + \mathbb{E}[\tau_{n+m}]\\&=\frac{m+1}{n\lambda} + \frac{1}{(n-1)\lambda} + \frac{1}{(n-2)\lambda} + \dots \frac{1}{\lambda}\end{aligned}\]
  4. What is the probability that the \((n+1)\)st car to enter a toll exits before the first car to enter a toll?
    - (Answer) \(\frac{n-1}{n} \frac{1}{2}\)
Compound Poisson Process
1. Let \(X_1, X_2, \dots\) be a sequence of i.i.d. random variables with mean \(\mu\) and variance \(\sigma^2\), and let \(N(t)\) be a poisson process with rate \(\lambda\) independent of all the \(X_k\). Define \(S(t) = \sum_{k=1}^{N(t)}X_k\).
  1. Compute \(\mathbb{E}[S(t)]\)
    - (Answer) \(t \lambda \mu\)
  2. Compute \(\mathrm{Cov}(S(t_1), S(t_2))\) for \(t_1 < t_2\)
    - (Solution)\[\begin{aligned}\mathrm{Cov}(S(t_1), S(t_2)) &= \mathrm{Cov}(S(t_1), S(t_2) - S(t_1) + S(t_1))\\ &= \mathrm{Cov}(S(t_1), S(t_2) - S(t_1)) + \mathrm{Var}(S(t_1))\\&=\mathrm{Cov}(\sum_{k=1}^{N(t_1)}X_k, \sum_{k=N(t_1)+1}^{N(t_2)}X_k) + \mathrm{Var}(S(t_1))\\&=\mathrm{Var}(S(t_1))\end{aligned}\] Where the last equality comes from the independence of \(X_i\) and \(X_j\) for \(i \neq j\) and the fact that the sums \(\sum_{k=1}^{N(t_1)}X_k\) and \(\sum_{k=N(t_1)+1}^{N(t_2)}X_k\) do not overlap in indices.
  3. Compute \(\mathrm{Var}(S(t))\)
    - (Answer) \(t\lambda(\sigma^2 + \mu^2)\)
  4. Suppose the \(X_k\) have MGF \(M_X(u)\). Compute the MGF of \(S(t)\)
    - (Answer) \(e^{t\lambda(M_X(u)-1)}\)
Thinning and Superposition
1. Let \(N_1(t)\) and \(N_2(t)\) be independent poisson processes with rates \(\lambda_1\) and \(\lambda_2\). Find the probability that the \(m_1^{\mathrm{th}}\) arrival of \(N_1(t)\) occurs before the \(m_2^{\mathrm{th}}\) arrival of \(N_2(t)\).
2. Let \(N(t)\) be a poisson process with rate \(\lambda\) and let each arrival of the process be identified as either type 1 with probability \(p\) or type 2 with probability \(1-p\). Find the probability that the \(m_1^{\mathrm{th}}\) arrival of type 1 occurs before the \(m_2^{\mathrm{th}}\) arrival of type 2.
3. \(n+m\) cars approach \(n\) toll booths \((m < n)\). The time taken for a car to pass through a toll booth is exponentially distributed with rate \(\lambda\). When a toll booth becomes available, a car fills it instantly if there are any cars waiting.
  1. (Discussed) Describe the exits of first \(m\) cars from the toll booths as a superposition of poisson processes
  2. (Discussed) What is the probability that the first car comes through the leftmost tollbooth?
  3. (Discussed) What is the probability that all of the first \(m\) cars comes through the leftmost tollbooth?
  4. What is the probability that each of the first \(m\) cars go exit through a different tollbooth?
    - (Answer) \(\frac{n-1}{n}\frac{n-2}{n} \dots \frac{n-m+1}{n}\)