I am doing a research on communication protocol design. A file of $n$ blocks is transferred in several rounds and $R_i$ denotes the number of blocks received in the $i$-th round. The sender sends $n-R_1-R_2-\cdots-R_{i-1}$ blocks in the $i$-th round and $X_i$ denotes the state of the channel in the $i$-th round. Actually, I would like to know the expected value of $\sum_{m=0}^l R_m$ to estimate the transmission rounds.

Assume that $X_i$ satisfies a first-order discrete time-homogeneous Markov chain with two states, thus I can obtain the random variables $R_i\mid R_1,R_2, \ldots, R_{i-1}, X_i$ conditioned on the previous states and the state of the $i$-th step of the Markov process $X$, i.e., $$ R_i \sim Bin(n-R_1-R_2-\cdots-R_{i-1},p(X_i)). $$ By induction on $i$, we have $R_1+R_2+\cdots+R_i \mid X_1,X_2,\ldots,X_i$, i.e., $$ R_1+R_2+\cdots+R_i \sim Bin(n,1-\prod_{m=1}^{i} (1-p(X_i))). $$ I would like to evaluate the expected value of $\sum_{m=1}^l R_m$, and deduce as follows. $$ \begin{aligned} & \mathbb{E}\left[\sum_{m=1}^l R_m \right] \\ = & \mathbb{E}\left[\mathbb{E}\left[\sum_{m=1}^l R_m \Bigg| X_1,X_2,\ldots,X_l \right] \right]\\ = & \mathop{\mathbb{E}}_{\text{over } X_1,X_2,\ldots,X_l} \left[ n\times (1-\prod_{m=1}^{l} (1-p(X_m))) \right]\\ = & n \times \left( 1- \mathop{\mathbb{E}}_{\text{over } X_1,X_2,\ldots,X_l} \left[ \prod_{m=1}^{l}1-p(X_m) \right] \right). \end{aligned} $$ I stuck here because if I carry out the evaluation of the expectations, the number of terms would be $2^l$, which is too large for computation.

An alternative approach is to evaluate the random variable $\sum_{m=1}^l R_m$ using discrete Ito integral, hoping this will simply the formula of the expectation. But I lack the knowledge of real analysis and measure theory, self studying stochastic calculus is difficult for me.

Any suggestions or hints? Thanks in advance!

This question has been posed in the Math Stackexchange Expectation over Markov Process and discrete Ito integral.

  • $\begingroup$ Your question is incomplete. What is the relationship between the $R_i$ and $X_j$? If $R_i = f(X_i)$ then $E[R_i|X] = E[R_i|X_i] = R_i$ but if $R_i$ depends on other $X_j$'s your derivation is false and the answer is probably more complicated. $\endgroup$
    – AFK
    Dec 26, 2015 at 18:15
  • $\begingroup$ I added the definition of $R$ and modified the derivation. Any suggestions? Thanks. @AFK $\endgroup$
    – robit
    Dec 27, 2015 at 8:55
  • $\begingroup$ Where is this question from? a paper or a book? $\endgroup$
    – Gordon
    Dec 27, 2015 at 17:14
  • $\begingroup$ Neither. It is from my research on communication protocol design. @Gordon $\endgroup$
    – robit
    Dec 28, 2015 at 6:05
  • $\begingroup$ some is still not clear; for example, what is $n$? what are $R_i$s? what do you want to achieve? A well defined question and more background information will be more helpful, as we do not have your background to understand your question. $\endgroup$
    – Gordon
    Dec 28, 2015 at 15:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy