4
$\begingroup$

I found an interesting problem (not homework) that I can't solve. Lake has 4 types of fishes (A, B, C, D) each with given probability to be caught (0.1, 0.2, 0.3, 0.4). We fish until we catch at least one of each type. What's the distribution on number of fishes we will catch? I know p(x=4) = 4!*0.1*0.2*0.3*0.4, and I can get p(x=5) as choose(5,4)*p(x=4)/2, but I don't know how to generalize it further. Thanks

$\endgroup$
1
  • 3
    $\begingroup$ You can solve this purely mechanically using Markov Chains. I show an explicit solution to a similar problem at stats.stackexchange.com/a/202393 . In this cases there are more elegant approaches, such as counting paths. $\endgroup$
    – whuber
    Mar 23, 2016 at 15:06

1 Answer 1

2
$\begingroup$

Let there be $m$ types of fishes with probabilities $p_i,\ i=1,2,\ldots, m$ (which therefore sum to unity) and let $k_i$ be the number of fish of type $i$ you have caught. It won't change the answer to suppose you keep fishing even after at least one of each is caught, so for any $n \ge 0$ let $F(n, \mathbf{p})$ designate the chance that you have at least one of each kind of fish in your creel after catching $n$ total: it is the distribution function you seek.

The Principle of Inclusion-Exclusion , or PIE, asserts that this chance can be expressed as an alternating sum, starting with $1$. From this you subtract the chance of not catching any fish of type $1$, the chance of not catching any fish of type $2$, and so on. Those chances are easy to compute when we assume that what kind of fish you catch with each cast of your line is independent of what kinds were caught previously. (This is only approximately true, but the approximation is good when there are large numbers of fish in the lake; and improving the approximation requires knowing how many of each type reside in the lake.) Independence implies the per-catch chances multiply, immediately giving $(p_2+p_3+\cdots + p_m)^n$ as the chance of not catching a fish of type $1$, etc.

These subtractions aren't quite right, because (say) the chance computed for not catching a fish of type $1$ and the chance computed for not catching a fish of type $2$ both account for not catching either type of fish: too much has been subtracted. Thus we must add back all the chances of not catching two specific types of fish. These chances are computed as $(p_3+p_4+\cdots + p_m)^n$, where the two indexes omitted from the sum ($1$ and $2$ in this example) designate the two types of fish.

This process of alternately adding and subtracting to correct earlier values has to be repeated as far as possible: that's the PIE. We may write a formula by adopting a convenient notation: for any subset $\mathcal{A}\subseteq \{1,2,\ldots, m\}$, let

$$p_{\mathcal{A}} = \sum_{i\in\mathcal{A}} p_i$$

be the sum of the probabilities associated with all the indexes in $\mathcal{A}$. Let us further use$|\mathcal{A}|$ to designate the number of indexes in $\mathcal{A}$. Then, for $m\ge 1$,

$$F(n, \mathbf{p}) = \sum_{k=1}^m \sum_{\mathcal{A}:\,|\mathcal{A}|=k} (-1)^{m-k}p_{\mathcal{A}}^n.$$

(Clearly $F(0, \mathbf{p})=0$.)

Lest this seem too abstract, let's look at a smaller example with just three types of fish, so that $m=3$. Then

$$\eqalign{ &F(n, (p_1,p_2,p_3)) =\\ &(p_1^n + p_2^n + p_3^n) - ((p_1+p_2)^n + (p_1+p_3)^n + (p_2+p_3)^n) + (p_1+p_2+p_3)^n }$$

(although of course $p_1+p_2+p_3=1$ can be simplified).

This isn't a great formula, because it has $2^m-1$ terms, growing exponentially with the number of distinct fish being considered. However, unless the $p_i$ exhibit some kind of regularity--such as all being equal--this formula will not simplify appreciably.

Figure: plot of F

This figure shows the graph of $F(n, (0.1,0.2,0.3,0.4))$.

The expectation of the total fish count is often of interest. This can be computed by summing the survival function,

$$\mathbb{E}_F = \sum_{n=0}^\infty (1-F(n)).$$

It breaks into collection of geometric series, easily summed, giving

$$\mathbb{E}_F = \sum_{k=1}^m \sum_{\mathcal{A}:\,|\mathcal{A}|=k} (-1)^{m-k}\frac{1}{1-p_{\mathcal{A}}}.$$

For the data in the question, this gives $445/36\approx 12.36$. As a check, when all $m$ of the $p_i$ are equal, this formula gives

$$\mathbb{E}_F = m\sum_{k=1}^m (-1)^{k-1} \binom{m}{k} \frac{1}{k} = m(1+1/2+1/3+\cdots+1/m),$$

the solution for the traditional Coupon Collector's problem.

Finally, we may double-check this result with a simulation. The following R code catches up to 90 fish at a time, repeating this 100,000 times. (In only seven cases were one or more types of fish not caught.) The output includes the empirical version of $F$, the histogram, and the average number of fish caught. It reports an average of $12.36$ in this particular run of the simulation, agreeing with the computed value to all four digits. The partial plot of $F$ on the figure's left is remarkably close to the theoretical plot in the first figure.

Figure 2: Distribution function and histogram

set.seed(17)
n.sim <- 1e5
p <- 1:4
p <- p/sum(p)  # Chances for each fish
m <- length(p) # Number of types of fish
N <- 90        # Number of fish to catch in each iteration

# Catch fish.
x <- matrix(sample.int(m, n.sim*N, replace=TRUE, prob=p), nrow=N)

# Determine the first index at which all types of fish have appeared.
sim <- apply(sapply(1:m, function(i) apply(rbind(x==i,1), 2, which.max)), 1, max)
#
# Plot the results.
#
par(mfrow=c(1,2))
plot(1:(30), cumsum(tabulate(sim))[1:30]/n.sim, ylim=c(0,1),
     xlab="n", ylab="F", pch=16, col="#7180C4", cex=0.6)

hist(sim[sim <= 50], breaks=0:51, main="Histogram", xlab="n", ylab="Probability",
     freq=FALSE, col="#7180C4", border="#00000000")
#
# Estimate the mean.
# (To be accurate, it is important that few values in `y` equal `N`: those
# indicate cases where not all types of fish were caught.)
#
y <- tabulate(sim)
tail(y)             # Check that the last value is tiny.
sum(y * 1:length(y)) / sum(y)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.