Poisson mixture process independence used to devastating effect on the Coupon collectors problem

Question

Proposition 5.2 of the book, Introduction to probability models by Sheldon Ross says that if we have a Poisson process and each event in the process is of type-1 with probability $p$ and type-2 with probability $1-p$, then the number of type-1 and type-2 events are independent Poisson processes with rates $\lambda p$ and $\lambda (1-p)$ respectively. The independence is key here. It is then used as a powerful tool in example 5.17, where Ross addresses the coupon collectors problem. Quoting:

There are $m$ different types of coupons. Each time a person collects a coupon it is, independently of ones previously obtained, a type $j$ coupon with probability $p_j$, $\sum\limits_{j} p_j = 1$. Let $N$ denote the number of coupons one needs to collect in order to have a complete collection of at least one of each type. Find $E[N]$.

In the solution, he starts with the straightforward approach, denoting by $N_j$ the number of coupons that must be collected to obtain a type $j$ coupon. We can then express $N$ as:

$$N = \max_{1\leq j \leq m} N_j \tag{1}$$

He notes that the $N_j$ are geometric, but this method runs into a wall when we realize that the $N_j$'s aren't independent. And this makes sense. If there were only two types of coupons, they would be competing each time we collected a coupon. So, if we need very few coupons to collect one for the first kind, it tells us it's a common coupon and so, we now know that we'll have to wait a long time to see the second coupon (meaning $N_1$ and $N_2$ are negatively correlated).

Now, Ross considers the coupons arriving according to a Poisson process with rate $1$. By proposition 5.2, the counting processes defining the arrivals of each of the coupon types (say $j$) are independent Poisson process with rates $1 . p_j$. Now, define $X$ the time at which all coupons are collected and $X_j$ the time at which the first type $j$ coupon is collected. We get an equation very similar to (1):

$$X = \max_{1\leq j \leq m} X_j \tag{2}$$

Now, we don't run into the wall since by proposition 5.2, the $X_j$'s are independent. However, I haven't been convinced by the arguments presented for this. Why does the reasoning we used to conclude that the $N_j$'s are negatively correlated not apply to the $X_j$'s as well?

Answer 1

The fact that $X_j$'s are independent follows directly from the fact that a Poisson process can split into one with rate $\lambda p$ and one with rate $\lambda (1-p)$ (but of course here it splits into $N$ such processes, not just $2$ such processes). So that's the "math" explanation.

If you would like a more "intuitive" explanation, esp. on why the $X_j$'s behave differently from the $N_j$'s, try this hand-wavy one. Imagine $N=2$, and you get $1$ coupon, then it is either type $1$ or $2$, and they are mutually exclusive (or "negatively correlate"). But if you wait $1$ unit of time in the Poisson formulation, you can get any number of coupons of either type. Crucially, the fact that you get one (or more) coupon of type $1$ does not affect the prob of you getting one (or more) coupon of type $2$ in that same unit of time - that is the magic of splitting Poisson processes. E.g. imagine you get a type-$1$ coupon in at time $t=0.6$, that does not change the prob that you get a type-$2$ coupon in the time interval $(0.6,0.6+\epsilon]$ for any $\epsilon$.

Allow me to vaguely define $A_i$ as the event "getting a coupon of type $i$" (under some to-be-specified circumstances), then:

• Conditioned on you getting $1$ coupon (total), then $A_1, A_2$ are mutually exclusive.

• In fact, for any $n \in \mathbb{N}, T \in \mathbb{R}$, conditioned on you waiting $T$ time and getting $n$ coupons (total), then $A_1, A_2$ are dependent ("negatively correlated").

• But, conditioned on you waiting $1$ unit of time (and no further conditioning on how many total coupons you got during that time), then $A_1, A_2$ are independent - and this is a non-trivial fact based on splitting Poisson processes.

Am I helping or am I just being repetitive? :)

Answer 2

I don't yet have an intuition for why your reasoning about the $N_j$s doesn't apply also to the $X_j$s, Rohit. In particular I haven't yet managed to properly grasp antkam's nice answer.

However, I have had a go at working out some details of Ross's proof of his Proposition 5.2 (via his hints, in so far as I understand them), which I'll share here in the hope that they might be useful, albeit that what I've written is rather clunky and possibly incorrect !

With all notation as in Ross's Proposition 5.2, suppose that $0<s<t$ and $k \in \{0, 1, 2, \ldots\}$. Then \begin{align*} P\{N_1(t)-N_1(s)=k\} &= \sum_{j \geq k} P\{N_1(t)-N_1(s)=k, N(t)-N(s)=j\} \\ &= \sum_{j \geq k} P\{N_1(t)-N_1(s)=k \, | \, N(t)-N(s)=j\} P\{N(t)-N(s)=j\} \\ &= \sum_{j \geq k} \binom{j}{k} p^k (1-p)^{j-k} P\{N(t-s)=j\}, \tag{1} \end{align*} which, given $\lambda$, $p$ and $k$, depends only on $t-s$, showing that $N_1$ has stationary increments.

Question: Can a counting process have stationary increments, without having independent increments ?

In any case, let's also try to show that $N_1$ has independent increments: Suppose $0<s<t \leq s'<t'$, and $k,k' \in \{0, 1, 2, \ldots \}$. Then \begin{align*} P\{N_1(t)-N_1(s)=k, N_1(t')-N_1(s')=k'\} &= \sum_{j \geq k, j' \geq k'} P\{N_1(t)-N_1(s)=k, N_1(t')-N_1(s')=k', N(t)-N(s)=j, N(t')-N(s')=j' \} \\ &= \sum_{j \geq k, j' \geq k'} P\{(N_1(t)-N_1(s)=k, N_1(t')-N_1(s')=k') \, | \, (N(t)-N(s)=j, N(t')-N(s')=j') \} P\{N(t)-N(s)=j, N(t')-N(s')=j'\} \\ &= \sum_{j \geq k, j' \geq k'} \binom{j}{k} \binom{j'}{k'} p^{k+k'} (1-p)^{j-k+j'-k'} P\{N(t)-N(s)=j\} P\{N(t')-N(s')=j'\} \\ &= \sum_{j \geq k, j' \geq k'} \binom{j}{k} \binom{j'}{k'} p^{k+k'} (1-p)^{j-k+j'-k'} P\{N(t-s)=j\} P\{N(t'-s')=j'\} \\ &= P\{N_1(t)-N_1(s)=k\} P\{N_1(t')-N_1(s')=k'\}, \end{align*} by (1). This shows that $N_1$ has independent increments.

Continuing to the 3rd bullet point of Ross's proof of his Proposition 5.2, in the second equation, he uses the fact that \begin{align*} P\{N_1(h)=1 \, | \, N(h) \geq 2 \} P\{N(h) \geq 2 \} = o(h). \end{align*} We know, from Definition 5.3 part (iv), that $P\{N(h) \geq 2 \} = o(h)$. I was worried about the other factor, so I tried to control it, as follows:

I believe that \begin{align*} P\{N_1(h)=1 \, | \, N(h) \geq 2\} &= P\{N_1(h)=1, N(h) \geq 2\}/P\{N(h) \geq 2 \} \\ &= \left (\sum_{k \geq 2} P\{N_1(h)=1, N(h)=k\} \right ) / P\{N(h) \geq 2\} \\ &= \left (\sum_{k \geq 2} P\{N_1(h)=1 \, | \, N(h)=k\} P\{N(h)=k\} \right ) / P\{N(h) \geq 2\} \\ &= \left (\sum_{k \geq 2} \binom{k}{1} p^1 (1-p)^{k-1} e^{- \lambda h} (\lambda h)^k/k! \right ) / (1 - (P\{N(h)=0\} + P\{N(h)=1\})) \\ &= \left (p e^{-\lambda h} \sum_{k \geq 2} k (1-p)^{k-1} (\lambda h)^k/k! \right ) / (1 - (e^{-\lambda h} + \lambda h e^{-\lambda h})) \\ &= (p(1 - \lambda h + o(h))o(h) / (1 - \lambda h + o(h) + \lambda h (1 - \lambda h + o(h))) \\ &= o(h) / (1 + o(h)) \\ &= o(h), \end{align*} therefore \begin{equation*} P \{N_1(h)=1 \, | \, N(h) \geq 2 \} P \{N(h)\geq 2\} = o(h)o(h) = o(h), \end{equation*} as required. Finally, regarding the claim in Proposition 5.2 that the two processes $\{N_1(t), t \geq 0 \}$ and $\{N_2(t), t \geq 0 \}$ are independent, I (rightly or wrongly) take this to mean that for all $t \geq 0$, the random variables $N_1(t)$ and $N_2(t)$ are independent. I don't follow the first sentence of Ross's explanation

Because the probability of a type I event in the interval from $t$ to $t + h$ is independent of all that occurs in intervals that do not overlap $(t, t + h)$, it is independent of knowledge of when type II events occur, showing that the two Poisson processes are independent. (For another way of proving independence, see Example 3.23.) ,

but I believe I do understand the alternate one given in Example 3.23.