## 3 Three Points on a Line
In our specific algorithm \(G_{n}^{ALG}\), we define those values as follows:  
\[S_{LC}=(1,0,0),\ S_{LR}=(0,1,0),\ S_{CR}=(0,0,1),\] \[S_{2i-1}=(p_{i},0,1-p_{i})\ (i=1,\ldots,n),\ S_{2i}=(p_{i},1-p_{i},0 )\ \ \ \ (i=1,\ldots,n-1)\]  
where \(p_{i}\) is \(\frac{n}{n+1}\cdot\frac{(1+\frac{1}{n})^{i}-1}{(1+\frac{1}{n})^{n}-1}\). We describe how to transform an algorithm graph into the actual algorithm. Suppose for example that the request sequence is \(CL\). Assume the algorithm is in state \(S_{2}\), and suppose that the next request is \(C\). The state transition from \(S_{2}\) to \(S_{3}\) occurs. Suppose that \(S_{2}\) has configuration-probability pairs \((C_{1},q_{1})\), \((C_{2},q_{2})\), and \((C_{3},q_{3})\) (\(C_{1}=(L,C),C_{2}=(L,R)\) and \(C_{3}=(C,R)\)) and \(S_{3}\) has \((C_{1},r_{1})\), \((C_{2},r_{2})\), and \((C_{3},r_{3})\). We introduce variables \(x_{ij}\) (\(i,j=1,2,3\)) such that \(x_{ij}\) is equal to the probability that the configuration before the transition is \(C_{i}\) and the configuration after the transition is \(C_{j}\). Indeed, by a slight abuse of notation the \(x_{ij}\) values can be considered to be the algorithm itself. The \(x_{ij}\) values also allow us to calculate the cost of the algorithm as described next. The average cost for a transition is given by \(cost=\sum_{i=1}^{3}\sum_{j=1}^{3}x_{ij}d(C_{i},C_{j})\), where \(d(C_{i},C_{j})\) is the cost to change the configuration from \(C_{i}\) to \(C_{j}\). We can select the values of \(x_{ij}\) in such a way that they minimize the above cost under the condition that \(\sum_{j=1}^{3}x_{ij}=q_{i},\quad\sum_{i=1}^{3}x_{ij}=r_{j}.\) In the case of three points on the line, it is straightforward to solve this linear program in general. If the servers are on \(L\) and \(C\) and the request is \(R\), then a greedy move (\(C\to R\)) is optimal. If the servers are on \(L\) and \(R\) and the request is \(C\), then the optimal probability is just a proportional distribution due to \(d(L,C)\) and \(d(C,R)\). The \(x_{ij}\) values also show the actual moves of the servers. For example, if the servers are on \(L\) and \(R\) in \(S_{2}\), we move a server in \(L\) to \(C\) with probability \(x_{23}/q_{2}\) and \(R\) to \(C\) with probability \(x_{21}/q_{2}\). From the values \(x_{ij}\), one can also obtain the expected cost of an algorithm for each transition, as follows:  
\[\text{cost}(S_{LC},S_{LR}) =n,\ \text{cost}(S_{CR},S_{LR})=1,\ \text{cost}(S_{LR},S_{1})=np_{1}+1-p_{1},\] \[\text{cost}(S_{2i-1},S_{2i}) =1-p_{i}\quad(i=1,\ldots,n-1),\] \[\text{cost}(S_{2i},S_{2i+1}) =n(p_{i+1}-p_{i})+1-p_{i+1}\quad(i=1,\ldots,n-1),\] \[\text{cost}(S_{2i-1},S_{CR}) =(n+1)p_{i}\quad(i=1,\ldots,n),\] \[\text{cost}(S_{2i},S_{LR}) =np_{i}\quad(i=1,\ldots,n-1),\] \[\text{cost}(S_{2n-1},S_{LC}) =(n+1)(1-p_{n}).\]  
We are now ready to prove Lemma 1. Recall that \(G_{n}^{OPT}\) and \(G_{n}^{ALG}\) are the same graph. With a request sequence \(\sigma\), we can thus associate the same sequence, \(\lambda(\sigma)\), of transitions in \(G_{n}^{OPT}\) and \(G_{n}^{ALG}\). The offline cost for \(\lambda(\sigma)\) can be calculated from \(G_{n}^{OPT}\) and the online cost from \(G_{n}^{ALG}\). Considering these two costs, we obtain the competitive ratio for \(\sigma\). We need only consider the cycles of the type considered below, as other cycles can be obtained as disjoint unions. 1. \(S_{1},S_{2},\ldots,S_{2h-1},S_{CR},S_{LR}\quad(h=1,\ldots,n-1)\)
2. \(S_{1},S_{2},\ldots,S_{2h},S_{LR}\quad(h=1,\ldots,n-1)\)
3. \(S_{1},S_{2},\ldots,S_{2n-1},S_{LC},S_{LR}.\)  
For sequence (1), the OPT cost is \(2h\) and ALG cost is \(2 np_{h}+2h-2\sum_{j=1}^{h-1}p_{j}=2 hC_{n}\). Similarly, for sequence (2), \(OPT=2h\) and \(ALG<2 hC_{n}\) and for sequence (3) \(OPT=2n\) and \(ALG=4n-2\sum_{j=1}^{n}p_{j}=2 nC_{n}\). Thus the competitive ratio is at most \(C_{n}\) for any of these sequences, which proves the lemma. \(\Box\)