Probability Help (1 Viewer)

phamtom44

Member
Hey guys, I ran into this question today:

Catch any pokemon every 5 minutes on average, 42 different pokemon total, how long before you have caught every kind of pokemon? you can use whatever program you want, need to explain assumptions.

I was thinking of using a Poisson process/Exponential distribution but I'm stuck.

InteGrand

Well-Known Member
Hey guys, I ran into this question today:

Catch any pokemon every 5 minutes on average, 42 different pokemon total, how long before you have caught every kind of pokemon? you can use whatever program you want, need to explain assumptions.

I was thinking of using a Poisson process/Exponential distribution but I'm stuck.
$\bg_white \noindent We can find the distribution of the desired time in the following way. Let n be the total types of Pok\'emon (in your case, n = 42). I will assume Pok\'emon arrive according to a Poisson process with mean interarrival time 5 minutes and conditional on an arrival of a Pok\'emon, any of the n types of Pok\'emon are equally likely to be the one that appears, independently of the arrival process. I will also assume that when a Pok\'emon appears, it is always successfully caught and the catching takes no time.$

$\bg_white \noindent Let \lambda be the rate of arrival of Pok\'emon per minute. For your case, \lambda = \frac{1}{5}. In general, it is the inverse of the mean time between arrivals. Due to our assumptions, we have a thinned'' Poisson process: it can be shown that the arrivals of each Pok\'emon type form independent Poisson processes with rate parameter \frac{\lambda}{n} (I'll give a link to some information about thinned Poisson processes at the end for further reading). Therefore, if we let T^{(i)} be the random variable denoting the time of first arrival of the i-th type of Pok\'emon (i = 1,2,\ldots, n), the T^{(i)} are iid rate \frac{\lambda}{n} exponential random variables, with CDF F(t) = 1-e^{-\frac{\lambda}{n} t}, t \geq 0.$

$\bg_white \noindent Now, the time at which we have caught all n types of Pok\'emon is the random variable$

$\bg_white M= \max \left\{T^{(1)},\ldots ,T^{(n)}\right\}.$

$\bg_white \noindent Therefore, the support of M is [0,\infty) and the CDF of M is F_{M}(t) \equiv \mathbb{P} (M\leq t) = \left(1 -e^{-\frac{\lambda}{n} t}\right)^{n}, t \geq 0. This gives us the distribution of M.$

• Poisson thinning: http://www.math.uah.edu/stat/poisson/Splitting.html

Last edited:

InteGrand

Well-Known Member
$\bg_white \noindent Note that if X_{1},\ldots , X_{n} are iid random variables with CDF F_{X}, then you can show quite easily that the CDF of their maximum is \left(F_{X}(x)\right)^{n}. This was used near the end above.$

InteGrand

Well-Known Member
$\bg_white \noindent Alternatively, if you only care about the expected time to catch all types of Pok\'emon, you can note that \mathbb{E}[M] = \frac{n}{\lambda}\sum_{k = 1}^{n}\frac{1}{k}. One way to show this is to consider the time to arrival of a new type of Pok\'emon at each stage that you just catch a Pok\'emon type that hadn't been caught before. It is explained here:$

http://www.stat.berkeley.edu/~mlugo/stat134-f11/exponential-maximum.pdf

$\bg_white \noindent and is essentially a continuous time version of the coupon collector problem:$

https://en.wikipedia.org/wiki/Coupon_collector's_problem .

Last edited: