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

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?

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.

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

Quote:

---

Originally Posted by zh305

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 be the number of loops formed, so we want to find , in particular .

It's easy to see that
.

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

.

Together with [1], you can use this equation to compute for any value of n.