I think the analytic answer should be sqrt(n/2).
So let's suppose X and Y are random points in the n dimensional hypercube
{0,1}^n. Let Z_i be an indicator variable that is 1 if X_i != Y_i and 0
otherwise. Then d(X,Y)^2 =sum (X_i - Y_i)^2 = sum( Z_i). Then the expected
squared distance is E d(X,Y)^2 = sum( E Z_i) = sum( Pr[ X_i != Y_i]) = n/2.
On Oct 19, 2011, at 12:57 PM, Federico Castanedo wrote:
> what about this:
>
> http://www.wisdom.weizmann.ac.il/~oded/p_aver-metric.html
>
> HTW
>
> 2011/10/19 Sean Owen <[email protected]>
>
>> (And when I do the simulation correctly, I get a better answer: sqrt(n/6) )
>>
>> On Wed, Oct 19, 2011 at 5:21 PM, Sean Owen <[email protected]> wrote:
>>> Hmm. Not knowing the analytics answer I just wrote a simulation.
>>> sqrt(n / 3) looks like a shockingly good fit for the average distance
>>> between two randomly chosen points in the n-dimensional hypercube.
>>>
>>> Accident? error? known result? Seems clear that something like sqrt(n)
>>> would be a better factor than n. But, indeed, there are yet more
>>> possibilities with exponential functions.
>>
