|
Just in case you missed it, here's the question. Let an denote the average number of loops when we start with n strings. We can make a couple key observations to find a recursive equation for an, which will give us the answer. First, let's do some small-n checking to help gain some understanding. If n=1, then clearly there must be exactly 1 loop at the end. This means that What if n=2? We take one end, and with probability 1/3 (since there are 3 ends to choose from), we tie it to itself. In that case, we must end up with 2 loops. Otherwise, with probability 2/3, we tie it to the other string and we must end up with 1 loop. We get Now for the general case. We take one end, and we choose randomly from the remaining 2n-1 ends. With probability 1/(2n-1), we tie this string to itself, and from there the situation is exactly as if we had started with 1 loop + n-1 strings. Otherwise, with probability (2n-2)/(2n-1), we tie this end to another string, and from there the situation is exactly as if we had started with n-1 strings. This breakdown can allow us to express an in terms of an-1 as follows: We can initiate this recursive equation with a1=1, or even a0=0 if we wish (they both give the same answers for all greater n). And we can summarize the end result nicely by writing it as: That is, if we start with n strings, then we can find the average number of loops by adding the reciprocals of the odds up to 2n-1. If we're interested in going a little further, we can notice that where Hn is the nth harmonic number, which is the sum 1 + 1/2 + 1/3 + ... + 1/n. Hn grows like log(n), the natural logarithm. Thus where the symbol ~ here means asymptotic equivalence. |