Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Average number of attempts

  1. Aug 8, 2004 #1

    mu

    User Avatar

    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
    [tex]
    \frac{{\left( {1 + 2 + 3 + 4 + 5} \right)}}{5} = 3
    [/tex]
    attempts.

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


    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...)
     
  2. jcsd
  3. Aug 8, 2004 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.

    [tex] \left\langle n \right\rangle = \sum\limits_{i=1}^N{p_i~n_i} = \frac{1}{N} \frac{{N(N + 1)}}{2} [/tex]
     
    Last edited: Aug 8, 2004
  4. Aug 11, 2004 #3

    mu

    User Avatar

    Thanks for your quick reply :smile:

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

    Thanks again
     
  5. Aug 18, 2004 #4

    mu

    User Avatar

    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:

    [tex]
    \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}}
    [/tex]

    Thanks to my good friend Maple for the simplification of the messy factorials.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?