# multi stage binomial “process”

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.

• Neat problem: Did you have a try with the moment generating function? – Xi'an Dec 11 '14 at 5:36
• 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 – robit Dec 11 '14 at 6:44
• 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. – Xi'an Dec 11 '14 at 7:26

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}

• 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. ^_^ – robit Dec 11 '14 at 8:25
• Sorry for my bad English... I meant I am very grateful :D – robit Dec 24 '14 at 5:30