A288416 Median of (2X-n)^2 + (2Y-n)^2 where X and Y are independent random variables with B(n, 1/2) distributions.

2, 4, 2, 4, 10, 8, 10, 8, 10, 16, 18, 20, 18, 20, 26, 20, 26, 20, 26, 32, 26, 32, 34, 36, 34, 36, 34, 40, 34, 40, 50, 40, 50, 52, 50, 52, 50, 52, 50, 52, 58, 64, 58, 64, 58, 68, 58, 68, 74, 68, 74, 72, 74, 72, 82, 80, 82, 80, 82, 80, 82, 80, 90, 100, 90, 100

Offset: 1

Author

Matt Frank, Jun 09 2017

Keywords

• nonn

Comments

Interpretation: Start at the origin, and flip a pair of coins. Move right one unit if the first coin is heads, and otherwise left one unit. Then move up one unit if the second coin is heads, and otherwise down one unit. This sequence gives your median squared-distance from the origin after n pairs of coin flips.

The mean of (2X-n)^2 + (2Y-n)^2 is 2n, or A005843.

A continuous analog draws each move from N(0,1) rather than from {+1,-1}, so the final x- and y- coordinates are distributed as N(0,sqrt(n)). Then the final point has probability 1 - exp(-r^2/2n) of being within r of the origin, and the median squared-distance for this continuous analog is n log(4). We also observe empirically that for this discrete sequence, a(n)/n approaches log(4).

Examples

			For n=3 the probabilities of ending up at the lattice points in [-3,3]x[-3,3] are 1/64 of:
1 0 3 0 3 0 1
0 0 0 0 0 0 0
3 0 9 0 9 0 3
0 0 0 0 0 0 0
3 0 9 0 9 0 3
0 0 0 0 0 0 0
1 0 3 0 3 0 1
So the squared-distance is 2 with probability 36/64, 10 with probability 24/64, and 18 with probability 4/64; the median squared-distance is therefore 2.
		

Crossrefs

Cf. A288347, which is similar, with shifted coordinates; and also A288346.

Programs

Mathematica

Shifted[x_, n_] := (2 x - n)^2;
WeightsMatrix[n_] := Table[Binomial[n, i] Binomial[n, j], {i, 0, n}, {j, 0, n}]/2^(2 n);
ValuesMatrix[n_, f_] := Table[f[i, n] + f[j, n], {i, 0, n}, {j, 0, n}];
Distribution[n_, f_] := EmpiricalDistribution[Flatten[WeightsMatrix[n]] -> Flatten[ValuesMatrix[n, f]]];
NewMedian[n_, f_] :=
Mean[Quantile[Distribution[n, f], {1/2, 1/2 + 1/2^(2 n)}]];
Table[NewMedian[n, Shifted], {n, 66}]