3.37 Degrees of Separation

This is pretty interesting: Facebook has a tool that estimates the average number of intermediate people needed to link you, via the shortest path, to anyone else on Facebook. Mine is 3.37, which means the average path length (number of links) to me is 4.37, or that the average number of people in a shortest chain connecting others with me (including me and the person at the end) is 5.37.

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} (2n/(2n+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} ((2n+1)/(2n+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.