Computing Expected Cumulative Successes in a Markov-Dependent Transfer
Summary
The document models a file transfer in which each round’s success probability depends on a two-state Markov channel. Given the channel states, the total blocks received by round l has a binomial distribution with success probability determined by the product of the round-by-round failure probabilities. This reduces the expected total to n times one minus the expected product of those failure probabilities.
The author’s main computational concern is avoiding an explicit sum over all possible channel-state sequences, whose count grows exponentially with the number of rounds. The post raises discrete stochastic calculus as a possible route but provides no answer or worked solution. For a trader or researcher, the transferable idea is that conditional expectations can simplify a dependent stochastic process, while Markov structure may permit recursive computation of expectations over state transitions. The document itself does not derive that recursion, establish conditions for it, or provide numerical evidence; its setting is communication reliability rather than finance.
Key ideas
- Conditioning on the channel path makes the cumulative number of received blocks binomial.
- The conditional success probability is one minus the product of the round-specific failure probabilities.
- The unconditional expectation requires averaging that failure product over Markov state paths.
- The document identifies exponential path enumeration as a computational obstacle but leaves its solution open.
Tags
Full text
# Expectation over Markov Process and discrete Ito integral (discrete stochastic calculus)
# Expectation over Markov Process and discrete Ito integral (discrete stochastic calculus)
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.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.