I developed an algorithm and have a recurrence for its runtime; I want to show the expected runtime is $O(\sqrt{n})$.At each iteration $i$, I have a random variable $k_i$ that is equal to the number of heads after flipping $\frac{n}{2^i}$ coins minus $\frac{n}{2^{i+1}}$ (i.e. a binomial distribution centered at 0 with width $\frac{n}{2^i}$). The runtime of my algorithm is then given by the following recurrence:$$B(0) = 0$$$$B(i) = \max\{B(i-1)+k_i, 0\}$$When $B(i)$ is large, the negative and positive $k_i$ can cancel each other out, so intuitively one should be able to come up with a pretty good bound on $\mathbb{E}[B(n)]$, but I have no idea where to start.
Help with a difficult expected runtime recurrence
algorithm analysis;runtime analysis;recurrence relation;randomized algorithms
Yes, you'll have $B(i) = O(\sqrt{n})$ (with very high probability).Note that $k_i$ is binomially distributed, so it is approximately Gaussian.  It has mean $0$ and standard deviation$$\sigma_i = \sqrt{n} \times 2^{-i/2 - 1}.$$The probability that $k_i$ is more than, say, 10 standard deviations above the mean is incredibly small.  We'll define the event $\textsf{BAD}_i$ to be true if $k_i \ge 10 \sigma_i$, and we'll define the event $\textsf{BAD}$ to hold if there exists $i$ such that $\textsf{BAD}_i$ holds, i.e.,$$\textsf{BAD} = \textsf{BAD}_1 \lor \dots \lor \textsf{BAD}_m.$$By a union bound, we have$$\Pr[\textsf{BAD}] \le \sum_i \Pr[\textsf{BAD}_i],$$which is still very small.  Moreover, if $\textsf{BAD}$ does not happen, then we have$$B(m) \le \sum_i 10 \sigma_i = 10 \sqrt{n}/2 \sum_i {1 \over \sqrt{2}^i} \le 10 \sqrt{n}/2 \times 3.5 = O(\sqrt{n}).$$In other words, there is a constant $c$ such that $B(m) \le c \times \sqrt{n}$ with overwhelmingly high probability.(I've shamelessly handwaved and glossed over details all over the place to present the intuition in a clean way, but even correcting for them isn't going to change the bottom-line answer.)