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

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?

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? :)

• Thanks for the answer, this certainly helps. However, what is wrong with the following argument - if $X_1$ and $X_2$ are the times until the first coupons of type 1 and 2 respectively are collected, then the value of $X_1$ does give us information about $X_2$. If $X_1$ is super low, it means we shouldn't expect a type-2 coupon for quite a long time because $p_1$ was probably high meaning necessarily that $p_2$ should be low. If observing $X_1$ is giving us information about $X_2$, then how can they be independent? Commented Nov 4, 2019 at 20:25
• It is very important that $p_1, p_2$ are fixed! We are not trying to look at the coupons and estimate $p_1, p_2$. Given constants $p_1, p_2$ (e.g. $0.3, 0.7$) in the two-coupon problem, the r.v.s $X_1$ and $X_2$ are independent - that is the magic property of splitting Poisson processes. E.g. suppose the total rate of arrival is $1$ per time-unit. Conditioned on $X_1 = 10000$, does that affect $X_2$? The answer is No. Sure $X_1 = 10000$ is a very improbable event for something with rate $p_1$, but it is what it is, and it in no way affects the distribution of $X_2$. Commented Nov 4, 2019 at 20:31
• Hmm, okay. Not 100% convinced, but I'm getting some vague intuition from your answer as to when the number of events are finite (and we condition over them), the two processes are "fighting" over them. However, when we look at it on a continuous spectrum like time, there are infinite points and so the two processes no longer have to "fight". Does this seem like a good explanation? Also, $p_1$ and $p_2$ are not necessarily $\frac 1 2$. Commented Nov 4, 2019 at 20:36
• YES. I like to think of Poisson as the limit of a Binomial process - flipping infinitely many coins each of infinitesimal chance of success. If there is only one coupon, then $A_1, A_2$ are mutually exclusive. But for whatever interval $[t, t+\epsilon]$ no matter how short, $A_1, A_2$ are independent. Consider the $p_1=p_2=1/2$ case, and lets say in this tiny interval, $Prob(A_1) = Prob(A_2) \approx \delta$ for some tiny $\delta$. Then the math will work out that $Prob(A_1 \cap A_2) \approx \delta^2$ so that $Prob(A_2 \mid A_1) = \delta$, hence independence. Commented Nov 4, 2019 at 20:42
• Personally I am not good with measure theory. I prefer to think of Poisson as the limit of $Binomial(N, {\lambda \over N})$ as $N \to \infty$ and argue informally. :) Commented Nov 4, 2019 at 20:45

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 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, 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.

• Thanks Simon. The part about the processes being independent was the most confusing. I actually didn't understand how example 3.23 (which deals with strategies for picking prizes) relates to the two Poisson processes being independent? Can you help me connect the dots there? Commented Mar 4, 2020 at 7:05
• Also, regarding your question on if a process can have stationary but not independent increments, apparently yes. If you look at mixed Poisson processes covered in section 5.4.3, he makes exactly this claim. An example is the negative binomial point process where the mixing distribution over the rate of the Poisson is Gamma and $N(t)$ is negative binomial instead of Poisson. Will be interesting to try and prove this with your methodology. Commented Mar 4, 2020 at 7:08
• I think the prize-picking example is 3.25, rather than 3.23 :) Example 3.23 starts on pg 123. Thank you for the pointer to Section 5.4.3 - reading it now ! Commented Mar 4, 2020 at 12:42
• I see. I was reading the 9th edition and that's where the confusion stemmed from. In the 9th, he refers to example 3.20 which also seems unrelated, so this might have been a typo in that edition. Commented Mar 5, 2020 at 18:59
• I understand. I'm using the 10th, which I got from the link you kindly provided. I guess they must have updated the file. In the 10th, example 3.23 is about a Yoga studio. Commented Mar 5, 2020 at 19:09