<s>[INST] Expectation of dependent Bernoulli sum I want to estimate the expected value of the following sum of random variables,
$$ Y = \sum_{i=1}^N X_i $$
where each $X_i$ is a Bernoulli random variable. In particular,
$$ X_1 = \begin{cases} 1, & \text{with prob. } 1/N \\
  0, & \text{with prob. }  1 - 1/N \end{cases} $$
and for all $2 \leq i \leq N$
$$ X_i = \begin{cases} 1, & \text{with prob. } p_i \\
  0, & \text{with prob. } 1 - p_i \end{cases} $$
where 
$$ p_i = \begin{cases} p_{i-1} + 1/N, & \text{if } X_{i-1} = 0 \\
  1/N, & \text{if } X_{i-1} = 1 \end{cases} $$
I have computed the value for $ N=2 $ and $ N=3 $. For $ N = 2 $,
$$
  \mathbb{E}[Y] = 1 \left[ \left( 1 - \frac{1}{N} \right) \frac{2}{N} + \frac{1}{N} \left( 1 - \frac{1}{N} \right)  \right] + 2 \frac{1}{N^2} = \frac{5}{4}
$$
where the first term corresponds to the sequences $(01)$ and $(10)$, while the second to $(11)$.
For $ N=3 $, here are the calculations
$$ 
\begin{gather}
\mathbb{E}[Y] = \left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right)\frac{3}{N} + 2 \times \left(1-\frac{1}{N}\right)\frac{2}{N} \frac{1}{N} + 2 \times \frac{1}{N}\left(1-\frac{1}{N}\right)\frac{2}{N} + 3 \times \frac{1}{N} \frac{1}{N} \frac{1}{N} + \left(1 - \frac{1}{N}\right)\frac{2}{N}\left(1-\frac{1}{N}\right) + \frac{1}{N}\left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right) + 2 \times \frac{1}{N} \frac{1}{N} \left(1-\frac{1}{N}\right) \\
 = \frac{3}{N^3} - \frac{6}{N^2} + \frac{6}{N} \\
N=3 \rightarrow = \frac{39}{27} 
\end{gather}
$$
This results from the sequences (001), (011), (101), (111), (010), (100), (110).
Is there any way to proceed farther?
 [/INST] MY TRY
We first look at $ P\{ Y=i\}$, i.e., $Y$ has exactly $i$ ones and $N-i$ zeros. The probability corresponding to ones is $N^{-i}$. The probability corresponding to zeros depends on number and size of blocks of zeros. There can be at most $i+1$ blocks of size between 0 and $N-i$, as we already have $i$ ones. Further, the probability corresponding to a block of size $a_k$ is $(a_k+1)!N^{-a_k} $. Thus, we have
\begin{align}
 P\{ Y=i\} &= N^{-i}\prod_{\substack{a_1,a_2,\ldots,a_{i+1}\geq 0\\ \sum_{k=1}^{i+1} a_k=N-i} }1-\frac{(a_k+1)!}{N^{a_k}}\\
&= N^{-N}\prod_{\substack{a_1,a_2,\ldots,a_{i+1i}\geq 0\\ \sum_{k=1}^{i+1} a_k=N-i} } N^N-(a_k+1)!
\end{align}
Also, we have the following:
\begin{align}
E\{Y\} = \sum_{i=0}^N i P\{ Y=i\} = N^{-N} \sum_{i=0}^N i  \prod_{\substack{a_1,a_2,\ldots,a_{i+1}\geq 0\\ \sum_{k=1}^{i+1} a_k=N-i} } N^N-(a_k+1)!
\end{align}
I don't know how to simplify it further!
</s>