5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Neat problem: Did you have a try with the moment generating function? $\endgroup$ – Xi'an Dec 11 '14 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 '14 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 '14 at 7:26
3
$\begingroup$

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

T=10^6
N=13
p=.85
ell=rep(1,T)
for (t in 1:T){
  x=rbinom(1,N,p)
  while (x<N){ ell[t]=ell[t]+1; x=x+rbinom(1,N-x,p)}}

and compare the frequencies with

probel=function(N,p,el){
 (1-(1-p)^(el-1)+p*(1-p)^(el-1))^N-(1-(1-p)^(el-1))^N}
$\endgroup$
  • $\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 '14 at 8:25
  • $\begingroup$ Sorry for my bad English... I meant I am very grateful :D $\endgroup$ – robit Dec 24 '14 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.