# Help with a difficult expected runtime recurrence

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.

• @dw B(i-1) can be less than B(i) because this is actually not the runtime but just the term of the total runtime I can't bound. You are wrong that it's just a sum: when B(i-1) is small, the binomial distribution gets the left tail cut off. Since B(i-1) depends on previous values of k, the distributions are very much not independent. – Elliot Gorokhovsky Nov 4 '16 at 1:19
• OK, so this is a one-dimensional random walk with a boundary at the origin. There's lots of theory on such random walks. Perhaps some of it may be helpful for this problem? – D.W. Nov 4 '16 at 4:26
• @D.W. Yes, except the step size is binomially distributed. All the random walk theory I've ever seen has been with uniformly distributed step size. – Elliot Gorokhovsky Nov 4 '16 at 4:35

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.)

• you are my hero – Elliot Gorokhovsky Nov 4 '16 at 4:59
• wait, hold up... all this shows is that $\mathbb{E}[B(n)] = (1-p)O(\sqrt{n}) + pO(n)$ for some small constant $p$. So this would still be $O(n)$. Is there any way to get $p = O(1/\sqrt{n})$? – Elliot Gorokhovsky Nov 4 '16 at 20:42
• @RenéG, I think $p$ can be driven to be arbitrarily, exponentially small (by increasing the number "10" as needed), and this will only increase $c$ by a small amount ($\log (1/p)$ or less). I realize this is all handwaving, so you should check my reasoning. E.g., it's probably worth working out the details more formally/carefully. – D.W. Nov 4 '16 at 20:52
• Hm... what I really need to do is compute the expected value of $k_i$, which I think should be something like $\sqrt{n}/2^i$. Then there's no problem, just use linearity of expectation. Do you have any idea how the expected value of $k_i$ might be calculated? – Elliot Gorokhovsky Nov 5 '16 at 1:20
• Because if there's a $\log(1/p)$ factor, that would give me $O(\sqrt{n}\log{n})$, which I can already get using the a different algorithm. – Elliot Gorokhovsky Nov 5 '16 at 1:21