Surviving pair revisited

Probability Level 5

You have two lists, $L_A$ and $L_B$ .

$L_A$ consists of the integers 1 to 1,024 in order.
$L_B$ consists of the integers 2 to 1,025 in order.

Now do the following experiment:

Toss a fair coin.
If the outcome is Heads, cross out all the numbers in odd positions in $L_A$ and those in even positions in $L_B$ . If it is Tails, cross out the numbers in even positions in $L_A$ and those in odd positions in $L_B$ .
$L_A$ and $L_B$ are now the new lists of surviving numbers. Note that they are half the previous length.
Repeat steps 1 to 3 with nine more independent coin flips.

Now $L_A$ and $L_B$ each have one number left. Let these be $A$ and $B,$ respectively.

What is the variance of $A+B?$

Recall that the variance of a random variable $X$ with mean $\mu$ is the expected value of $(X-\mu)^2.$

Inspiration

The answer is 0.

3 solutions

Varsha Dani
Oct 19, 2018

As I already showed in my solution to the problem that inspired this, the process of successively crossing out numbers in positions of a particular parity corresponds to a bit string with a 0 for when even indices were crossed out and 1 when odd indices were crossed out, and moreover, the bit string represents the binary expansion of the index of the surviving number. In that problem, the bit strings were alternating 0s and 1s, but here, they are determined by a sequence of ten random coin flips. However, the important point is that since we cross out indices of opposite parities in the two lists, the two bit strings are complementary (one obtained from the other by swapping 1s and 0s). Thus the sum of the indices of the two surviving numbers is always the string 1111111111, which is the binary representation of 1023. Since the numbers stored in the lists are one more than the index in $L_A$ and two more than the index in $L_B$ , the sum $A+B$ is always 1026, and does not depend on the actual sequence of coin flips. Hence the variance is zero.

The easiest way to see this is to reverse the order of the second list. Odd becomes even,even becomes odd.

A Former Brilliant Member - 2 years, 7 months ago

Ah, good point. I guess I oversimplified the problem by making the list length a power of 2. If it weren't this would not work. Or rather, it would, but you would have to pad the lists out to a power of 2 first.

Varsha Dani - 2 years, 7 months ago

Ivan Koswara
Oct 21, 2018

Note that list B always has an even number of elements until the very last step. Thus, if we erase the odd positions in list B, if we reverse list B we would erase the even positions, and vice versa.

Reverse list B. Now the positions of erased numbers in both lists match. This also means at the end, whichever pair remains had the same position in the lists before any number got erased. But all pairs add up to 1026, which means the final pair will also have sum 1026. There is no variance, and so the variance is 0.

Abhishek Sinha
Oct 18, 2018

Note that, at every stage, the surviving members from both lists form an A.P with the same common difference (the value of the common difference after $n-1$ elimination is $2^n$ ). Hence, after $9$ th round of elimination the lists look like as follows: $L_A=\{a, a+d\}, L_B=\{b, b+d\},$ for some integers $a,b,d$ . Thus after the $10$ th stage the sum of the surviving numbers is $a+b+d$ w.p.1. Hence, the conditional variance of the sum of the surviving members is zero. Taking expectation, we get the result.

Your first statements are correct. But the variance is not the expectation of the conditional variance. If it were, then all variances would be zero, since the conditional variance of any random variable, given its own value, is zero.

Varsha Dani - 2 years, 7 months ago

Surviving pair revisited

The answer is 0.

3 solutions

0 pending reports