# Bounding Bernoulli trials by the standard Bernoulli process

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?

• good point - I will fix – dEmigOd Jan 12 '20 at 13:58
• Just to be clear: the success probabilities are chosen independently, with each new toss? – kimchi lover Jan 12 '20 at 14:12
• Yes, and I'm not asking to calculate the exact expectation (but if it could be done - this is nice) – dEmigOd Jan 12 '20 at 14:14
• @Peter, in a standard Bernoulli process (I want to claim it is an upper bound with $p = \frac{1}{2}$) – dEmigOd Jan 12 '20 at 14:20
• 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. – 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.

• Is this valid? How do we know the underlying space is rich enough to support the $U_i$ and the $S_i$? – Jack M Jan 12 '20 at 15:00
• @kimchi lover, MATLAB simulations return an average of $1.385 \pm 0.003$. – dEmigOd Jan 12 '20 at 18:25
• My simulation gave 1.333105, with $10^7$ trials. – kimchi lover Jan 12 '20 at 18:59
• did you simulate different success probabilities before each trial? – dEmigOd Jan 12 '20 at 19:50
• 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. – 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.