What's yours?

An interesting aspect of this is that they use the Flajolet-Martin algorithm to estimate the path length. The paper of Flajolet-Martin deals with a certain correction factor φ, which is defined as follows: φ = 2^{-½} *e*^{γ} α^{-1}, where γ = 0.57721... is Euler's constant and α is the constant
Π_{n ≥ 1} (2*n*/(2*n*+1))^{(-1)t(n)},
where *t*(*n*) is the Thue-Morse sequence, the sequence that counts the parity of the number of 1's in the binary expansion of *n*.

The Thue-Morse sequence has long been a favorite of mine, and Allouche and I wrote a survey paper about it some time ago, where we mentioned the Flajolet-Martin formula. The Thue-Morse sequence comes up in many different areas of mathematics and computer science. And we also wrote a paper about a constant very similar to α: it is Π_{n ≥ 0} ((2*n*+1)/(2*n*+2))^{(-1)t(n)}. Believe it or not, it is possible to evaluate *this* constant in closed form: it is equal to 2^{-½} !

By contrast, nobody knows a similar simple evaluation for α. In fact, I have offered $50 for a proof that α is irrational or transcendental.

## 7 comments:

Mine is 3.16. How sensitive is this to the number of Friends you have? It doesn't seem to be a big factor as long as you have several Friends.

If I were to set up three Facebook accounts (A, B, and C) where C's only Friend is B and B's only Friend is A then you can't link to C without going through 2 degrees of separation, right? Wouldn't this screw up the results posted on the website?

Why do you think the weird possibility that you envision, which probably never happens, would "screw up" the results?

Anyway, if you read the link, you will see that they are not computing the average path length explicitly, but rather estimating it using a certain probabilistic counting technique. It is not guaranteed to be perfectly accurate.

Maybe I didn't think this through. The "average" would only be affected if I created several million such groups, right?

Do you know the answer to my first question?

Yes to the first question.

Adding more friends will improve your average if your friends are 'well-connected'; otherwise it won't. So it doesn't directly depend on the number of friends, just their connectedness.

3.87

Mine is 3.2.

~~ Paul

I'm 3.46, average. I've only been on FB for a few months.

Post a Comment