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.
Best Answer
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)$.