Average number of attempts

[mu]

Hi everyboby :smile:

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 :smile: (and sorry about my english...)

[Gokul43201]

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}

[mu]

Thanks for your quick reply :smile:

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

Thanks again

[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.