I wish to model the retransmission time of a file that divided into K blocks. I know the successful blocks of first transmission obey the binomial distribution $$ X_1 \sim \text B(K,p) $$ , p is the successful probability of packet delivery. Then, the first retransmission(second transmission) try to complete the file delivery with retransmitting the $N_2 = K-X_1$ packets, and the number of successful packets received is $X_2$. $$ X_2 \sim \text B(K-X_1,p) $$ The remainder of retransmission follows: $$ N_i = K - \sum_{m=1}^{i-1}X_m \\ X_i \sim \text B(N_i,p) $$ We stop the file transaction when $\sum_{m=1}^L X_m = K$.
Eventually, I wish to derive the probability density function of $L$. I think the hard point to model $L$ is the parameter of $X_i$'s distribution depends on $X_{i-1}$.
I know the "multi stage binomial tree model" might be suffice for deriving the PDF of $L$. I also consider if there is a existing stochastic process models this process. But i can't find any.
Any suggestion about the theoretical pdf, stochastic process or approximation is appreciated.

  • $\begingroup$ Neat problem: Did you have a try with the moment generating function? $\endgroup$
    – Xi'an
    Dec 11, 2014 at 5:36
  • 1
    $\begingroup$ After your comment, I tried the MGF. But the MGF refer to it's random variable L which is $\prod_{i=1}^L(1+P+Pe^t)^{K-\sum_{j=1}^{i-1}X_i}= (1+P+Pe^t)^{KL- \sum_{i=1}^L \sum_{j=1}^{i-1}X_i}= (1+P+Pe^t)^{KL-\sum_{i=1}^{L-1}(L-i)X_i}$. I don't know how to handle this MGF. @Xi'an $\endgroup$
    – robit
    Dec 11, 2014 at 6:44
  • $\begingroup$ note: there are mistakes in your mgf: $1+P$ should be $(1-P)$ and the product does not apply because of the dependence between the $X_i$'s, you have to use a sequence of conditional expectations. $\endgroup$
    – Xi'an
    Dec 11, 2014 at 7:26

1 Answer 1


From $$\mathbb{E}[s^{X_1}]=(sp+q)^K$$ (where $q=1-p$), it is rather straightforward to show that $$\mathbb{E}[s^{X_1+\ldots+X_\ell}]=\left\{s(1-q^\ell)+q^\ell\right\}^K$$ Indeed, if we assume it holds for a given $\ell$ (and it does for $\ell=1$), then \begin{align*}\mathbb{E}[s^{X_1+\ldots+X_{\ell+1}}]&=\mathbb{E}[\mathbb{E}[s^{X_1+\ldots+X_{\ell+1}}|X_1+\ldots+X_\ell]]\\ &=\mathbb{E}[s^{X_1+\ldots+X_{\ell}}(sp+q)^{K-X_1-\ldots-X_\ell}]\\ &=(sp+q)^K \left\{ \frac{s}{sp+q}\,(1-q^\ell)+q^\ell\right\}^K\\ &=\left\{s(1-q^{\ell-1})+q^{\ell+1}\right\}^K \end{align*} From there, it follows that, for a given $\ell$, $X_1+\ldots+X_\ell$ is distributed as a Binomial $\text{B}(K,1-q^\ell)$ random variable. Hence, \begin{align*}\mathbb{P}(L=\ell)&=\mathbb{P}(X_1+\ldots+X_{\ell-1}<K=X_1+\ldots+X_{\ell})\\ &=\mathbb{E}[\mathbb{P}(K=X_1+\ldots+X_{\ell}|X_1+\ldots+X_{\ell-1})\mathbb{I}_{X_1+\ldots+X_{\ell-1}<K}]\\&=\mathbb{E}[p^{K-X_1-\ldots-X_{\ell-1}}\,\mathbb{I}_{X_1+\ldots+X_{\ell-1}<K}]\\&=\sum_{i=1}^{K-1} {K \choose i} (1-q^{\ell-1})^i (q^{\ell-1})^{K-i} p^{K-i}\\ &=\sum_{i=1}^{K-1} {K \choose i} (1-q^{\ell-1})^i \left[q^{\ell-1} p\right]^{K-i}\\ &=\left[1-q^{\ell-1}+q^{\ell-1} p\right]^K-(1-q^{\ell-1})^K \end{align*} This gives you the distribution of $L$.

As a checkup, you can run the following code

for (t in 1:T){
  while (x<N){ ell[t]=ell[t]+1; x=x+rbinom(1,N-x,p)}}

and compare the frequencies with

  • $\begingroup$ Thank you for showing me so much insight of this r.v.'s distribution. I am still working for the moment generating function. With your help, I am able to continue my study. And your hint is very inspiring. I am very appriciated. ^_^ $\endgroup$
    – robit
    Dec 11, 2014 at 8:25
  • $\begingroup$ Sorry for my bad English... I meant I am very grateful :D $\endgroup$
    – robit
    Dec 24, 2014 at 5:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.