# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 3 Multi-Phase Adaptive Recoding
### Multi-Phase Systematic Adaptive Recoding Problem (SAP)
: We first prove the amount of resources consumed. When \(k=1\), the resources consumed is \(\sum_{i}r_{1}\Pr(r_{1})=\mathbb{E}[R_{1}]=\frac{1-p^{k}}{1-p}\mathbb{E}[R_{1}]\). Assume that the resources consumed by \(k\) phases is \(\sum_{i=1}^{k}\sum_{r_{i}}r_{i}\Pr(r_{i})=\frac{1-p^{k}}{1-p}\mathbb{E}[R_{1}]\). When there are \(k+1\) phases, the resources consumed is  
\[\sum_{i=1}^{k+1}\sum_{r_{i}}r_{i}\Pr(r_{i})=\frac{1-p^{k}}{1-p}\mathbb{E}[R_{1} ]+\mathbb{E}[\hat{R}_{k+1}]\stackrel{{(a)}}{{=}}\frac{1-p^{k}}{1 -p}\mathbb{E}[R_{1}]+p^{k}\mathbb{E}[R_{1}]=\frac{1-p^{(k+1)}}{1-p}\mathbb{E}[ R_{1}],\]  
where (a) follows Lemma 2. This part is proved by induction. Next, we prove the expected rank (at the next node) by induction. Note that for any \(r\in\{0,1,2,\ldots\}\), we have \(E(r,r)=(1-p)r\). When \(k=1\), the expected rank is \(\sum_{r_{1}}\Pr(r_{1})E(r_{1},r_{1})=(1-p^{(1)})\mathbb{E}[R_{1}]\). Assume that the expected rank after \(k\) phases is \(\sum_{i=1}^{k}\sum_{r_{i}}\Pr(r_{i})E(r_{i},r_{i})=(1-p^{k})\mathbb{E}[R_{1}]\). When there are \(k+1\) phases, the expected rank is  
\[\sum_{i=1}^{k+1}\sum_{r_{i}}\Pr(r_{i})E(r_{i},r_{i})\] \[= (1-p^{k})\mathbb{E}[R_{1}]+\sum_{R_{+1}}\Pr(r_{k+1})E(r_{k+1},r_ {k+1})\] \[= (1-p^{k})\mathbb{E}[R_{1}]+(1-p)\mathbb{E}[\hat{R}_{k+1}]\] \[\stackrel{{(b)}}{{=}} (1-p^{k})\mathbb{E}[R_{1}]+(1-p)p^{k}\mathbb{E}[R_{1}]\] \[\mathbb{E}[\tilde{R}_{k+1}] =\sum_{r_{1},r_{2},\ldots,r_{k+1}}r_{k+1}\Pr(r_{1})\prod_{j=1}^{k }\text{Bin}(r_{j},p;r_{j}-r_{j+1})\]0  
where (b) follows Lemma 2 as well. The proof is then completed. An intuitive meaning of the above statements is as follows. Every systematic phase remains \(p\) portion of innovative rank on average, which is the average rank lost during the transmission. Therefore, after \((k-1)\) systematic phases, the expectation of the innovative rank remaining is the \(p^{k-1}\) portion of \(\mathbb{E}[R_{1}]\). The resources consumed by \(k\) systematic phases is the sum of the expected innovative rank in all the phases, which is \((1+p+p^{2}+\ldots+p^{k-1})\mathbb{E}[R_{1}]=\frac{1-p^{k}}{1-p}\mathbb{E}[R_{ 1}]\). The average expected rank at the next node is the part that is not innovative, i.e., \(\mathbb{E}[R_{1}]-p^{k}\mathbb{E}[R_{1}]\) by Lemma 2. When \(k\rightarrow\infty\), the resources consumed is \(\frac{\mathbb{E}[R_{1}]}{1-p}\). This means that if \(\frac{\mathbb{E}[R_{1}]}{1-p}\leq t_{\text{avg}}\), then there are always enough resources to perform more systematic phases. Otherwise, we can only perform \(S^{\prime}\) systematic phases where, according to Theorem 3, \(S^{\prime}\) is the largest integer satisfying \(\frac{1-p^{S^{\prime}}}{1-p}\mathbb{E}[R_{1}]\leq t_{\text{avg}}\). In other words, we have  
\[\mathbb{E}[\tilde{R}_{k+1}] =\sum_{r_{1},r_{2},\ldots,r_{k+1}}r_{k+1}\Pr(r_{1})\prod_{j=1}^{k }\text{Bin}(r_{j},p;r_{j}-r_{j+1})\]1  
Note that if there are remaining resources, we need to apply TAP for one more phase in our setting. **Corollary 1**. : _Consider SAP with the highest possible number of systematic phases. Then, \(\mathbb{E}[R]=\min\{(1-p)t_{\text{avg}},\mathbb{E}[R_{1}]\}\)._  
Proof. : If \(\mathbb{E}[R_{1}]\leq(1-p)t_{\text{avg}}\), then we do not have an upper limit on the number of systematic phases. By Theorem 3, we know that \(\mathbb{E}[\bar{R}]=\lim_{k\rightarrow\infty}(1-p^{k})\mathbb{E}[R_{1}]= \mathbb{E}[R_{1}]\). Now, we consider \(\mathbb{E}[R_{1}]>(1-p)t_{\text{avg}}\). Let \(S^{\prime}=\lfloor\log_{p}(1-\frac{(1-p)t_{\text{avg}}}{\mathbb{E}[R_{1}]})\rfloor\). According to Theorem 3, the expected rank after \(S^{\prime}\) systematic phases is \((1-p^{S^{\prime}})\mathbb{E}[R_{1}]\). The remaining resources after \(S^{\prime}\) systematic phases is \(t^{\prime}_{\text{avg}}:=t_{\text{avg}}-\frac{1-p^{S^{\prime}}}{1-p}\mathbb{E}[ R_{1}]\). In the \((S^{\prime}+1)\) phase, there are insufficient resources to send a basis of the innovative rank space. We gain \((1-p)t_{\text{avg}}^{\prime}\) expected rank in this phase.