Some sort of geometric distribution with no replacement.

May 2010
3
0
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 a moderator:
May 2010
1,034
272
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?
 
May 2010
3
0
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.
 
May 2010
1,034
272
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 :D


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
 

awkward

MHF Hall of Honor
Mar 2008
934
409
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 \(\displaystyle X_n\) be the number of loops formed, so we want to find \(\displaystyle E(X_n)\), in particular \(\displaystyle E(X_{237})\).

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

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

\(\displaystyle 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 \(\displaystyle E(X_n)\) for any value of n.