1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Elliot Gorokhovsky Nov 4 '16 at 1:19
  • $\begingroup$ 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? $\endgroup$ – D.W.♦ Nov 4 '16 at 4:26
  • $\begingroup$ @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. $\endgroup$ – Elliot Gorokhovsky Nov 4 '16 at 4:35
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ you are my hero $\endgroup$ – Elliot Gorokhovsky Nov 4 '16 at 4:59
  • $\begingroup$ 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})$? $\endgroup$ – Elliot Gorokhovsky Nov 4 '16 at 20:42
  • $\begingroup$ @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. $\endgroup$ – D.W.♦ Nov 4 '16 at 20:52
  • $\begingroup$ 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? $\endgroup$ – Elliot Gorokhovsky Nov 5 '16 at 1:20
  • $\begingroup$ 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. $\endgroup$ – Elliot Gorokhovsky Nov 5 '16 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.