# A Question on Probability - Hunter and Rabbit

Suppose there are m different hunters and n different rabbits. Each hunter selects a rabbit uniformly at random independently as a target. Suppose all the hunters shoot at their chosen targets at the same time and every hunter hits his target.

(i) Consider a particular Rabbit $$1$$, what is the probability that Rabbit $$1$$ survives?

(ii) Suppose $$m=7$$, $$n=5$$. What is the probability that no rabbit survives?

Attempt for (i):

Consider 1st hunter, No. of rabbits he can choose is $$n-1$$, since Rabbit $$1$$ survives. Consider 2nd hunter, No. of rabbits he can choose is $$n-1$$, since Rabbit $$1$$ survives. .... So, for $$m$$ hunters, number of ways they choose rabbits such that they won't choose Rabbit 1 $$= (n-1)^m$$ And number of ways ways they choose rabbits = $$n^m$$

$$P(\text{Rabbit 1 survives)} = \frac{ (n-1)^m }{n^m} = \left[ \frac{(n-1)}{n} \right]^m$$

For (2), you can try Inclusion-Exclusion, using the fact (generalizing (i)) that the probability that a particular set of $k$ rabbits survives is $((n-k)/n)^m$.

EDIT: Here's the Inclusion-Exclusion calculation:

\eqalign{ P(0\text{ survive}) &= 1 - P(\ge 1\text{ survive}) \cr &= 1 - {5 \choose 1} (4/5)^7 + {5 \choose 2} (3/5)^7 - {5 \choose 3} (2/5)^7 + {5 \choose 4} (1/5)^7\cr &= \frac{672}{3125}}

(which is the same as $16800/78125$). In general with $m$ hunters and $n$ rabbits the probability that none survive is $$1 + \sum_{k=1}^{n-1} (-1)^k {n \choose k} \left(\dfrac{n-k}{n}\right)^m$$

• Is P(1 rabbit survives) = [(5-1)/5]^7 * C(5,1) ? Dec 17, 2013 at 11:43
• This works out for all rabbits surviving, since $k=n$, the probability is $0$, which is correct (every hunter has to pick a rabbit, so the best case for the rabbits is one very unlucky rabbit getting shot by all hunters). This also works out for $k=1$, since that becomes case (i), if that is correct. But this puts the probability of no rabbit surviving at $1$, since $k=0$ and so $$\left[ \frac{(n-k)}{n} \right]^m = \left[ \frac{n}{n} \right]^m = 1$$
– SQB
Dec 17, 2013 at 11:45
• When getting ((n-1)/n)^m, we specify the rabbit Rabbit 1. So, I thought if we need to find P(1 rabbit survives), P(1 rabbit survives) = ((n-1)/n)^m * C(n,1) Dec 17, 2013 at 12:28
• Inclusion-exclusion again. Probability that at least $k$ survive = ${n \choose k} \cdot$ probability of a given $k$-tuple surviving $- {n \choose {k+1}} \cdot$ probability of a given $k+1$-tuple surviving $+ \ldots$. Dec 17, 2013 at 13:31
• For 7 hunters and 5 rabbits, there are 78125 ways for the hunters to choose a rabbit ($5^7$). Of those, 16800 have all rabbits killed.
– SQB
Dec 17, 2013 at 14:51

For part 2 , i followed this approach. I think it is correct or else please write your comment.
for all rabbits to die, each should be hit by atleast one hunter.

so selecting n hunters among m maintaining the order - mpn
and the remaining m-n hunters can shoot any one. so n(m-n)

so total number of chances -> mpn * n(m-n)

so , the probability is ((mpn * n(m-n)) / nm)

I found out how to arrive at the numbers I got from my simulation, so I'll try my hand at answering.

First, my simulation. As I think we've killed enough rabbits by now, I'll try to make the world a better place by giving icecream to children.
We've got 7 children: Alice, Bob, Carol, Dave, Eve, Frank, and Gabrielle.
The icecream parlor has only 5 flavours. You can come up with any flavours you like, but we'll just number them 1 through 5.
The kids get one scoop each. These kids like to share, and they'd like to try each flavour. So if they can make sure that they have picked each flavour at least once among the seven of them, they all can taste every flavour by sharing.

The question now becomes, what is the probability of the 7 children having picked all 5 flavours between them (if they don't know what the others picked, of course).

Now here's my simulation of that in SQL (Oracle 11g).

CREATE OR REPLACE TYPE nums AS TABLE OF NUMBER;
/

WITH
icecream AS (
SELECT LEVEL AS flavour
FROM dual
CONNECT BY LEVEL <= :v_nr_of_flavours
),
children AS (
SELECT
a.flavour AS alice,
b.flavour AS bob,
c.flavour AS carol,
d.flavour AS dave,
e.flavour AS eve,
f.flavour AS frank,
g.flavour AS gabrielle,
CARDINALITY(
nums(
a.flavour,
b.flavour,
c.flavour,
d.flavour,
e.flavour,
f.flavour,
g.flavour
)
MULTISET UNION DISTINCT
nums()
) AS nr_of_flavours_picked
FROM icecream g
CROSS JOIN icecream f
CROSS JOIN icecream e
CROSS JOIN icecream d
CROSS JOIN icecream c
CROSS JOIN icecream b
CROSS JOIN icecream a
)
SELECT
COUNT(*) AS nr_of_combinations,
nr_of_flavours_picked,
CASE
WHEN GROUPING(nr_of_flavours_picked) = 1
THEN NULL
ELSE DECODE(nr_of_flavours_picked, :v_nr_of_flavours, 1, 0)
END AS all_flavours_picked
FROM children
GROUP BY ROLLUP (nr_of_flavours_picked);


This gives us a value of 78125 total possibilities of which 16800 have all rabbits killed all flavours picked.

But where do those numbers come from?

The number of total possibilities is easy, that's ($5^7$). But the other number is a bit more involved.

As it turns out, there are two ways to have 7 children pick all 5 flavours. Either two flavours are picked twice, or one flavour is picked thrice.

That last case is the easiest, as that is just $7 \cdot 6 \cdot 5 \cdot 4$ (the first four kids pick a flavour that hasn't been picked yet, the last three kids pick the one flavour left). Of course there are ${5 \choose 1} = 5$ flavours that can be picked thrice, so we get $7 \cdot 6 \cdot 5 \cdot 4 \cdot 5$ possibilities.

The first case is a little bit harder, but not much. Here we have $7 \cdot 6 \cdot 5 \cdot 6$ (the first three kids pick a flavour that hasn't been picked yet, after which there are 6 ways to distribute the remaining two pairs of flavours among the remaining four kids). Here we have ${5 \choose 2} = 10$ ways of deciding which two flavours get picked twice, so the total number here is $7 \cdot 6 \cdot 5 \cdot 6 \cdot 10$.

The total of these two cases is $7 \cdot 6 \cdot 5 \cdot 4 \cdot {5 \choose 1} + 7 \cdot 6 \cdot 5 \cdot 6 \cdot {5 \choose 2} = 7 \cdot 6 \cdot 5 \cdot (4 \cdot 5 + 6 \cdot 10) = 210 \cdot 80 = 16800$ which is indeed the number we got from our simulation.

So the probability of the children having picked all flavours is $\frac{16800}{78125}$.

Here are the results for 7 children with different numbers of flavours. $$\begin{array}{rrr} \begin{array}{c}\text{Nr. of flavours}\end{array} & \begin{array}{c}\text{Nr. of combinations} \\ \text{with all flavours chosen}\end{array} & \begin{array}{c}\text{Nr. of possible combinations}\end{array} \\ \hline 1 & 1 & 1 \\ 2 & 126 & 128 \\ 3 & 1806 & 2187 \\ 4 & 8400 & 16384 \\ 5 & 16800 & 78125 \\ 6 & 15120 & 279936 \\ 7 & 5040 & 823543 \\ \end{array}$$ The general question remains to find a formula for different $m$ (hunters or children) and $n$ (rabbits or icecream flavours). I can explain all the numbers in the table above, but so far I haven't been able to formulate the general formula.