First of all, its interesting to wonder why the method of calculating the average was worded the way it was. It was "Specifically, consider one were to select an initial piece of string and ask "what is the expected value of the length of the loop this piece of string will end up in?"". This is different than if it had been "Specifically, consider one were to randomly select a final loop from all of the loops and ask "what is the expected length of this loop?"". The first wording basically gives a heavier weighting to longer loops, and will have a larger answer. Also, it gives an answer with an actual clean mathematical form, rather than the second one which gives a total mess (feel free to work it out sometime, maybe somebody smarter than me can point out a nice form of it that I just missed).
Anyway, lets start by figuring out a few simple cases. Suppose we have N strings, and G(N) is the answer we seek. It is pretty easy to see that G(1)=1. For N=2, consider where the first end of one of the strings ends up. With 1/3 chance, it loops to itself, and we have two loops of length 1, with 2/3 chance it does not loop to itself and we have 1 loop of length 2. So,
G(2)=1/3 1+2/3 2
=1+2/3
=5/3
The 1+2/3 line is going to turn into an attempt to establish the overall pattern, the final loop the first string is in (which is as good as any other string) is at least length 1, and 2/3 of the time it is an extra length.
Next, N=3: the first end of the first string (which is the random string we are going to choose at the end) has a 1/5 chance of looping to itself. It has a 4/5 chance of not looping to itself and then a 1/3 chance of closing with length 2 and a 2/3 chance of closing with length 3. So we have
G(3)=1/5+4/5 1/3+4/5 2/3
=1+4/5+4/5 2/3
=7/3
The 1+4/5+4/5 2/3 is again an attempt at the overall pattern, the final loop of the first string starts at length 1, is 4/5 chance to be length +1 and is 4/5 2/3 chance to be another length +1.
We can already guess the overall formula, G(N)=1 + 2/3 (N-1), and if you check the next few terms you will find this still works. To prove it in general is quite the trick though. First, we can see the general formula for G(N):
G(N)=1+Σ Π (2N-2m)/(2N-2m+1)
where the sum has k from 1 to N-1 and the product has m from 1 to k. You can fiddle with this a bit using the formula:
Π (m-N)=Γ (k+1-N)/ Γ (1-N)(product over m going from 1 to k) (Γ being the Gamma function), or you can just shove it all into Maple at once. Basically you get a bunch of garbage whatever you do.
After spending some time simplifying that garbage, you can find
G(N) = 1+2/3 (N-1)-1/(3 √π ) Γ (1/2-N)/Γ (1-N)
So, we see the term we want, and them some Gamma function garbage. This extra term shows up for a few reasons. First of all, in the first formula Π (m-N)=Γ (k+1-N)/ Γ (1-N), the math doesn't "know" if k is greater than N (in which case you need to get zero), or even if the things you are using are integers at all.
Anyway, in our case everything is an integer, so Γ (1/2-N) is simply a number one can find using the analytic continuation of the Gamma function, and Γ (1-N) is infinitely large, as Gamma has simple poles at every nonpositive integer. So the extra garbage term is just zero.
If one can find a way to solve this problem that doesn't involve the Gamma function, I would love to hear it.
No comments:
Post a Comment