multi stage binomial "process"

Question

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.

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

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}