# Multi-Phase Adaptive Recoding: An Analogue of Partial Retransmission in Batched Network Coding +
## 2 Preliminary
### Expected Rank Functions  
The distribution of the ranks of the batches is closely related to the throughput of BNC. Hence, the expectation of the rank distribution is a core component in recoding strategy. We first describe the formulation of this expectation at the next network node. Let \(\mathrm{Bin}(n,p)\) be a binomial distribution with failure probability \(p\). Its probability mass function, where \(x\in\mathbb{Z}\) is defined, is as follows:  
\[\mathrm{Bin}(n,p;x)= \begin{cases}\binom{n}{x}(1-p)^{x}p^{n-x}&\text{if }x=0,1, \ldots,n,\\ 0&\text{otherwise.}\end{cases} \]We further define a variant of \(\text{Bin}(n,p)\), denoted by \(\underset{\leftrightarrow}{\text{Bin}}(n,p,c)\), which we called the condensed binomial distribution. The word \"condensed\" is borrowed from the Bose-Einstein condensate in physics, which has a similar phenomenon on the distribution. Here, we give a brief description in layman terms. Suppose we have a distribution of finding a boson, which is a type of particle, in different (quantum) states. When we lower the temperature, the distribution shifts towards the lower states. However, there is a lowest accessible state. The probability masses that shifted beyond the aforementioned state accumulate and \"condense\" into the lowest accessible state. Its probability mass function is defined as  
\[\underset{\leftrightarrow}{\text{Bin}}(n,p,c;x)= \begin{cases}\text{Bin}(n,p; x)&\text{if }x=0,1,\ldots,c-1,\\ \sum_{i=c}^{n}\text{Bin}(n,p;i)&\text{if }x=c,\\ 0&\text{otherwise}\end{cases} \]  
for \(x\in\mathbb{Z}\). The hooked arrow symbolizes that we move the probability masses of the tail towards where the arrows point to. The parameter \(k\) is called the condensed state of the distribution. We can interpret these distributions this way. Let \(p\) be the packet loss rate of the outgoing channel. Assume the packet loss events are independent. The random variable of the number of received packets of a batch at the next node when the current node sends \(n\) packets of this batch follows \(\text{Bin}(n,p)\), while the random variable of the rank of this batch at the next node follows \(\underset{\leftrightarrow}{\text{Bin}}(n,p,r)\) when this batch has rank \(r\) at the current node. This is because when the field size is sufficiently large, any \(i\) random vectors from an \(r\)-dimensional vector space can span a \(\text{min}\{i,r\}\)-dimensional vector subspace with high probability. One can find the exact formula for the probability mass function for the rank in [63]. Yet, it is common to assume a sufficiently large field size in the context of recoding of BNC [70, 74, 75]. Let \(V\) and \(V^{\prime}\) be the vector spaces spanned by (the coefficient vectors of) the packets of a batch at the current node and the next node, respectively. The \"rank\" of the batch at the current node that can still provide the next node is the \"useful\" information of the batch at the current node. This concept, known as the innovative rank, was adopted in [122], although there is context for handling overhearing networks. Formally, it is defined as  
\[\text{dim}(V+V^{\prime})-\text{dim}(V^{\prime}).\]  
Before the current node sends any packet to the next node, \(V^{\prime}\) is an empty space. In this case, the innovative rank is the same as the rank of the batch--that is, for a fire-and-forget recoding scheme, the rank equals the innovative rank. The goal of recoding is to retain as much \"rank\" as possible. In a distributed view, we want to maximize the expected rank of the batches at the next node, which is the core idea of adaptive recoding. Denote by \(E(r,t)\) the expected rank of a batch at the next node when this batch has innovative rank \(r\) at the current node and the current node sent \(t\) recoded packets--that is,  
\[E(r,t)=\sum_{i=0}^{t}\text{Bin}(t,p;i)\text{min}\{i,r\}=\sum_{i=0}^{M}i\, \underset{\leftrightarrow}{\text{Bin}}(t,p,r;i).\]  
This is called the expected rank function.