# A coupon collector type problem with changing probabilities

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

• In the bounded case, do you assume a success if you run out of coins? – 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.

• 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). – Clement C. Oct 19 '18 at 16:11
• FWIW, my guess based on calculations and computations is that the true expectation is $\sqrt t + 1/2 - \Theta(1/\sqrt t)$. – Neal Young Oct 19 '18 at 19:56
• @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? – Neal Young Oct 19 '18 at 21:26
• I am most likely missing something here. Why doesn't $$\frac{x^{1-\alpha}}{1-\alpha}\Bigg|_{t}^{t+i}$$ work? – Clement C. Oct 19 '18 at 21:29
• @ClementC. -- Sorry, not Step (6), I meant to say Step (9). E.g. for $\alpha=0.4$? – Neal Young Oct 19 '18 at 21:50