Results 1 to 5 of 5

Math Help - Some sort of geometric distribution with no replacement.

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    3

    Some sort of geometric distribution with no replacement.

    Can any one help with the following problem please:

    There are 237 snake in a pit, a head and a tail are chosen at random and the head made to bite the tail. If the head and tail belong to the same snake you achieve a loop if they are from differing snakes both are discarded. Repeat the process until no more snakes remain.

    What is the expected number of loops?

    Basically the expected number of attempts where a head and tail is picked belonging to the same snake, bearing in mind that a failure means 2 snakes are discarded!

    so basically this is as far as i could get:

    the probability of a loop on the nth attempt provided you have had z previous succeses (loops achieved) is= 1/(237 - 2(n-1) + z)

    Thank you
    Last edited by mr fantastic; May 31st 2010 at 01:20 PM. Reason: Edited title.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    If i read your question right, you have an odd number of snakes in your pit, and you can only discard them 2 at a time.

    So You will never discard them all (after some amount of time you will end up with 1 snake, and then get loops forever).

    E(loops) = infinite (which happens with probability 1)


    Did you mean to say you also discard the 1 snake if you get a loop?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    3
    Yes sorry for the poorly written question, you are correct snakes that loop are also discarded.

    Let me try and describe it again, hopefully more simply this time:
    -You have a pit of 273 snakes
    -You pick 1 snake head and 1 snake tail at random
    -If you happen to pick the head and tail belonging to the same snake, effectively a successful trial, then this snake forms a loop and is discarded
    -If you happen to pick a tail and a head from separate snakes then this is effectively a failed trial, no loops are achieved and both snakes are discarded.
    Repeat the trials until no snakes are left. What is the expected number of loops/successes.

    As a result of their bieng an odd number of snakes then:
    Pr[You make at least 1 loop]=1

    hopefully this helps.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    May 2010
    Posts
    1,028
    Thanks
    28
    i cant see an algebraic solution to this problem using pre-university level stats. You do know that the number of loops is at least 1, at most 273, and must be an odd number. That gives you about 140 possible values of L, you could use a computer to find the probability of each and get the expected value from that.....but i doubt thats what your teacher had in mind


    If you have studied markov Jump processes you could do this as one of those, but that is not a pre-univeristy topic and it would be very messy. Sorry i cant help more, maybe someone else has a better idea
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by zh305 View Post
    Can any one help with the following problem please:

    There are 237 snake in a pit, a head and a tail are chosen at random and the head made to bite the tail. If the head and tail belong to the same snake you achieve a loop if they are from differing snakes both are discarded. Repeat the process until no more snakes remain.

    What is the expected number of loops?

    Basically the expected number of attempts where a head and tail is picked belonging to the same snake, bearing in mind that a failure means 2 snakes are discarded!

    so basically this is as far as i could get:

    the probability of a loop on the nth attempt provided you have had z previous succeses (loops achieved) is= 1/(237 - 2(n-1) + z)

    Thank you
    Here is a recursive approach which will give you the answer, but only after a lot of computation.

    More generally, suppose you have n snakes in the pit. Let X_n be the number of loops formed, so we want to find E(X_n), in particular E(X_{237}).

    It's easy to see that
    [1] \quad E(X_1) = E(X_2) = 1.

    Now suppose n > 2. With probability 1/n we get a loop on the first head-tail chosen, leaving n-1 snakes in the pit with an expected value of E_{n-1} loops. With probability 1-1/n there is no match, and we leave n-2 snakes in the pit with an expected value of E(X_{n-2}) loops. So

    E(X_n) = (1/n) (1 + E(X_{n-1})) + (1-1/n) E(X_{n-2}).

    Together with [1], you can use this equation to compute E(X_n) for any value of n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: July 5th 2011, 08:13 PM
  2. Probability distribution when with replacement
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: February 18th 2010, 08:56 AM
  3. Geometric distribution
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 8th 2010, 09:24 AM
  4. Geometric (p) Distribution on (0,1,2,...)
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: November 7th 2009, 06:32 PM
  5. Replies: 2
    Last Post: October 5th 2009, 02:29 AM

Search Tags


/mathhelpforum @mathhelpforum