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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.