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'anDec 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$– robitDec 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'anDec 11, 2014 at 7:26
1 Answer
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}
-
$\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$– robitDec 11, 2014 at 8:25
-
$\begingroup$ Sorry for my bad English... I meant I am very grateful :D $\endgroup$– robitDec 24, 2014 at 5:30