# Average number of attempts

1. Aug 8, 2004

### mu

Hi everyboby

I need something very simple for a personnal project, but I'm not quite sure I got it right. Here it is:

Suppose there are 5 boxes side-to-side. One of them contains an object (the probablity is equal for all boxes, 1-in-5). On average, how many attempts does it take to find the object?

Here is what I figured:

if the object is in box 1, you need 1 attempt;
if the object is in box 2, you need 2 attemps;
etc.

After finding the object, you 'randomize' the system and try to find the object again. After doing this 5 times, the object will have been in each of the boxes 1 time (let's say that the system is REALLY random, or that we did a great number of tests). We will then have made 1, 2, 3, 4 and 5 attempts (not necessarily in that order) out of 5 tests. So, on average, we have made
$$\frac{{\left( {1 + 2 + 3 + 4 + 5} \right)}}{5} = 3$$
attempts.

Generalizing to N boxes, we have
$$\left\langle n \right\rangle = \frac{1}{N}\sum\limits_{i = 1}^N i = \frac{{N + 1}}{2}$$

So... is this right or am I wrong somewhere? It seems suspiciously simple. Anyway, thanks alot for your help (and sorry about my english...)

2. Aug 8, 2004

### Gokul43201

Staff Emeritus
Looks okay to me. I may have reasoned slightly differently though :

Assume you are going to pick in the order 1, 2, 3, ....
The probablity that the object is in any particular box is 1/N.

$$\left\langle n \right\rangle = \sum\limits_{i=1}^N{p_i~n_i} = \frac{1}{N} \frac{{N(N + 1)}}{2}$$

Last edited: Aug 8, 2004
3. Aug 11, 2004

### mu

I appreciate the insight you provided with your alternative approach. It seems so evident now...

Thanks again

4. Aug 18, 2004

### mu

Well, it's quiet in here :zzz:

Not that anybody cares, but I pursued my little quest and found an equation for a more general problem. I don't know why I'm posting this... just sharing, I guess.

Suppose you have k objects in N boxes. On average, how many picks (n) will you need to find an object? Here's what I found:

$$\left\langle n \right\rangle = \frac{{\sum\limits_{i = 1}^N {i \cdot \left( \begin{array}{l} N - i \\ k - 1 \\ \end{array} \right)} }}{{\left( \begin{array}{l} N \\ k \\ \end{array} \right)}} = \frac{{N + 1}}{{k + 1}}$$

Thanks to my good friend Maple for the simplification of the messy factorials.