# Calculating the expectation of a sum of dependent random variables

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.