6
$\begingroup$

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.

$\endgroup$
  • $\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 '15 at 18:15
  • $\begingroup$ I added the definition of $R$ and modified the derivation. Any suggestions? Thanks. @AFK $\endgroup$ – robit Dec 27 '15 at 8:55
  • $\begingroup$ Where is this question from? a paper or a book? $\endgroup$ – Gordon Dec 27 '15 at 17:14
  • $\begingroup$ Neither. It is from my research on communication protocol design. @Gordon $\endgroup$ – robit Dec 28 '15 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 '15 at 15:23

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.