I have no idea how to solve a problem which goes something like this:

"In a neighborhood, 30 people live in 30 different houses. What is the expected number of houses that one must visit in order to find 6 particular people?"

I tried several approaches which gave me strange answers, although I remember one time where I miraculously got something around 23, which seems most reasonable.

Can anyone help me?

## Comments

Sort by:

TopNewestThere are \(\dbinom{30}{6}\) ways in which the \(6\) people can be "distributed" amongst the \(30\) houses with regards to any sequence we choose to take, each of which is equally likely. Now it's the house that we find the \(6\)th person in that will determine the tally of houses we've had to check. So say the last person was found in the \(24\)th house we've checked; there are \(\dbinom{23}{5}\) ways we could then have found the other \(5\) people before getting to this last house. So the expected value will be

\(\dfrac{1}{\dbinom{30}{6}} \displaystyle\sum_{k=5}^{29} (k + 1)\dbinom{k}{5} = \dfrac{186}{7} = 26.57\) to 2 decimal places.

That is, for \(5 \le k \le 29,\) if the last person found is in the \((k + 1)\)st house, then there were \(\dbinom{k}{5}\) ways in which we found the previous five people before getting to this last house, each of which was equally likely. The "weight" of each of these outcomes with respect to the expected value calculation is \((k + 1),\) resulting in the above calculation.

It's interesting to analyze the general discrete function

\(E(n,m) = \dfrac{1}{\dbinom{n}{m}} \displaystyle\sum_{k=m-1}^{n-1} (k + 1)\dbinom{k}{m-1}\)

representing the expected number of houses that need to be visited to find \(m\) people distributed amongst \(n\) houses. For \(n = 30\) and starting at \(m = 1\) we obtain the following results:

\(15.5, 20.67, 23.25, 24.8, 25.83, 26.57, 27.13, 27.56, 27.9, 28.18, .....\)

To find \(15\) people we would expect to have to visit just over \(29\) houses.

Log in to reply

The general form is \( \dfrac{m(n+1)}{m+1} \)

Log in to reply

Great! I hadn't seen that formula before. I'll have to see now how to simplify my formula for \(E(n,m)\) to obtain yours.

Log in to reply

Your summand is \( (k+1)\binom{k}{m-1} = m\binom{k+1}{m}, \) and now you can factor out the \(m \) to get \[ E(m,n) = \frac{m}{\binom{n}{m}} \sum_{k=m-1}^{n-1} \binom{k+1}{m} \] and that sum, \( \binom{m}{m} + \binom{m+1}{m} + \cdots + \binom{n}{m} \), is well-known to equal \( \binom{n+1}{m+1} \).

So \[ E(m,n) = \frac{m \binom{n+1}{m+1}}{\binom{n}{m}} = \frac{m(n+1)}{m+1} \] as desired.

Log in to reply

Log in to reply

Thanks man! :D

Log in to reply

You're welcome. :) The value of \(26.57\) was higher than I would have anticipated, but "intuition" is pretty unreliable when it come to probability and expected value questions.

Log in to reply

Log in to reply

Your question is analogous to this one

Log in to reply

Hmm.

Log in to reply