1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ good point - I will fix $\endgroup$
    – dEmigOd
    Jan 12, 2020 at 13:58
  • 1
    $\begingroup$ Just to be clear: the success probabilities are chosen independently, with each new toss? $\endgroup$ Jan 12, 2020 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, 2020 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, 2020 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, 2020 at 14:50

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
6
  • $\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, 2020 at 15:00
  • $\begingroup$ @kimchi lover, MATLAB simulations return an average of $1.385 \pm 0.003$. $\endgroup$
    – dEmigOd
    Jan 12, 2020 at 18:25
  • $\begingroup$ My simulation gave 1.333105, with $10^7$ trials. $\endgroup$ Jan 12, 2020 at 18:59
  • $\begingroup$ did you simulate different success probabilities before each trial? $\endgroup$
    – dEmigOd
    Jan 12, 2020 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$ Jan 12, 2020 at 20:04
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .