<p><strong>Lemma.</strong> <em>In the unbounded case, the expected number of flips is at most <span class="math-container">$\sqrt t + 3/2$</span>.</em></p>

<p><em>Proof.</em> Let r.v. <span class="math-container">$F$</span> be the number of flips until a head.
Then the expected number of flips is</p>

<p><span class="math-container">\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}</span></p>

<hr>

<p>Of course the same bound holds in the bounded case as well.</p>

CC BY-SA 4.0
2018-10-19T16:11:52.847Z
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.
CC BY-SA 4.0
2018-10-19T19:56:44.977Z
FWIW, my guess based on calculations and [computations](https://repl.it/@nealyoung/SecondaryFrugalTwintext?language=python3) is that the true expectation is $\sqrt t + 1/2 - \Theta(1/\sqrt t)$.
Neal Young
CC BY-SA 4.0
2018-10-19T21:26:21.800Z
@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
CC BY-SA 4.0
2018-10-19T21:29:44.950Z
I am most likely missing something here. Why doesn't $$\frac{x^{1-\alpha}}{1-\alpha}\Bigg|_{t}^{t+i}$$ work?
Clement C.
CC BY-SA 4.0
2018-10-19T21:50:31.153Z
@ClementC. -- Sorry, not Step (6), I meant to say Step (9).  E.g. for $\alpha=0.4$?
Neal Young
CC BY-SA 4.0
2018-10-19T21:58:58.000Z
I don't think there is a closed form, but why wouldn't that similarly be $$\int_{t}^\infty e^{-\frac{5}{3}x^{3/5}}dx$$ (which does converge)?
Clement C.
CC BY-SA 4.0
2018-10-19T06:06:17.373Z
2018-10-19T13:28:48.037Z
2018-10-19T13:28:48.037Z
Neal Young
<p>Suppose we are flipping coins starting at some time <span class="math-container">$t$</span>. At time <span class="math-container">$t$</span> the probability we obtain heads is <span class="math-container">$\frac{1}{\sqrt{t}}$</span>. If the coin lands tails, at time <span class="math-container">$t+1$</span> the probability of heads is now <span class="math-container">$\frac{1}{\sqrt{t+1}}$</span> 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 <span class="math-container">$T$</span>, e.g. there at most <span class="math-container">$T &gt; t$</span> coins. </p>

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

CC BY-SA 4.0
2018-10-18T18:24:33.600Z
In the bounded case, do you assume a success if you run out of coins?
Clement C.
<pr.probability>
A coupon collector type problem with changing probabilities
SVN
# A coupon collector type problem with changing probabilities

(Asked by: username_0 on 2018-10-17)

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

**Tags:** pr.probability
> **Comments:**
> **username_1**: In the bounded case, do you assume a success if you run out of coins?  

---

## 1 answers

### Answer by username_2 on 2018-10-19. Score: 5

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

> **Comments:**
> **username_1**: 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).  
> **username_2**: FWIW, my guess based on calculations and [computations](https://repl.it/@nealyoung/SecondaryFrugalTwintext?language=python3) is that the true expectation is $\sqrt t + 1/2 - \Theta(1/\sqrt t)$.  
> **username_2**: @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?  
> **username_1**: I am most likely missing something here. Why doesn't $$\frac{x^{1-\alpha}}{1-\alpha}\Bigg|_{t}^{t+i}$$ work?  
> **username_2**: @ClementC. -- Sorry, not Step (6), I meant to say Step (9).  E.g. for $\alpha=0.4$?  
> **username_1**: I don't think there is a closed form, but why wouldn't that similarly be $$\int_{t}^\infty e^{-\frac{5}{3}x^{3/5}}dx$$ (which does converge)?  

---

