7

You have 100 string in a bag and you randomly pull out one end of a string. You randomly pull out another end and tie them together. You do this until you have no more ends.

The expected number of loops is $\sum_{i=1}^{n} \frac{1}{2n-1}$.

What is the expected number of self loops? (Strings that are tied to its own end.)

My take: The probability of having a self loop with the first string is 1/199. By linearity of expectation, each string has 1/199 chance of forming a self loop, so the expected number of self loops is $100/199$.

Is this correct? Seems like a low number but then again you have many strings and it's unlikely to pull out your own end.

narcissa
  • 771
  • The probability of a string forming a self-loop changes, so I'm not sure you can do that. – Zach L. Aug 10 '13 at 23:00
  • Yeah, you want to compute the probability that a fixed strand in the bag stays by itself, not specializing to the first string picked. – Evan Aug 10 '13 at 23:31
  • This problem can be thought of as a way of generating a random permutation via cycle notation, labeling all the strands in the bag from 1 to 100. The problem boils down to a counting problem. I think the answer is 1. – Evan Aug 10 '13 at 23:34
  • Oops, what I said is not quite right. – Evan Aug 10 '13 at 23:47

2 Answers2

2

Ok, I think you are right now.

Identify procedure by labeling each string end from 1 to 200. Let's say (1,2) identifies string 1, (3,4) identifies string 2, etc, (2k-1,2k) identifies string k.

We can think of this procedure as generating a permutation over 200 elements, and pairing numbers. Specifically, generate a random ordering of the numbers from 1 to 200, and processing the order from left to right, pair the numbers together, indicating which ends are tied together.

To figure out the probability that string 1 is going to end up as a self-loop, we need the probability that in the permutation, (1,2) is paired together.

So, count the number of ways (1,2) appears together in the following manner: First, 1 can appear in one of 200 slots. Given the location of 1, 2 has to be in the right position (only 1 possibility) for the configuration to indicate that the ends are tied together. After this, the other slots do not matter, and there are 198! ways to generate those. Then the answer is 200*198! / 200! = 1/199.

Alternatively, we can follow the process of generating a random permutation, where we first place 1 in one of 200 slots, and then place 2 in one of the remaining 199 slots, and the rest of the process can be ignored. The probability that 2 lands in the right place to indicate ends 1 and 2 are tied together is 1/199.

The same reasoning works for any other string $(2k-1,2k)$.

Evan
  • 3,861
0

If you look at the probability of the 2nd pair of ends forming a self-loop, the probability is $1/198$ if the first pair of ends made a self-loop (which had probability $1/199$), otherwise if you first tied two strings together (probability $198/199$) then you need to choose one of the $197/199$ ends that are not part of the two tied strings, and then you have a $1/198$ chance of making a self-loop. So the probability of the 2nd pair forming a self-loop is

$$(1/199)(1/198) + (198/199)(197/199)(1/198) = (1/199)(1/198 + 197/199)$$

which is a bit smaller than $1/199$. In general taking into account all the possible cases for the $k$th pair of ends forming a self-loop for $k > 2$ seems hard to do with a formula, but maybe possible. But no the overall expectation is not $100/199$, at least not by arguing via linearity of expectation.

user2566092
  • 26,142
  • Oh I see. So it's strictly less than $100/199$ but there's no closed formula. – narcissa Aug 11 '13 at 00:00
  • I don't think you should look at it this way, you really want to look at the strands themselves, and follow a single strand through the entire process. See my answer. – Evan Aug 11 '13 at 00:17
  • Here's what I did: after tying string 1, there are 198 ends left. The chance of string 1 forming a self loop is 1/199 and so you will always pick a free string and you have a 1/197 chance of forming a self end. On the other hand, if the first string does not form a self loop, then you have a 196/198 chance of picking an unattached string's end and a 1/197 chance of forming a self loop.

    The total probability of the second string forming a self loop is 196/197 * 1/197 * 198/199 + 1/199 * 1/197 = 1/199.

     – narcissa Aug 11 '13 at 00:36