Suppose we are flipping coins starting at some time $t$. At time $t$ the probability we obtain heads is $\frac{1}{\sqrt{t}}$. If the coin lands tails, at time $t+1$ the probability of heads is now $\frac{1}{\sqrt{t+1}}$ and so on... What is the expected number of flips until the coin lands heads? In particular I would be interested in an upper bound on the expectation.. If this is difficult suppose we also make the assumption that it is bounded by $T$, e.g. there at most $T > t$ coins.

If the probabilities are constant at $p$ at each round, the expected value is $1/p$ which is like one coupon being collected in the coupon collector problem. Since the probability of heads is less than $1/\sqrt{t}$ at each round, $\sqrt{t}$ is a lower bound for the expectation. On the other hand, the probability is greater than $1/\sqrt{T}$ in the bounded case, and so $\sqrt{T}$ is an upper bound. The question is where in this regime $[\sqrt{t}, \sqrt{T}]$ does the expectation fall..

  • 1
    $\begingroup$ In the bounded case, do you assume a success if you run out of coins? $\endgroup$ – Clement C. Oct 18 '18 at 18:24

Lemma. In the unbounded case, the expected number of flips is at most $\sqrt t + 3/2$.

Proof. Let r.v. $F$ be the number of flips until a head. Then the expected number of flips is

\begin{align} E[F] & = \sum_{i=1}^\infty \Pr[F \ge i] && (1)\\ &= \sum_{i=0}^\infty \Pr[\text{first $i$ flips are tails}] && (2)\\ &= \sum_{i=0}^\infty \prod_{j=t}^{t+i-1} (1-1/\sqrt{j}) && (3)\\ &\le \sum_{i=0}^\infty \exp(\textstyle-\sum_{j=t}^{t+i-1} 1/\sqrt j) & \text{as } 1+z\le e^z~~ & (4)\\ &\le \sum_{i=0}^\infty \textstyle\exp(-\int_{t}^{t+i} 1/\sqrt x ~dx) & \text{as } \textstyle \sum_{j=a}^{b-1} f(j) \ge \int_{a}^b f(x)\, dx~~&(5)\\[-10ex] &&~~\text{for $f$ decreasing}~~\\ &= 1+\sum_{i=1}^\infty \textstyle\exp(2\sqrt{t}-2\sqrt{t+i}) & \text{as } \textstyle\int 1/\sqrt x ~dx = 2\sqrt x~~&(6)\\ &= 1+e^{2\sqrt{t}} \sum_{i=t+1}^\infty e^{-2\sqrt i}&&(7)\\ &\le 1+e^{2\sqrt{t}} \int_{t}^\infty e^{-2\sqrt x}\,dx &\text{as } \textstyle \sum_{i=a}^{\infty} f(i) \le \int_{a-1}^\infty f(x)\, dx ~~&(8)\\ &&\text{for monotonic $f$}~~\\ \\ &= 1 + e^{2\sqrt{t}} \,e^{-2\sqrt t}(\sqrt t + 1/2) & \text{as } \textstyle\int_t^\infty e^{-2\sqrt x}\,dx = e^{-2\sqrt t}(\sqrt t + 1/2)~~&(9)\\\\ &= \sqrt {t} + 3/2&&~~\Box \end{align}

Of course the same bound holds in the bounded case as well.

  • $\begingroup$ Just as a remark, eyeballing the argument: the same analysis goes through for $1/t^{\alpha}$, for any $0<\alpha < 1$ (and for $\alpha=1$, one gets an infinite expectation). $\endgroup$ – Clement C. Oct 19 '18 at 16:11
  • $\begingroup$ FWIW, my guess based on calculations and computations is that the true expectation is $\sqrt t + 1/2 - \Theta(1/\sqrt t)$. $\endgroup$ – Neal Young Oct 19 '18 at 19:56
  • $\begingroup$ @ClementC., for $1/t^\alpha$ with $\alpha\ne 1/2$, what integral do you get for in Step (6) in the (generalized) proof that you have in mind? $\endgroup$ – Neal Young Oct 19 '18 at 21:26
  • $\begingroup$ I am most likely missing something here. Why doesn't $$\frac{x^{1-\alpha}}{1-\alpha}\Bigg|_{t}^{t+i}$$ work? $\endgroup$ – Clement C. Oct 19 '18 at 21:29
  • $\begingroup$ @ClementC. -- Sorry, not Step (6), I meant to say Step (9). E.g. for $\alpha=0.4$? $\endgroup$ – Neal Young Oct 19 '18 at 21:50

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.