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



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