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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.