## 4 Discrete Time Markov Chain Models and Analysis
### Multi-Link Access with the Shortest Backoff (MLA-S)
Since each selected backoff counter on each link is uniformly  
Figure 6: A simplified Markov Chain model for the backoff window size in MLA-S when the two stations are affiliated with an MLD. distributed and they are independent and identically distributed (i.i.d. ), we can represent \(X_{n,i}\) as follows:  
\[X_{1,i},X_{2,i},\ldots,X_{n,i},\ldots,X_{N,i}\sim Uniform(0,W_{i}-1). \tag{16}\]  
where \(N\) is the total number of links. Let another discrete random variable \(B_{N,i}^{MLA-S}\) be the minimum value of \(N\) backoff counters among \(N\) links in stage \(i\), then \(B_{N,i}^{MLA-S}\) can be expressed as follows:  
\[B_{N,i}^{MLA-S}=\min(X_{1,i},X_{2,i},\ldots,X_{N,i}). \tag{17}\]  
To derive one-step transition probability for the second, the third, and the fourth equations in Equation (15), we need to come up with a probability mass function (PMF) of \(B_{N,i}^{MLA-S}\). To this end, we first derive a cumulative distribution function (CDF) for the probability that the minimum backoff counter of an MLD as follows:  
\[ \begin{split} P\Big{(}B_{N,i}^{MLA-S}\leq k\Big{)}& =1-P\Big{(}B_{N,i}^{MLA-S}>k\Big{)}\\ &=1-P(\min(X_{1,i},X_{2,i},...,X_{N,i})>k)\\ &=1-P(X_{1,i}>k,X_{2,i}>k,...,X_{N,i}>k)\\ &=1-\prod_{j=1}^{N}P\big{(}X_{j,i}>k\big{)}\\ &=1-\prod_{j=1}^{N}\big{(}1-P\big{(}X_{j,i}\leq k\big{)}\big{)}\\ &=1-\prod_{j=1}^{N}\bigg{(}1-\frac{k+1}{W_{i}}\bigg{)}\\ &=1-\bigg{(}1-\frac{k+1}{W_{i}}\bigg{)}^{N}.\end{split}  \tag{18}\]  
The PMF of \(B_{N,i}^{MLA-S}\) can easily be derived with the CDF which we expressed in Equation (18) as follows:  
\[ \begin{split} P\Big{(}B_{N,i}^{MLA-S}=k\Big{)}&=P \Big{(}B_{N,i}^{MLA-S}\leq k\Big{)}-P\Big{(}B_{N,i}^{MLA-S}\leq(k-1)\Big{)}\\ &=\bigg{(}1-\frac{k}{W_{i}}\bigg{)}^{N}-\bigg{(}1-\frac{k+1}{W_{i }}\bigg{)}^{N}.\end{split}  \tag{19}\]  
Since we assumed there are two links, the probability that the minimum value of two backoff values is chosen to \(k\) in stage \(i\) is expressed as follows:  
\[ \begin{split} P\Big{(}B_{2,i}^{MLA-S}=k\Big{)}&= \bigg{(}1-\frac{k}{W_{i}}\bigg{)}^{2}-\bigg{(}1-\frac{k+1}{W_{i}}\bigg{)}^{2} \\ &=\frac{2(W_{i}-k)-1}{{W_{i}}^{2}}.\end{split}  \tag{20}\]  
Since the second equation in Equation (15) accounts for the successful transmission case whereas the third and the fourth equations do for the failed transmissions, \((1-p)\) and \(p\) are multiplied to the derived formula of Equation (20). Now that the Markov Chain has been constructed, we can solve \(\tau_{MLA-S}\) which we introduced in Equation (3). To this end, we need to derive the conditional probabilities,\(P(s_{MLA-S}=i|TX)\) and \(P(TX|s_{MLA-S}=i)\). First, \(P(s_{MLA-S}=i|TX)\) can be expressed same with Equation (5) with \(p_{MLA-S}\) as follows:  
\[P(s_{MLA-S}=i|TX)=\frac{(1-p_{MLA-S})p_{MLA-S}i}{1-p_{MLA-S}{}^{R+1}}. \tag{21}\]  
For \(P(TX|s_{MLA-S}=i)\), we need to derive the average value of backoff counter for stage \(i\), \(E[b_{i}]\). We can use the derived one-step transition probabilities, which are the second, the third, and the fourth equations in Equation (15). Referring Equation (3), we need to derive \(P(TX|s_{MLA-S}=i)\) for all \(i\). Using Equations (6) and (19), it can be derived as follows:  
\[ \begin{split} P(TX|s_{MLA-S}=i)&=\frac{1}{1+E[b_{i, MLA-S}]}\\ &=\frac{1}{1+\sum\limits_{k=0}^{W_{i}-1}k\cdot P\Big{(}B_{n,i}^{ MLA-S}=k\Big{)}}\\ &=\frac{1}{1+\sum\limits_{k=0}^{W_{i}-1}k\bigg{\{}\Big{(}1-\frac{ k}{W_{i}}\Big{)}^{N}-\Big{(}1-\frac{k+1}{W_{i}}\Big{)}^{N}\bigg{\}}},\quad\text{for} \quad i\in[0,m]\end{split}  \tag{22}\]  
where \(E[b_{i,MLA-S}]\) is the average value of backoff counter for stage \(i\) in MLA-S case. Finally, we can get \(\tau_{MLA-S}\) by means of solving non-linear equations with Equations (3), (4), (21) and (22). Next then, we can express throughput equation for MLA-S, \(S_{MLA-S}\) in a similar way to Equation (10) since the condition for boosting channel access is the same with SLA.