Suppose we have a Bernoulli-like process $P$. At each step a coin is tossed and the outcome ("success", "failure") is recorded. What differentiate $P$ from the standard Bernoulli process, is that we pick a probability of "success" uniformly at random in range $(1/2, 1)$ at each step before we toss the coin.

I'm interested in finding an upper bound on the expected number of trials until the first "success" is tossed.

What I have thought, if the probability of "success" is at least $1/2$, then at each step $P$ is more probable to stop than a standard Bernoulli process, therefore an expectation of a standard geometrically distributed variable bounds from above the expectation of steps until the first "success".

How can I make this claim formal?

  • $\begingroup$ good point - I will fix $\endgroup$ – dEmigOd Jan 12 '20 at 13:58
  • 1
    $\begingroup$ Just to be clear: the success probabilities are chosen independently, with each new toss? $\endgroup$ – kimchi lover Jan 12 '20 at 14:12
  • $\begingroup$ Yes, and I'm not asking to calculate the exact expectation (but if it could be done - this is nice) $\endgroup$ – dEmigOd Jan 12 '20 at 14:14
  • $\begingroup$ @Peter, in a standard Bernoulli process (I want to claim it is an upper bound with $p = \frac{1}{2}$) $\endgroup$ – dEmigOd Jan 12 '20 at 14:20
  • 1
    $\begingroup$ What do you think a "standard" Bernoulli process is? Your trial consists of setting a number $p$ uniformly in $(1/2,1)$ and then tossing a coin that produces success with probability $p.$ Each such trial this has a certain probability of success. That probability (not the number $p$) is the same for each trial. Each trial is independent of every other trial. $\endgroup$ – David K Jan 12 '20 at 14:50

As David K states implies, your process is exactly a Bernoulli process with non-random success probability $p=3/4$. The expected number of flips is then $4/3\approx1.333$.

Your argument & approach are good. You can* construct an iid sequence $U_i$ of $U[0,1]$ variables and another, $S_i$, iid $U[1/2,1]$, and consider the sequence of coupled binary outcomes $(X_i,Y_i)$ where $X_i = 1$ exactly when $U_i\le 1/2$ and $Y_i = 1$ exactly when $U_i\le S_i$. Then the $X_i$ process has the same probability distribution as the standard Bernoulli process and the $Y_i$ process has the same probability distribution as your $P$ process, and $X_i\le Y_i$ with probability $1$.

Footnote: If you are afraid your original probability space $(\Omega,\mathcal A, P)$ is not rich enough to support all these newly constructed rvs, don't worry. It is rich enough to support a $U[1/2,1]$ random variable, and hence is a so-called standard probability space. If it supports a uniform rv, that rv's binary digits are an iid sequence of fair coin flips, and by Cantor, a countable sequence of such sequences, and thus a countable sequence of uniforms, and so on. The resulting $X_i$ and $Y_i$ constructed this way will not be equal $\omega$ by $\omega$ to what you started out with, but will have the same distributional properties.

  • $\begingroup$ Is this valid? How do we know the underlying space is rich enough to support the $U_i$ and the $S_i$? $\endgroup$ – Jack M Jan 12 '20 at 15:00
  • $\begingroup$ @kimchi lover, MATLAB simulations return an average of $1.385 \pm 0.003$. $\endgroup$ – dEmigOd Jan 12 '20 at 18:25
  • $\begingroup$ My simulation gave 1.333105, with $10^7$ trials. $\endgroup$ – kimchi lover Jan 12 '20 at 18:59
  • $\begingroup$ did you simulate different success probabilities before each trial? $\endgroup$ – dEmigOd Jan 12 '20 at 19:50
  • $\begingroup$ With this code: for(k=1; ; k++){ p = (1+drand48())/2; u = drand48(); if(u<p)break; } The final value of $k$ is the number of flips needed. $\endgroup$ – kimchi lover Jan 12 '20 at 20:04

While, kimchi's answer is an answer to the problem as I have stated it in the first place ...

I want to share an approach, that tackles directly the expectation bound.

Suppose, we have a series of independent Bernoulli trials $X_i$ each with a probability of success $p_i \geq \frac{1}{2}$. And a series of standard i.i.d. Bernoulli trials $Y_i$ with a probability of success $p = \frac{1}{2}$.

Define by $X$ - the index of the first success in the series $X_i$, and by $Y$ - an index of the first success in the series $Y_i$.

We have that $Y \sim Geom(\frac{1}{2})$, and $\mathbb{E}(Y) = 2$.

We ask, what is $\mathbb{P}(X > k)$ ?

In other words what is the probability that the first success in series $X_i$ happens after the $k^{th}$ trial. The answer can be calculated in a straight-forward way: $$\mathbb{P}(X > k) = \prod\limits_{i=1}^k(1-p_i),$$ as all trials before and including $k^{th}$ should fail.

We further use the fact that $p_i \geq p$ to show that $$\mathbb{P}(X > k) = \prod\limits_{i=1}^k(1-p_i) \leq \prod\limits_{i=1}^k(1-p) = \mathbb{P}(Y > k)$$

Recall, that for a discrete variable $Z$(such as $X$ and $Y$) taking values in $\{1, 2, \ldots \} \cup \{ +\infty\}$ $$\mathbb{E}(Z) = \sum\limits_{k = 1}^{\infty}\mathbb{P}(Z > k)$$

Now sum the probabilities to get the expectations: $$\mathbb{E}(X) = \sum\limits_{k = 1}^{\infty}\mathbb{P}(X > k) \leq \sum\limits_{k = 1}^{\infty}\mathbb{P}(Y > k) = \mathbb{E}(Y)$$

Thus a direct upper bound is shown.


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.