Let $(X_i)_{i=1}^m$ be a sequence of i.i.d. Bernoulli random variables such that $\Pr(X_i=1)=p<0.5$ and $\Pr(X_i=0)=1-p$. Let $(Y_i)_{i=1}^m$ be defined as follows: $Y_1=X_1$, and for $2\leq i\leq m$ $$ Y_i = \begin{cases} 1,\ &\mathrm{if\ \ \ }p\left(1-\frac{1}{i-1}\sum_{j=1}^{i-1}Y_j\right)+(1-p)\frac{1}{i-1}\sum_{j=1}^{i-1}Y_j<\frac{1}{i}\sum_{j=1}^iX_j\\ 0,\ & \mathrm{otherwise} \end{cases} $$ Finally, define $$ Z_i=\begin{cases} Y_i,\ &\mathrm{w.p. }\ \ 1-p\\ 1-Y_i,\ & \mathrm{w.p. }\ \ p \end{cases} $$ for $i=1,2,\ldots,m$. I want to calculate or get an upper bound on the expectation $\mathbb{E}\left(\sum_{i=1}^mZ_i\right)$ and the variance $\mathrm{Var}\left(\sum_{i=1}^mZ_i\right)$.

For any $i$, we have $\mathbb{E}Z_i = p+(1-2p)\mathbb{E}Y_i$. So a trivial upper bound is $$ \mathbb{E}\left(\sum_{i=1}^mZ_i\right) =mp+(1-2p)\sum_{i=1}^m\mathbb{E}Y_i\leq mp+m(1-2p) = m(1-p) $$ becasue $\mathbb{E}Y_i\leq1$. Unfortunately, when trying to calculate explicitly $\mathbb{E}Y_i$ things quickly become quite involved. Is there any way to get better bounds? Numerical calculation (as well as analytical calculation of the first few) of the means of the random variables $Y_i$ suggest that $\mathbb{E}Y_i\leq \mathbb{E}Y_1 = p$ for any $i$, which would give $$ \mathbb{E}\left(\sum_{i=1}^mZ_i\right)\leq 2mp(1-p) $$ However, it is not clear if $\mathbb{E}Y_i\leq \mathbb{E}Y_1$ is indeed true.

  • $\begingroup$ So actually the actual question here is to compute (or bound) $E[Y_i]$, what follows is pretty irrelevant, right? $\endgroup$
    – leonbloy
    Dec 10, 2018 at 16:30
  • $\begingroup$ @leonbloy Yes, for the calculation of the mean of $\sum_iZ_i$ (I'm also curious about the variance) it is suffice to compute or bound $E[Y_i]$ for any $i$. $\endgroup$
    – Mike_D
    Dec 10, 2018 at 16:33
  • $\begingroup$ This looks interesting. Could you elaborate on the interpretation of the success criteria for $Y_i~$, the $p(1-\frac{Y_{i-1}}{i-1})+(1-p)\frac{Y_{i-1}}{i-1}<\frac{1}{i}\sum_{j=1}^iX_j$? Does it come from a geometric or combinatorial scheme? $\endgroup$ Dec 10, 2018 at 16:56
  • $\begingroup$ @LeeDavidChungLin Yes. First note that I've fixed a typo in this condition. The meaning condition is if the relative number of 1's up to time $i$ in the sequence $(X_1,\ldots,X_i)$ is greater than the binary convolution of the parameter $p$ with the relative number of 1's up to time $i-1$ in the sequence $(Y_1,\ldots,Y_{i-1})$, then $Y_i=1$. Note that $\sum_iZ_i$ is in fact just $\mathrm{Binomial}(\sum_{i=1}^mY_i,1-p)+\mathrm{Binomial}(m-\sum_{i=1}^mY_i,p)$ whose expectation, given the $\sum_{i=1}^mY_i$ is exactly $m$ times the left hand side of the success criteria for $Y_m$. $\endgroup$
    – Mike_D
    Dec 10, 2018 at 17:11
  • $\begingroup$ oh, binary convolution, I see. Thanks for clarifying. $\endgroup$ Dec 10, 2018 at 17:13

1 Answer 1


Not an answer. From simulations, it seems that $E[Y_i]$ has a suprisingly wild (chaotic?) behaviour, we should not expect to get a closed formula for it - nor even attempt to prove it's monotonous. Here's a graph for $p=0.15$ and $p=0.19$.

Now, in case you're thinking: "statistical noise"... it doesn't seem to be. If you look closely, I have drawn two graphs (orange and blue lines) for $p=0.15$ , for different runs ($10^6$ tries each), they are almost undistinguishable (look around $i=85$).

What seems to be true (already conjectured) is that $E[Y_i]\le p$, for $p < \frac12$ and $E[Y_i]\ge p$, for $p > \frac12$

enter image description here

  • $\begingroup$ Thanks! Indeed this is exactly the behavior that I notices from my simulations too. The question is then whether it can be shown that $E(Y_i)\leq p$ for $p<0.5$. $\endgroup$
    – Mike_D
    Dec 11, 2018 at 19:04

You must log in to answer this question.

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