Professor Macarius bought a complete binary Christmas tree having $2^D - 1$ vertices. Unfortunately, on the Christmas Eve his dog Brutus bit the tree. Each of the edges is bit with probability $\frac{1}{2}$, independently from other edges. Let $X$ be the number of vertices in the remaining tree (connected part containing the tree's tip). Count the expected value and variance of $X$.
My solution: Let $1, 2, ..., 2^D - 1$ be the numbers of the vertices counting from the top left ($1$ is the number of the tip, $2$ is the number of the left son of the tip etc.). Let $X_i$ be a Bernoulli random variable such that $X_i=1$ if vertex no. $i$ is in the remaining part of the tree. $$EX_i = \frac{1}{2}^{\lfloor{log_2{i}}\rfloor}$$ $$X = X_1 + ... + X_{2^D - 1}$$ $$EX = \sum_{i=1}^{2^D - 1}\left(\frac{1}{2}\right)^{\lfloor log_2 i \rfloor} \le H_{2^D - 1}$$ Is it correct? Can you get a better approximation for $EX$?
How to count the variance? I'm unfortunately unable to count $EX^2$.
The expectation can be calculated by saying that there if levels are labelled $0,1,\ldots,D-1$, there are $2^d$ vertices at level $d$ and each of these has probability $\frac1{2^d}$ of staying connected to the tip, so the overall expected number connected is $\sum_d 2^d \frac1{2^d} = D$