Proof Sketch of [lem:32upper32bound32cost32of32framework] (full proof in 7.1). First, note that the total cost incurred by the algorithm is upper bounded by the total amount we charge to each arrival, \(\sum_{t \in [n]} \mathrm{charge}(t)\), so we focus on upper bounding this quantity in expectation. We split the total charge into three terms: (i) \(\sum_{t \in J} \mathrm{charge}(t)\) conditional on event \(E_{bad}\) happening, (ii) \(\sum_{t \in J} \mathrm{charge}(t)\) conditional on event \(E_{bad}\) not happening, and (iii) \(\sum_{t \notin J} \mathrm{charge}(t)\).

For (i) we use [lem:32charge32requests32in32J32for32bad32event] to obtain upper bound \(n \cdot (\sup{J} - \inf{J})\), and \(E_{bad}\) happens with probability \(O(\log^2{n} / n)\), so we get \(O(\log^2{n}) \cdot (\sup{J} - \inf{J}) \leq O(\log^2{n}) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_t - \min_{t \in [n]}r_t \right]\) due to [lem:maxminregions].

For (ii), notice that when \(r_t \in J\), we have \(\mathrm{charge}(t) \leq \mathrm{cost}(t)\) by definition, so we upper bound this term by the total cost of the algorithm conditional on \(E_{bad}\) not happening. Then we use [lem:32total32cost32for32good32event] to obtain upper bound \(O(\log^2{n}) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_t - \min_{t \in [n]}r_t \right]\).

For (iii) we use [lem:32charge32requests32outside32J] to obtain upper bound \(2 (\sup{J} - \inf{J}) + n \cdot \mathop{\mathrm{\mathbb{E}}}_{r \sim \mathcal{D}}\left[\inf_{x \in J} |r - x|\right]\), which we further upper bound by \(O(1) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_t - \min_{t \in [n]}r_t \right]\) by [lem:maxminregions]. ◻

Proof. We proceed to show that 2 satisfies 1 2 3, the \(O(\log^2 n)\)-competitive ratio then follows immediately from [lem:32ratio32of32algorithmic32framework].

3.5.0.1 1.

We prove this by inducting on the number of phases. First, note that if the number of unmatched requests is ever equal to the number of requests yet to arrive, it will be equal for all subsequent time steps as all arriving requests will be immediately matched and the number of unmatched requests and yet to arrive requests will decrease at the same rate. Therefore, it suffices to consider whether the number of unmatched requests is equal to the number of future requests at time \(t_{\rho}\).

For \(k \in [\rho]\), let \(F_k = \cap_{j \in \left[\beta^{\rho+1-k}\right]} \left\{\left|B_j \setminus M_{t_k}\right| \leq 1\right\}\) be the event that each bucket ends the \(k\)-th phase with at most one unmatched request and \(A_k = \left\{\forall t \in \left[t_{k}\right] : |\{r_1, \dots, r_{t}\} \setminus M_t | < n - t - 1 \right\}\) be the event that the number of unmatched requests at the end of the \(k\)-th phase is less than the number of future requests. We will show that, \(\Pr[A_{\rho}] \geq \Pr\left[\cap_{k \leq \rho} F_k\right] \geq 1-\rho/n\). We first prove \(\Pr\left[\cap_{k \leq \rho} F_k\right] \geq 1-\rho/n\) by induction. In the first phase, each bucket begins with zero unmatched requests. Since requests in the same bucket are matched immediately, it is impossible for some bucket to end the phase with more than one unmatched request, i.e. \(\Pr[F_1] = 1 \geq 1-1/n\).

Now, fix some \(k \geq 1\) and assume \(\Pr\left[\cap_{k'\leq k} F_{k'}\right] \geq 1-k/n\). Note that \[\begin{align} \Pr\left[\cup_{k' \leq k+1} \bar{F}_{k'}\right] &= \Pr\left[\cup_{k' \leq k} \bar{F}_{k'}\right] + \Pr\left[\bar{F}_{k+1}\middle|\cap_{k' \leq k} F_{k'}\right] \cdot \Pr\left[\cap_{k' \leq k} F_{k'}\right]\\ &\leq \Pr\left[\cup_{k' \leq k} \bar{F}_{k'}\right] + \Pr\left[\bar{F}_{k+1}\middle|\cap_{k' \leq k} F_{k'}\right]\\ &\leq \frac{k}{n} + \Pr\left[\bar{F}_{k+1}\middle|\cap_{k' \leq k} F_{k'}\right], \end{align}\] where the first equality follows from the tower rule and the fact that \(\cup_{k' \leq k} \bar{F}_{k'} \implies \cup_{k' \leq k+1} \bar{F}_{k'}\), and the last inequality follows from the induction hypothesis. So, it suffices to show \(\Pr\left[\bar{F}_{k+1}\middle|\cap_{k' \leq k} F_{k'}\right] \leq \frac{1}{n}\). Note that, by \(F_k\), each bucket ended the \(k\)-th phase with at most one unmatched request. Since the requests in the \((k+1)\)-th phase are formed from \(\beta\) buckets in the \(k\)-th phase, this means that each bucket begins the \((k+1)\)-th phase with at most \(\beta\) unmatched requests.

Since each bucket in the \((k+1)\)-th phase has probability \(1/\beta^{\rho+1-(k+1)}\) of receiving a request, the following Chernoff bound proves that \(\Pr\left[\bar{F}_{k+1} \mid \cap_{k' \leq k} F_{k'}\right] \leq \frac{1}{n}\). Let \(X^{k+1}_j\) be the number of requests in bucket \(B_j\). Then, by definition of \(f\) in 2, we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ X^{k+1}_j \right] = \mathop{\mathrm{\mathbb{E}}}\left[\left| \{ t \in \{t_{k} + 1, \dots, t_{k+1}\}: i(t) = j\} \right|\right] &= \left( t_{k+1} - t_{k} \right) \cdot \frac{1}{\beta^{\rho + 1 - (k+1)}} = 3(\beta-1) \end{align}\]

Then, by Chernoff bounds, for \(\delta = 1\): \[\begin{align} \Pr_{I \sim \mathcal{D}^n}\left[X_j^{k+1} \leq (1- \delta) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ X_j^{k+1} \right] \right] \leq \exp\left(- \frac{\delta^2}{2} (3\beta - 1)\right) = \exp\left(-\frac{3\beta-1}{2}\right) \leq \frac{1}{n}, \end{align}\] where the last inequality follows from \(\beta = \left\lfloor 400\log{n} \right\rfloor\). So, we have \[\begin{align} \Pr\left[\cup_{k' \leq k+1}\bar{F}_{k'}\right] \leq \Pr\left[\bar{F}_{k+1} \mid \cap_{k' \leq k} F_{k'}\right] + \frac{k}{n} \leq \frac{1}{n} + \frac{k}{n} =\frac{k+1}{n}. \end{align}\]

So, it suffices to show \(\Pr[A_{\rho}] \geq \Pr\left[\cap_{k \leq \rho} F_k\right]\), or equivalently, \(\cap_{k \leq \rho} F_k \implies A_{\rho}\). To do so, note that at the end of any phase, the number of future requests is equal to three times the number of buckets. By \(\cap_{k \leq \rho} F_k\), each bucket ends each phase with at most one unmatched request. So, at the end of any phase, the number of unmatched requests is at most the number of buckets, which is less than the number of future requests. Thus, given \(\cap_{k \leq \rho} F_k\), it is impossible that the number of unmatched requests at time \(t_{\rho}\) is equal to the number of future requests. Therefore, we have \(\Pr[A_{\rho}] \geq \Pr\left[\cap_{k \leq \rho} F_k\right] \geq 1-\rho/n\), as desired.

3.5.0.2 2.

By definition of \(f\), no requests are ever assigned to \(B_{L}\) or \(B_{R}\). Therefore, w.p.\(1\), we have \(\left| \{t \in \{ t_0+1, \dots, n\}: i(t) \in \left\{L, R\right\} \} \right| = 0 \leq \beta^2\).

To prove the second part of the condition, again note that, for any \(k \in [2..\rho], j \in \left[\beta^{\rho+1-k}\right]\), the expected number of arrivals in bucket \(B_j\) is \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\left[X_j^k\right] = \mathop{\mathrm{\mathbb{E}}}\left[\left| \{ t \in \{t_{k-1} + 1, \dots, t_{k}\}: i(t) = j\} \right|\right] &= \beta^{\rho+1-k} \cdot 3(\beta-1) \cdot \frac{1}{\beta^{\rho+1-k}}\\ &= 3(\beta-1). \end{align}\] Then, a Chernoff bound with \(\delta = 3\) yields \[\Pr_{I \sim \mathcal{D}^n} \left[X^k_j \geq (1+\delta) \cdot \mathop{\mathrm{\mathbb{E}}}\left[X_j^k\right]\right] \leq \exp\left(-\frac{\delta^2 \cdot \mathop{\mathrm{\mathbb{E}}}\left[X_j^k\right]}{2+\delta}\right) \leq \exp\left( - \frac{9 \cdot 3(\beta-1)}{5}\right) \leq \frac{1}{n},\] where the last inequality follows from \(\beta = \left\lfloor 400\log{n} \right\rfloor\). For \(k=1\), we have \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\left[X_j^1\right] = \mathop{\mathrm{\mathbb{E}}}\left[\left| \{ t \in \{t_0+ 1, \dots, t_{1}\}: i(t) = j\} \right|\right] &= \left(n-t_0- 3\beta^{\rho}\right) \cdot \frac{1}{\beta^{\rho}}\\ &< 4 \beta^{\rho+2} \cdot \frac{1}{\beta^{\rho}}\\ &=4\beta^2. \end{align}\] Then, a Chernoff bound with \(\delta = 1\) yields \[\Pr_{I \sim \mathcal{D}^n} \left[X^1_j \geq (1+\delta) \cdot \mathop{\mathrm{\mathbb{E}}}\left[X_j^1\right]\right] \leq \exp\left(-\frac{\delta^2 \cdot \mathop{\mathrm{\mathbb{E}}}\left[X_j^1\right]}{2+\delta}\right) \leq \exp\left( - \frac{4\beta^2}{3}\right) \leq \frac{1}{n},\] where the last inequality follows from \(\beta = \left\lfloor 400\log{n} \right\rfloor\).

3.5.0.3 3.

We bound the expected length of the intervals: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[\sum_{j = 1}^{ \beta^{\rho} } (\sup{I^1_j} - \inf{I^1_j}) \right] = \beta^{\rho} \cdot \frac{1}{\beta^{\rho}} = 1 \leq 3 - \frac{6}{n+1} = 3 \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]} r_t - \min_{t \in [n]} r_t \right], \end{align}\] where the first equality is since \(I^1_j = \left[ \frac{(j-1)}{\beta^{\rho}}, \frac{j}{ \beta^{\rho}} \right]\) for all \(j \in [ \beta^{\rho} ]\) by definition of \(f\), the second inequality holds for \(n > 0\) and the second equality since \(\mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}{r_t} - \min_{t \in [n]}{r_t} \right] = \frac{n}{n+1} - \frac{1}{n+1} = \frac{n-1}{n+1} = 1 - \frac{2}{n+1}\) by order statistics of \(U[0,1]\). ◻

Proof. Let \(A\) and \(B\) be sets with sizes \(K\) and \(N-K\) respectively. Suppose that we draw elements from \(A \cup B\) without replacement in two processes. In the first process, elements are drawn until exactly \(\ell\) elements have been drawn from the set \(B\). Let \(Y\) be the number of elements drawn from \(A\) during this process. Then, \(Y \sim \textrm{NegativeHypergeometric}(N, K, \ell)\). In the subsequent process, we continue drawing elements until exactly \(m+\ell\) elements have been drawn from \(A \cup B\) (if there at least \(m+\ell\) draws in the initial process, no elements will be drawn in the second process). Let \(X\) be the number of elements drawn from \(B\) during the first \(m+\ell\) draws. Then, \(X \sim \textrm{Hypergeometric}(N, N-K, m+\ell)\).

We will show that \(Y \leq m \iff X \geq \ell\). For the forward implication, suppose that \(Y \leq m\). Then, the initial process contains at most \(m+\ell\) draws, with \(\ell\) of them being from the set \(B\). Therefore, \(X \geq \ell\). For the reverse direction, suppose that \(X \geq \ell\). Then, at most \(m\) items were drawn from \(A\) across both processes. Since \(Y\) is the number of elements drawn from \(A\) in the first process, we clearly have \(Y \leq m\). So, we conclude that \(Y \leq m \iff X \geq \ell\). Since \(Y \sim \textrm{NegativeHypergeometric}(N, K, \ell)\) and \(X \sim \textrm{Hypergeometric}(N, N-K, m+\ell)\), we have \[\Pr\left[Y \sim \textrm{NegativeHypergeometric}(N, K, \ell) \leq m\right]= \Pr\left[X \sim \textrm{Hypergeometric}(N, N-K, m+\ell) \geq \ell\right]\] ◻

Proof. Recall that, because the requests appear in random order, the requests that arrive in the learning phase constitute a uniformly random subset of size \(t_0\) of the total set of requests. Thus, each \(Y_j\) follows the same distribution. Let the set of learning phase requests be \(T\), and the set of non-learning phase requests be \([n]\setminus T\). Then, each \(Y_j\) corresponds to the number of elements drawn from \([n]\setminus T\) before \(\beta/8\) elements are drawn from \(T\) when elements from \([n]\) are drawn without replacement. This is the same formulation described in 2 with parameters \(n\), \(n-t_0\), and \(\beta/8\). So, we conclude \(Y_j \sim \textrm{NegativeHypergeometric}(n,n-t_0, \beta/8)\). ◻

Proof sketch. The lemma is proved by using 2 to rewrite the tail bounds for the negative hypergeometric distribution in terms of tail bounds for the hypergeometric distribution. The result then follows from 1. ◻

Proof. Note that: \[\begin{align} \Pr\left[\bar{E}_M \right] = \Pr\left[\bigcup_{j \in \left[\beta^{\rho}\right]} \left\{Y_j \not\in \left[\frac{n\beta}{16t_0}, \frac{n\beta}{4t_0}\right] \right\}\right] &\leq\sum_{j \in \left[\beta^{\rho}\right]} \Pr\left[Y_j \not \in \left[\frac{n\beta}{16t_0}, \frac{n\beta}{4t_0}\right]\right]. \end{align}\] So, for any \(j \in \left[\beta^{\rho}\right]\), it suffices to bound \(\Pr\left[Y_j \not \in \left[\frac{n\beta}{16t_0}, \frac{n\beta}{4t_0}\right]\right]\). Note that by Lemma 3, we have \(Y_j \sim \textrm{NegativeHypergeometric}\left(n, n-t_0, \beta/8\right)\). Then: \[\begin{align} \Pr\left[Y_j \not \in \left[\frac{n\beta}{16t_0}, \frac{n\beta}{4t_0}\right] \right] = \Pr\left[Y_j \sim \textrm{NegativeHypergeometric}\left(n, n-t_0, \beta/8\right) \not \in \left[\frac{n\beta}{16t_0}, \frac{n\beta}{4t_0}\right] \right] \leq \frac{2}{n^3}, \end{align}\] where the inequality follows from Lemma 4. We conclude that: \[\begin{align} \Pr\left[\bar{E}_M \right] = \Pr\left[\bigcup_{j \in \left[\beta^{\rho}\right]} \left\{Y_j \not\in \left[\frac{n\beta}{16t_0}, \frac{n\beta}{4t_0}\right] \right\}\right] &\leq\sum_{j \in \left[\beta^{\rho}\right]} \Pr\left[Y_j \not \in \left[\frac{n\beta}{16t_0}, \frac{n\beta}{4t_0}\right]\right] \leq \beta^{\rho} \cdot \frac{2}{n^3} < \frac{1}{n^2}, \end{align}\] where the first inequality is due to (1) and the second inequality follows from \(\beta^{\rho} < n/2\). ◻

Proof. Let \(k \in [\rho], j \in \left[\beta^{\rho+1-k}\right]\) be arbitrary. By the law of total probability, we have \[\begin{align} \Pr\left[X^k_j < \beta\right] &= \Pr\left[X^k_j < \beta \middle| E_M\right] \cdot \Pr\left[E_M\right] + \Pr\left[X^k_j < \beta \middle| \bar{E}_M\right] \cdot \Pr\left[\bar{E}_M\right]\\ &\leq \Pr\left[X^k_j < \beta \middle| E_M\right] + \Pr\left[\bar{E}_M\right]\\ &\leq \Pr\left[X^k_j < \beta \middle| E_M\right] + \frac{1}{n^2}, \end{align}\] where the last line follows from Lemma 5. Now, recall that the interval mapping to \(B_j\) in the \(k\)-th phase is \(\left(r_{\left((j-1)\cdot \frac{\beta^k}{8} \, : \, t_0\right)}, r_{\left(j\cdot \frac{\beta^k}{8} \, : \, t_0\right)}\right]\), since \(B_j\) in the \(k\)-th phase is formed from \(\beta^{k-1}\) buckets from the first phase, each of which received \(\beta/8\) requests in the learning phase. Let \(\mathcal{B}_j = \left\{j' \cdot \frac{\beta}{8} : (j-1) \cdot \frac{\beta^k}{8} \leq j' \cdot \frac{\beta}{8} \leq j \cdot \frac{\beta^k}{8}\right\}\) be the set of indices of initial buckets that are combined to form the \(j\)-th bucket in the \(k\)-th phase. Recall that for \(j' \in \left[\beta^{\rho}\right]\), \(Y_{j'}\) is the number of non-learning phase requests between the endpoints of the \(j'\)-th initial bucket. Therefore, the number of non-learning phase requests between the endpoints of \(j\)-th bucket in the \(k\)-th phase is \(\sum_{j' \in \mathcal{B}_j} Y_{j'}\). Note that these \(Y_{j'}\) are fixed after the learning phase. Further, conditioned on \(E_M\), each \(Y_{j'}\) is at least \(\frac{n \beta}{16t_0}\). Thus, conditioned on \(E_M\), \(\sum_{j' \in \mathcal{B}_j} Y_{j'} \geq \frac{n \beta}{16t_0} \cdot \beta^{k-1} = \frac{n \beta^k}{16t_0}\).

Now, given that the \(Y_{j'}\) are fixed before the \(k\)-th phase, recall that the number of requests from the \(k\)-th phase that appear in the \(j\)-th bucket will be some fraction of \(\sum_{j' \in \mathcal{B}_j} Y_{j'}\). Since the requests arrive in random order, and there are \(n-t_0\) total non-learning phase requests and \(t_k - t_{k-1}\) requests in the \(k\)-th phase, the fraction of the \(\sum_{j' \in \mathcal{B}_j} Y_{j'}\) requests that appear in the \(k\)-th phase is distributed according to the hypergeometric distribution with parameters \(n-t_0\), \(\sum_{j' \in \mathcal{B}_j} Y_{j'}\), and \(t_k - t_{k-1}\). So, conditioned on the \(Y_{j'}\) being fixed before the \(k\)-th phase, \(X^k_j \sim \textrm{Hypergeometric}\left(n-t_0, \sum_{j' \in \mathcal{B}_j} Y_{j'}, t_k - t_{k-1}\right)\).

Therefore, \[\begin{align} \Pr\left[X^k_j < \beta \middle| E_M\right] &= \Pr\left[X^k_j \sim \textrm{Hypergeometric}\left(n-t_0, \sum_{j' \in \mathcal{B}_j} Y_{j'}, t_k - t_{k-1}\right) < \beta\middle| E_M\right]\\ &\leq \Pr\left[X^k_j \sim \textrm{Hypergeometric}\left(n-t_0, \frac{n\beta^{k}}{16t_0}, t_k - t_{k-1}\right) < \beta\right], \end{align}\] where the second line follows from the fact that, for \(K \geq K'\), stochastic dominance gives \[\Pr\left[X \sim \textrm{Hypergeometric}(N,K,m) \leq \ell\right] \leq \Pr\left[X \sim \textrm{Hypergeometric}(N,K',m) \leq \ell\right] .\]

Then, hypergeometric tail bounds described in Lemma 1 allow us to bound this probability: let \[\begin{align} \mu = \frac{t_k - t_{k-1}}{n-t_0} \cdot \frac{n\beta^k }{16t_0} > \frac{t_k - t_{k-1}}{16t_0} \;\cdot \beta^k \geq \frac{3\beta^{\rho+1-k}(\beta-1)}{16 \cdot \frac{\beta^{\rho+1}}{8}} \cdot \beta^k =\frac{3}{2}(\beta-1)\geq \frac{5}{4}\beta, \end{align}\] where the second inequality follows from \(n \geq 4\beta^{\rho+1}\). Additionally, let \(\delta = 1-\frac{\beta}{\mu} \geq 1 - \frac{\beta}{\frac{5}{4}\beta} = \frac{1}{5}\). Then, we have \[\begin{align} &\Pr\left[X \sim \textrm{Hypergeometric}\left(n-t_0, \frac{\beta^k n}{16t_0}, t_k - t_{k-1}\right) < \beta\right]\\ = \;&\Pr\left[X \sim \textrm{Hypergeometric}\left(n-t_0, \frac{\beta^k n}{16t_0}, t_k - t_{k-1} \right) < (1-\delta) \cdot \mu \right]\\ \leq \;&\exp\left(-\frac{\delta^2 \mu}{2}\right)\\ \leq \;&\exp\left(-\frac{\mu}{50}\right)\\ \leq \;&\exp\left(-\frac{\beta}{40}\right)\\ \leq \;&\frac{1}{n^2}, \end{align}\] where the third line follows from Lemma 1, the fourth line follows from \(\delta \geq \frac{1}{5}\), the fifth line follows from \(\mu \geq \frac{5}{4}\beta\), and the last line follows from from \(\beta \geq 500 \log n\). So, \[\begin{align} \Pr\left[X^k_j < \beta\right] &\leq \Pr\left[X^k_j \sim \textrm{Hypergeometric}\left(n-t_0, \frac{\beta^k n}{16t_0}, t_k - t_{k-1}\right) < \beta \middle| E_M \right] + \Pr\left[\bar{E}_M\right]\\ &\leq \frac{1}{n^2} + \frac{1}{n^2} = \frac{2}{n^2}. \end{align}\]

Therefore, we conclude \[\begin{align} \Pr[F] &= 1 - \Pr\left[\cup_{k \in [\rho]}\cup_{j \in \left[\beta^{\rho+1-k}\right]} \left\{X^k_j < \beta\right\}\right] \\ &\geq 1-\sum_{k \in [\rho]} \sum_{j \in \left[\beta^{\rho+1-k}\right]} \Pr\left[X^k_j < \beta\right] \\ &\geq 1 - \frac{2}{n^2} \sum_{k \in [\rho]} \beta^{\rho+1-k}\\ &\geq 1 - \frac{2}{n^2} \beta^{\rho+1}\\ &\geq 1-\frac{2}{n}. \end{align}\] ◻

Proof. First, note that \(\Pr[A_{\rho}] \geq \Pr\left[F\right]\). This follows from the fact that the number of future requests at the end of a phase is equal to three times the number of buckets, the fact that there are at most \(2\) requests outside of the buckets, and \(F\) which guarantees that, in each phase, each bucket receives at least as many requests as it began the phase with, so no bucket has more than one unmatched request. Therefore, we have \[\begin{align} \Pr\left[A_{\rho}\right] \geq \Pr\left[F\right] \geq 1-2/n, \end{align}\] where the last inequality follows from Lemma 6. ◻

Proof. Let \(r_{(1\,: \, n)} \leq \dots \leq r_{(n\,: \, n)}\) be the order statistics of the \(n\) samples. Then: \[\begin{align} &\Pr\left[ |\{t \in \{ t_0+1, \dots, n\}: i(t) \in \{L, R\} \}| \leq 32\beta^2 \right] \\ \geq_{(1)} \;&\Pr\left[ |\{t \in \{ t_0+1, \dots, n\}: i(t) \in \{L, R\} \}| \leq \frac{n\beta}{t_0} \right] \\ \geq \;&\Pr\left[ \min_{t \in [t_0]}r_t \leq r_{\left(\frac{n\beta}{2t_0}\,: \, n\right)}, \max_{t \in [t_0]}r_t \geq r_{\left(n - \frac{n\beta}{2t_0}\,: \, n\right)} \right] \\ \geq \;&1 - \Pr\left[ \min_{t \in [t_0]}r_t > r_{\left(\frac{n\beta}{2t_0}\,: \, n\right)}\right] - \Pr\left[ \max_{t \in [t_0]}r_t < r_{\left(n - \frac{n\beta}{2t_0}\,: \, n\right)}\right] \\ \geq_{(2)} \;&1 - 2\exp\left(- \frac{t_0\cdot \frac{n\beta}{2t_0}}{n} \right)\\ = \;&1- 2\exp\left(-\beta/2\right)\\ \geq_{(3)} \;&1 - \frac{2}{n}, \end{align}\] where (1) follows from \(n \leq 4\beta^{\rho+2}\) and \(t_0= \frac{\beta^{\rho+1}}{8}\) implies \(\frac{n}{t_0} \leq 32\beta\), (2) is due to 8 for \(k = t_0\) and \(m = \frac{n \beta}{2t_0}\), and (3) from \(\beta = \left\lfloor 500 \log n\right\rfloor\) and \(n \geq 2\). ◻

Proof sketch. As in the proof of 6, we use 3 to give a bound on the expected number of requests in each bucket. Specifically, we show, \(E\left[X^k_j\right] \leq \frac{1}{n} + \begin{aligned} \begin{cases} \frac{4n}{\beta^{\rho}} , \quad &\textrm{ if } k=1\\ 12\beta , & \textrm{else} \end{cases} \end{aligned}\). We then apply a Chernoff bound to get the high probability result. ◻

Proof. For any instance \(I = \left(\left\{r_{(1)}, \dots, r_{(n)}\right\}, \pi\right)\), \[\begin{align} \sum_{j \in \left[\beta^{\rho}\right]} (\sup{I^1_j} - \inf{I^1_j}) = r_{(t_0: t_0)} - r_{(1: t_0)} \leq r_{(n:n)} - r_{(1:n)} = \max_t r_t - \min_t r_t \end{align}\] ◻

Proof. By Lemma [lem:32ratio32of32algorithmic32framework], it suffices to show that Algorithm 1, with the subroutine FindIntialBuckets defined by Algorithm 3 and with learning parameter \(t_0= \frac{\beta^{\rho+1}}{8}\), satisfies [cond: probability of hitting wall,cond: few arrivals in any one bucket,cond: buckets have bounded length]. 1 is shown by 7, 2 by 9 10, and 3 by 11. ◻

Proof. For any \(n \geq 4, \epsilon \in (0,1)\), we define the following multi-sets, both of cardinality \(n\): \[\begin{align} I_1 = \{ \underbrace{0, \dots, 0}_{n-4}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2} + \epsilon, \frac{1}{2} + \epsilon \}, \quad I_2 = \{ \underbrace{0, \dots, 0}_{n-4}, \frac{1}{2}, \frac{1}{2} + \epsilon, 1-\epsilon, 1 \}. \end{align}\] We show the following two points, from which the statement follows:

1. On instance \(I_1\), we show that any randomized algorithm with bounded competitive ratio must match \(\left(\frac{1}{2} + \epsilon \right)\)-requests to \(\frac{1}{2}\)-requests with probability \(0\),

2. Any algorithm that satisfies (1) has an unbounded competitive ratio on instance \(I_2\).

For any random permutation \(\pi(I) = (r_1, r_2, \dots, r_n)\), we define as \(M_t(\pi(I))\) the matching after time step \(t\) of the algorithm. We define the event that two requests in locations \(\frac{1}{2}, \frac{1}{2} + \epsilon\) arrive before other non \(0\)-requests have arrived: \[\begin{align} E_{order}(\pi(I)) = \{ \exists t_1, t_2 \in [n]: r_{t_1} = \frac{1}{2}, r_{t_2} = \frac{1}{2} + \epsilon, r_{t'} = 0 \;\forall t' \in [\max(t_1, t_2)] \setminus \{t_1, t_2\} \}. \end{align}\] We also define the event that these two requests are matched to each other: \[\begin{align} E_{match}(\pi(I)) = \{\exists t_1, t_2 \in [n]: r_{t_1} = \frac{1}{2}, r_{t_2} = \frac{1}{2} + \epsilon, r_{t'} = 0 \forall t' \in [\max(t_1, t_2)] \setminus \{t_1, t_2\}, \\ \{r_{t_1}, r_{t_2}\} \in M_{\max(t_1, t_2)}(\pi(I))\}. \end{align}\] We start with (1). Note that by [lemma:32OPT32structure] the optimal matching matches all the \(0\)-requests to each other (since \(n-4\) is even), the \(\frac{1}{2}\)-requests to each other, and the \(\left( \frac{1}{2} + \epsilon \right)\)-requests to each other, therefore \(\mathop{\mathrm{\mathbb{E}}}_{\pi}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(\pi(I_1)) \right] = 0\).

Let \(p = \Pr_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ E_{match}(\pi(I_1)) \middle| E_{order}(\pi(I_1)) \right]\), then the algorithm finds a matching with the following cost: \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_1)) \right] \\ \geq \;&\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_1)) \middle| E_{order}(\pi(I_1)) \right] \cdot \Pr_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ E_{order}(\pi(I_1)) \right] \\ \geq \;&\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_1)) \middle| E_{order}(\pi(I_1)) \right] \cdot \frac{1}{6} \\ \geq \;&\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_1)) \middle| E_{order}(\pi(I_1)), E_{match}(\pi(I_1)) \right] \cdot \Pr_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ E_{match}(\pi(I_1)) \middle| E_{order}(\pi(I_1))\right] \cdot \frac{1}{6} \\ \geq \;&\frac{\epsilon \cdot p}{6}, \end{align}\] where the first line is by tower rule, the second line is because by definition of event \(E_{order}(\pi(I_1))\), it only happens one \(\frac{1}{2}\)-request and one \(\left(\frac{1}{2} + \epsilon\right)\)-request arrive before the other two such requests which happens with probability at least \(\frac{1}{6}\) by considering all possible orders of the non \(0\)-requests, the third line is by tower rule and the fourth line is because if a \(\frac{1}{2}\)-request is matched to a \(\left( \frac{1}{2} + \epsilon \right)\)-request, then \(\mathop{\mathrm{\mathrm{\small Alg}}}\) pays at least the distance \(\epsilon\). Assume \(p > 0\), then \(\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_1)) \right] > 0\), therefore the competitive ratio is unbounded.

We proceed to show (2) by assuming \(p = 0\). Note that by [lemma:32OPT32structure], the optimal matching matches all \(0\)-requests to each other (since \(n-4\) is even), the \(\frac{1}{2}\)-request is matched to the \(\left( \frac{1}{2} + \epsilon \right)\)-request and the \((1-\epsilon)\)-request is matched to the \(1\)-request, which gives \(\mathop{\mathrm{\mathbb{E}}}_{\pi}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(\pi(I_2)) \right] = 2 \epsilon\). We have that: \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_2)) \right] \\ \geq \;&\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_2)) \middle| E_{order}(\pi(I_2)) \right] \cdot \Pr_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ E_{order}(\pi(I_2)) \right] \\ \geq \;&\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_2)) \middle| E_{order}(\pi(I_2)) \right] \cdot \frac{1}{6} \\ \geq \;&\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_2)) \middle| E_{order}(\pi(I_2)), \bar{E}_{match}(\pi(I_2)) \right] \cdot \Pr_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \bar{E}_{match}(\pi(I_2)) \middle| E_{order}(\pi(I_2)) \right] \cdot \frac{1}{6} \\ = \;&\mathop{\mathrm{\mathbb{E}}}_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(\pi(I_2)) \middle| E_{order}(\pi(I_2)), \bar{E}_{match}(\pi(I_2)) \right] \cdot \frac{1}{6} \\ = \;&\frac{1/2-\epsilon}{6} \\ = \;&\frac{1/2-\epsilon}{12 \epsilon} \cdot \mathop{\mathrm{\mathbb{E}}}_{\pi}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(\pi(I_2)) \right], \end{align}\] where the first line is by tower rule, the second line is because the \(\frac{1}{2}\), \(\left(\frac{1}{2} + \epsilon\right)\)-requests arrive before \((1-\epsilon), 1\)-requests in \(\pi(I_2)\) with probability \(\frac{1}{6}\) by reordering, the third line is by tower rule, the fourth line is because \(\Pr_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \bar{E}_{match}(\pi(I_2)) \middle| E_{order}(\pi(I_2)) \right] = \Pr_{\pi, \mathop{\mathrm{\mathrm{\small Alg}}}}\left[ \bar{E}_{match}(\pi(I_1)) \middle| E_{order}(\pi(I_1)) \right] = 1 - p = 1\) because at the arrival of the \(\frac{1}{2}\), \(\left( \frac{1}{2} + \epsilon \right)\)-requests in \(\pi(I_2)\) we have no information that distinguishes it from \(\pi(I_1)\), therefore the algorithm matches \(\frac{1}{2}\) to \(\left( \frac{1}{2} + \epsilon \right)\) with the same probability and by assumption \(p = 0\), the fifth line is because if the \(\frac{1}{2}\)-request is not matched to the \(\left( \frac{1}{2} + \epsilon \right)\)-request, then it will be matched to either the \(1-\epsilon\) or the \(1\)-request and the cost will be at least \(\frac{1}{2} - \epsilon\), and the sixth line due to \(\mathop{\mathrm{\mathbb{E}}}_{\pi}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(\pi(I_2)) \right] = 2\epsilon\).

Then the ratio is unbounded as \(\epsilon \rightarrow 0\). ◻

Proof. Let \(S_i = \{s_1, s_2, \dots, s_i\}\) and \(R_i = \{r_1, r_2, \dots, r_i\}\) for any \(i \in [n+1]\). For any \(x \in [0,1]\) we define the following random variable: \[Z_n(x) = \sum_{i \in [n]}\mathbb{1}\{s_i \leq x\} - \sum_{i \in [n]}\mathbb{1}\{r_i \leq x\}.\] Notice that: \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}_{s_{n+1} \sim \mathcal{D}, r_{n+1} \sim \mathcal{D}}\left[ Z_{n+1}(x) \middle| Z_n(x) \right] \\ =\;&\mathop{\mathrm{\mathbb{E}}}_{s_{n+1} \sim \mathcal{D}, r_{n+1} \sim \mathcal{D}}\left[ Z_{n}(x) + \mathbb{1}\{s_i \leq x\} - \mathbb{1}\{r_i \leq x\} \middle| Z_n(x) \right] \\ =\;&Z_n(x) + \mathop{\mathrm{\mathbb{E}}}_{s_{n+1} \sim \mathcal{D}, r_{n+1} \sim \mathcal{D}}\left[ \mathbb{1}\{s_{n+1} \leq x\} - \mathbb{1}\{r_{n+1} \leq x\} \middle| Z_n(x) \right] \\ =\;&Z_n(x) + \mathop{\mathrm{\mathbb{E}}}_{s_{n+1} \sim \mathcal{D}, r_{n+1} \sim \mathcal{D}}\left[ \mathbb{1}\{s_{n+1} \leq x\} - \mathbb{1}\{r_{n+1} \leq x\} \right] \\ =\;&Z_n(x), \end{align}\] where the first line is by definition of \(Z_{n+1}(x)\), the second line id due to conditioning on \(Z_n(x)\), the third line is because \(s_{n+1}, r_{n+1}\) are independent of \(S_n, R_n\) and therefore independent of \(Z_n(x)\) and the fourth line is because \(\mathop{\mathrm{\mathbb{E}}}_{s_{n+1} \sim \mathcal{D}}\left[ \mathbb{1}\{s_{n+1} \leq x\} \right] = \Pr_{s_{n+1} \sim \mathcal{D}}\left[ s_{n+1} \leq x \right] = \Pr_{r_{n+1} \sim \mathcal{D}}\left[ r_{n+1} \leq x \right] = \mathop{\mathrm{\mathbb{E}}}_{r_{n+1} \sim \mathcal{D}}\left[ \mathbb{1}\{r_{n+1} \leq x\} \right]\). This implies: \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}_{S_{n+1} \sim \mathcal{D}^{n+1}, R_{n+1} \sim \mathcal{D}^{n+1}}\left[ |Z_{n+1}(x)| \right] \\ \geq \;&| \mathop{\mathrm{\mathbb{E}}}_{S_{n+1} \sim \mathcal{D}^{n+1}, R_{n+1} \sim \mathcal{D}^{n+1}}\left[ Z_{n+1}(x) \right] | \\ =\;&| \mathop{\mathrm{\mathbb{E}}}_{S_{n} \sim \mathcal{D}^{n}, R_{n} \sim \mathcal{D}^{n}}\left[ \mathop{\mathrm{\mathbb{E}}}_{s_{n+1} \sim \mathcal{D}, r_{n+1} \sim \mathcal{D}}\left[ Z_{n+1}(x) \middle| Z_n(x) \right] \right] | \\ =\;&| \mathop{\mathrm{\mathbb{E}}}_{S_{n} \sim \mathcal{D}^{n}, R_{n} \sim \mathcal{D}^{n}}\left[ Z_n(x) \right] |, \end{align}\] where the first line is by Jensen since \(\phi(x) = |x|\) is convex, the second line is by tower rule and the third line is due to (1). Then we have: \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}_{S_{n+1} \sim \mathcal{D}^{n+1}, R_{n+1} \sim \mathcal{D}^{n+1}}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(S_{n+1}, R_{n+1})\right] \\ =\;&\mathop{\mathrm{\mathbb{E}}}_{S_{n+1} \sim \mathcal{D}^{n+1}, R_{n+1} \sim \mathcal{D}^{n+1}}\left[ \int_0^1{|Z_{n+1}(x)|}\,dx \right] \\ =\;&\int_0^1{\mathop{\mathrm{\mathbb{E}}}_{S_{n+1} \sim \mathcal{D}^{n+1}, R_{n+1} \sim \mathcal{D}^{n+1}}\left[|Z_{n+1}(x)| \right]}\,dx \\ \geq \;&\int_0^1{\mathop{\mathrm{\mathbb{E}}}_{S_{n} \sim \mathcal{D}^{n}, R_{n} \sim \mathcal{D}^{n}}\left[|Z_{n}(x)| \right]}\,dx \\ =\;&\mathop{\mathrm{\mathbb{E}}}_{S_{n} \sim \mathcal{D}^{n}, R_{n} \sim \mathcal{D}^{n}}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(S_n, R_n)\right], \end{align}\] where the first line is because \(\mathop{\mathrm{\mathrm{\small Opt}}}(S_{n+1}, R_{n+1})\) matches the requests of \(S_{n+1}\) to those of \(R_{n+1}\) greedily from left to right, and for every \(x \in [0,1]\), we pay it as many times as \(x\) is between a matched pair, or equivalently as large as the imbalance of points from \(S_{n+1}\) are to the left of \(x\) compared the points of \(R_{n+1}\), the second line is by Fubini-Tonelli, the third line is by (2). ◻

Proof of 12. Let \(R_2 = R \setminus R_1\) and \(S_2 = S \setminus S_1\). Note that \(|R_2| = n - |R_1| = |S_1|\) and \(|S_2| = n - |S_1| = |R_1|\). Let \(n_S = |S_1|\) and \(n_R = |R_1| = n - n_S\). Then we have: \[\begin{align} &\mathop{\mathrm{\mathbb{E}}}_{S \sim \mathcal{D}^n, R \sim \mathcal{D}^n,}\left[ \mathop{\mathrm{\mathrm{\small Osr}}}(S, R, \pi) \right] \\ = \;&\mathop{\mathrm{\mathbb{E}}}_{S_1 \sim \mathcal{D}^{n_S}}[ \mathop{\mathrm{\mathbb{E}}}_{R_2 \sim \mathcal{D}^{n_S}}\left[ \mathcal{A}(S_1, R_2) \right] ] + \mathop{\mathrm{\mathbb{E}}}_{R_1 \sim \mathcal{D}^{n_R}}[ \mathop{\mathrm{\mathbb{E}}}_{S_2 \sim \mathcal{D}^{n_R}}\left[ \mathcal{A}(R_1, S_2) \right] ] \\ \leq \;&a \cdot \mathop{\mathrm{\mathbb{E}}}_{S_1 \sim \mathcal{D}^{n_S}}[ \mathop{\mathrm{\mathbb{E}}}_{R_2 \sim \mathcal{D}^{n_S}}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(S_1, R_2) \right] ] + a \cdot \mathop{\mathrm{\mathbb{E}}}_{R_1 \sim \mathcal{D}^{n_R}}[ \mathop{\mathrm{\mathbb{E}}}_{S_2 \sim \mathcal{D}^{n_R}}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(R_1, S_2) \right] ] \\ = \;&a \cdot \mathop{\mathrm{\mathbb{E}}}_{S_1 \sim \mathcal{D}^{n_S}, R_2 \sim \mathcal{D}^{n_S}}[ \mathop{\mathrm{\mathrm{\small Opt}}}(S_1, R_2) ] + a \cdot \mathop{\mathrm{\mathbb{E}}}_{S_2 \sim \mathcal{D}^{n_R}, R_1 \sim \mathcal{D}^{n_R}}[ \mathop{\mathrm{\mathrm{\small Opt}}}(R_1, S_2) ] \\ \leq \;&a \cdot \mathop{\mathrm{\mathbb{E}}}_{S_1 \sim \mathcal{D}^{n}, R_2 \sim \mathcal{D}^{n}}[ \mathop{\mathrm{\mathrm{\small Opt}}}(S_1, R_2) ] + a \cdot \mathop{\mathrm{\mathbb{E}}}_{S_2 \sim \mathcal{D}^{n}, R_1 \sim \mathcal{D}^{n}}[ \mathop{\mathrm{\mathrm{\small Opt}}}(R_1, S_2) ] \\ = \;&2a \cdot \mathop{\mathrm{\mathbb{E}}}_{S \sim \mathcal{D}^{n}, R \sim \mathcal{D}^{n}}[ \mathop{\mathrm{\mathrm{\small Opt}}}(S, R) ], \end{align}\] where the first line is by definition of 4, the second line is due to the assumption for \(\mathcal{A}\), the fourth line is due to 13, and the fifth line is by renaming the sets of requests. ◻

Proof of [thm:32ratio32for32two32sided32bipartite32arrivals]. For general metrics we use 4 with \(\mathcal{A}_1\), which has ratio \(a = O(\log{\log{\log{n}}})^2\) by 14. For tree metrics we use 4 with \(\mathcal{A}_2\), which has ratio \(a = 9\) by 15. ◻

Proof. We have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \in J} \mathrm{charge}(t) \middle| E_{bad} \right] &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t, r_{\tau(t)} \in J} \mathrm{charge}(t) \middle| E_{bad} \right] \\ &\leq \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t, r_{\tau(t)} \in J} \frac{\sup{J} - \inf{J}}{2} \middle| E_{bad} \right] \\ &= \frac{n}{2} \cdot (\sup{J} - \inf{J}), \end{align}\] where the first line is because if \(\tau(t) \notin J\), then \(\mathrm{charge}(t) = 0\) by definition, the second line because if both \(r_t, r_{\tau(t)} \in J\), then \(\mathrm{charge}(t) = \frac{|r_t - r_{\tau(t)}|}{2} \leq \frac{\sup{J} - \inf{J}}{2}\) by definition, and the third line is by summing \(n\) times. The statement follows since \(n/2 \leq n\). ◻

Proof. We have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}&_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]} \mathrm{cost}(t) \middle| \bar{E}_{bad} \right] = \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [t_{\rho}]} \mathrm{cost}(t) + \sum_{t \in [n] \setminus [t_{\rho}]} \mathrm{cost}(t) \middle| \bar{E}_{bad} \right] \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [t_{\rho}]: i(t) \in \{L,R\}} \mathrm{cost}(t) + \sum_{t \in [t_{\rho}]: i(t) \notin \{L,R\}} \mathrm{cost}(t) + \sum_{t \in [n] \setminus [t_{\rho}]} \mathrm{cost}(t) \middle| \bar{E}_{bad} \right]. \end{align}\] For the first term we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}&_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [t_{\rho}]: i(t) \in \{L,R\}} \mathrm{cost}(t) \middle| \bar{E}_{bad} \right] \leq \\ &\leq \sum_{k=1}^{\rho} \mathop{\mathrm{\mathbb{E}}}\left[ \sum_{j = 1}^{\beta^{\rho + 1 - k}} | \{ t \in \{t_{k-1} + 1, \dots, t_k \}: i(t) = j\} | \cdot ( \sup{I^k_j} - \inf{I^k_j} ) \middle| \bar{E}_{bad} \right] \\ &\leq \mathop{\mathrm{\mathbb{E}}}\left[ \sum_{j = 1}^{\beta^{\rho}} | \{ t \in \{t_{t_0} + 1, \dots, t_1 \}: i(t) = j\} | \cdot ( \sup{I^1_j} - \inf{I^1_j} ) \middle| \bar{E}_{bad} \right] \\ & \qquad + \sum_{k=2}^{\rho} \mathop{\mathrm{\mathbb{E}}}\left[ \sum_{j = 1}^{\beta^{\rho + 1 - k}} | \{ t \in \{t_{k-1} + 1, \dots, t_k \}: i(t) = j\} | \cdot ( \sup{I^k_j} - \inf{I^k_j} ) \middle| \bar{E}_{bad} \right] \\ &\leq \mathop{\mathrm{\mathbb{E}}}\left[32 \beta^2 \cdot ( \sup{I^1_j} - \inf{I^1_j} ) \middle| \bar{E}_{bad} \right] + \sum_{k=2}^{\rho} \mathop{\mathrm{\mathbb{E}}}\left[ \sum_{j = 1}^{\beta^{\rho + 1 - k}} 24 \beta \cdot ( \sup{I^k_j} - \inf{I^k_j} ) \middle| \bar{E}_{bad} \right] \\ &= 32 \beta^2 \cdot \mathop{\mathrm{\mathbb{E}}}\left[ \sup{I^1_j} - \inf{I^1_j} \middle| \bar{E}_{bad} \right] + \sum_{p=1}^{\rho} 12 \beta \cdot \mathop{\mathrm{\mathbb{E}}}\left[ \sum_{j = 1}^{\beta^{\rho + 1 - k}} ( \sup{I^k_j} - \inf{I^k_j} ) \middle| \bar{E}_{bad} \right] \\ &\leq 96\beta^2 \cdot \mathop{\mathrm{\mathbb{E}}}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \middle| \bar{E}_{bad} \right] + \sum_{k=2}^{\rho} 36 \beta \cdot \mathop{\mathrm{\mathbb{E}}}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \middle| \bar{E}_{bad} \right] \\ &= (96\beta^2 +36 \rho \beta) \cdot \mathop{\mathrm{\mathbb{E}}}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \middle| \bar{E}_{bad} \right], \end{align}\] where the first line is due to \(\bar{E}_{bad} \subseteq \bar{A}_{\rho}\), which implies our algorithm is not forced to make arbitrary assignments in the first \(\rho\) phases, and each request that arrives in bucket \(B_j\) pays at most the length of \(I^k_j\) as matching cost. The second line is due to splitting the sum into the cost of the first phase and the cost of the subequent phases. The third line is due \(\bar{E}\) implies \(\bar{E}_a\), i.e. no bucket in the first phase receives more than \(32\beta^2\) requests, and no bucket in a later phase receives more than \(24\beta\) requests. The third line is by linearity of expectation, the fourth line is due to 3.

For the second term we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [t_{\rho}]: i(t) \in \{L, R\}} \mathrm{cost}(t) \middle| \bar{E}_{bad} \right] &\leq \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [t_{\rho}]: i(t) \in \{L, R\}} \left( \max_{t' \in [n]}r_{t'} - \min_{t' \in [n]}r_{t'} \right) \middle| \bar{E}_{bad} \right] \\ &\leq \beta^2 \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \middle| \bar{E}_{bad} \right], \end{align}\] where the first line is because \(\mathrm{cost}(t) \leq |r_t - r_{\tau{t}}| \leq \max_{t' \in [n]}r_{t'} - \min_{t' \in [n]}r_{t'}\), the second line is due to that fact \(\bar{E}_{bad} \subseteq \bar{E}_o\), i.e., at most \(\beta^2\) requests arrive outside of the buckets.

Similarly, for the third term we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n] \setminus [t_{\rho}]} \mathrm{cost}(t) \middle| \bar{E}_{bad} \right] &\leq \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n] \setminus [t_{\rho}]} \left( \max_{t' \in [n]}r_{t'} - \min_{t' \in [n]}r_{t'} \right) \middle| \bar{E}_{bad} \right] \\ &= \left( n - t_{\rho} \right) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \middle| \bar{E}_{bad} \right] \\ &= 3 \beta \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \middle| \bar{E}_{bad} \right], \end{align}\] where \(n-t_{\rho} = 3\beta\) follows from the definition of \(t_{\rho}\). Also we have: \[\begin{align} 1 - \frac{\rho + 4}{n} \geq 1 - \frac{\log n + 4}{n} \geq \frac{1}{4}, \end{align}\] where the first inequality is because \(\rho \leq \frac{\log{\frac{n}{\beta^\rho}}}{\log{\beta}} \leq \log{n}\), and the second inequality is by assumption \(n \geq 2 \cdot 10^6\).

By substituting Equations (2a), (2b), (2c) to (2) we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(I) \middle| \bar{E}_{bad} \right] &\leq \left(96\beta^2 + 36\beta\rho + 3\beta + \beta^2 \right) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \middle| \bar{E}_{bad} \right] \\ &\leq \left(96\beta^2 +36\beta\rho + 3\beta + \beta^2 \right) \cdot \frac{\mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \right]}{\Pr\left[ \bar{E}_{bad} \right]} \\ &\leq \left(96\beta^2 +36\beta\rho + 3\beta + \beta^2 \right) \cdot \frac{\mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \right]}{1 - \frac{\rho + 4}{n}} \\ &\leq \left(288\beta^2 + 144\beta\rho + 12\beta + 4\beta^2 \right) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_{t} - \min_{t \in [n]}r_{t} \right], \end{align}\] where the second equality is by tower rule, the third line is due to \(\Pr\left[ \bar{E}_{bad} \right] \geq 1 - \frac{6\rho\beta + 2}{n}\) by 1 2 3 and union bound, and the fourth line is due to Equation (2d). Then the statement follows from \(\beta, \rho = O(\log{n})\). ◻

Proof. We have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}&_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \notin J}\mathrm{charge}(t) \right] = \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t < \inf{J}}\mathrm{charge}(t) \right] + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t > \sup{J}}\mathrm{charge}(t) \right] \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t < \inf{J}} (\sup{J} - r_t) \right] + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t > \sup{J}}( r_t - \inf{J}) \right], \end{align}\] where the first line is by linearity of expectation, and the second line is by definition of \(\mathrm{charge}(t)\). For the first term we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}&_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t < \inf{J}} (\sup{J} - r_t) \right] = \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t < \inf{J}} (\inf{J} - r_t + \sup{J} - \inf{J} ) \right] \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t < \inf{J}} (\inf{J} - r_t) \right] + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]}\mathbb{1}\{r_t < \inf{J}\} \right] \cdot (\sup{J} - \inf{J}) \\ &\leq \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]} (\inf{J} - r_t)^+ \right] + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]} \frac{1}{n} \right] \cdot (\sup{J} - \inf{J}) \\ &= n \cdot \mathop{\mathrm{\mathbb{E}}}_{r \sim \mathcal{D}}\left[ (\inf{J} - r)^+ \right] + (\sup{J} - \inf{J}), \end{align}\] where the first line is by adding and subtracting \(\inf{J}\), the second line is due to linearity of expectation, the third line is because \(\Pr_{r \sim \mathcal{D}}\left[ r < \inf{J} \right] \leq 1/n\) by definition, and the fourth line is because we sum \(n\) times. For the second term we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}&_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t > \sup{J}}( r_t - \inf{J}) \right] = \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t > \sup{J}} (r_t - \sup{J} + \sup{J} - \inf{J} ) \right] \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t > \sup{J}} (r_t - \sup{J}) \right] + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]}\mathbb{1}\{r_t > \sup{J}\} \right] \cdot (\sup{J} - \inf{J}) \\ &\leq \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]} (r_t - \sup{J})^+ \right] + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]} \frac{1}{n} \right] \cdot (\sup{J} - \inf{J}) \\ &= n \cdot \mathop{\mathrm{\mathbb{E}}}_{r \sim \mathcal{D}}\left[ (r - \sup{J})^+ \right] + (\sup{J} - \inf{J}), \end{align}\] where the first line is by adding and subtracting \(\sup{J}\), the second line is due to linearity of expectation, the third line is because \(\Pr_{r \sim \mathcal{D}}\left[ r > \sup{J} \right] \leq 1/n\) by definition, and the fourth line is because we sum \(n\) times. We obtain the statement by substituting Equations (1a), (1b) to (1). ◻

Proof. First, we have, \((1-p)^n = e^{n \log(1-p)} \le e^{-np} \leq 1 - np / 2\) where the last inequality is since \(np \leq 1\). Moreover, \(p^n \le p (1/n)^{n-1} \leq \frac{p}{n} \le \frac{np}{4}\) where the first inequality is since \(0\le p\le 1/n\), the second is since \(n\ge 2\), and the third since \(n^2 \geq 4\). Combining these bounds gives \(g(p) \geq 1 - np/4 - (1 - np/2) \ge np/4\). ◻

Proof. We have \(p^n\le(1-1/n)^n \leq 1/e\) and \((1-p)^n\le(1-1/n)^n \leq 1/e\), so \(g(p)\ge 1-2/e\). ◻

Proof of [lem:maxminregions]. Note that \[\begin{align} \mathbb{E}[\max_{t \in [n]} r_t-\min_{t \in [n]} r_t] & =\int_0^1\Pr[\max_{t \in [n]} r_t>x]\,dx-\int_0^1\Pr[\min_{t \in [n]} r_t>x]\,dx \\ & =\int_0^1(1 - F(x)^n)\,dx-\int_0^1(1-F(x))^n\,dx \\ & =\int_0^1 \Big(1-F(x)^n-(1-F(x))^n\Big)\,dx. \end{align}\]

We now split the integral into three regions.

Left region \([0,\inf{J}]\). For \(x<\inf{J}\), we have \(F(x)\le 1/n\), so by Claim 1, \[g(F(x))\ge \frac{nF(x)}{4}.\] Hence \[\int_0^{\inf{J}} g(F(x))\,dx \ge \frac{n}{4}\int_0^{\inf{J}}F(x)\,dx = \frac{n}{4} \int_0^{\inf{J}}\Pr_{r \sim \mathcal{D}}[r\le x]\,dx = \frac{n}{4} \mathop{\mathrm{\mathbb{E}}}_{r \sim \mathcal{D}}\left[ (\inf{J} - r)^+ \right].\]

Middle region \([\inf{J},\sup{J}]\). For \(x\in(\inf{J},\sup{J})\), we have \(F(x)\in[1/n,\,1-1/n]\), so by Claim 2, \(g(F(x))\ge 1-\frac{2}{e}.\) Therefore \[\int_{\inf{J}}^{\sup{J}} g(F(x))\,dx \ge \Bigl(1-\frac{2}{e}\Bigr)(\sup{J}-\inf{J}).\]

Right region \([\sup{J},1]\). For \(x>\sup{J}\), we have \[g(F(x)) = g(1 - F(x)) \ge \frac{n(1-F(x))}{4} = \frac{n}{4}\Pr[r>x].\] where the first equality is since \(g(p) = g(1-p)\) for all \(p\) and the inequality by Claim 1 and since \(1-F(x)\le 1/n\). Thus \[\int_{\sup{J}}^1 g(F(x))\,dx \ge \frac{n}{4}\int_{\sup{J}}^1\Pr[r>x]\,dx = \frac{n}{4} \mathop{\mathrm{\mathbb{E}}}_{r \sim \mathcal{D}}\left[ (r - \sup{J})^+ \right].\] By combining the three regions, we get the desired inequality. ◻

Proof of [lem:32upper32bound32cost32of32framework]. For \(n \leq 2 \cdot 10^6\): \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(I) \right] = \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]}\mathrm{cost}(t) \right] \leq n \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_t - \min_{t \in [n]}r_t \right] \leq 2\cdot10^6 \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \mathop{\mathrm{\mathrm{\small Opt}}}(I) \right], \end{align}\] where the equality is by definition of \(\mathrm{cost}(t)\), the first inequality is because \(\mathrm{cost}(t) \leq \max_{t\in[n]}r_t - \min{t \in [n]}r_t\) for any \(t \in [n]\) and the second inequality is by assumption on \(n \geq 2 \cdot 10^6\) and [lemma:32opt32pays32expected32rightmost32minus32expected32leftmost]. The remaining proof assumes \(n \geq 2 \cdot 10^6\): \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \mathop{\mathrm{\mathrm{\small Alg}}}(I) \right] = \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]}\mathrm{cost}(t) \right] \leq \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]}\mathrm{charge}(t) \right], \end{align}\] where the equality is because we sum the cost paid in each time step \(t\) over all \(t \in [n]\) and the inequality is because for all \(t \in [n]\), we have \(\mathrm{cost}(t) + \mathrm{cost}(\tau(t)) \leq \mathrm{charge}(t) + \mathrm{charge}(\tau(t))\) by definition. By linearity of expectation: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]}\mathrm{charge}(t) \right] = \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \in J}\mathrm{charge}(t) \right] + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \notin J}\mathrm{charge}(t) \right]. \end{align}\] For the first term we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}&_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \in J}\mathrm{charge}(t) \right] \leq \\ &\leq \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \in J}\mathrm{charge}(t) \middle| E_{bad} \right] \cdot \frac{6\rho \beta + 2}{n} + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \in J}\mathrm{charge}(t) \middle| \bar{E}_{bad} \right] \\ &\leq \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \in J}\mathrm{charge}(t) \middle| E_{bad} \right] \cdot \frac{6\rho \beta + 2}{n} + \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \in J}\mathrm{cost}(t) \middle| \bar{E}_{bad} \right] \\ &\leq O(\log^2{n}) \cdot \left( \sup{J} - \inf{J} \right) + O\left( \log^2{n} \right) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_t - \min_{t \in [n]}r_t \right] \\ &\leq O\left( \log^2{n} \right) \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_t - \min_{t \in [n]}r_t \right], \end{align}\]. where the first line is due to \(\Pr_{I \sim \mathcal{D}^n}\left[ E_{bad} \right] \leq \Pr_{I \sim \mathcal{D}^n}\left[ \bar{A}_{\rho} \right] + \Pr_{I \sim \mathcal{D}^n}\left[ \bar{E}_{a} \right] + \Pr_{I \sim \mathcal{D}^n}\left[ \bar{E}_{o} \right] \leq \frac{6\rho \beta + 2}{n}\) by 1 2 and union bound, the second line is because for all \(t\) such that \(r_t \in J\) we have \(\mathrm{charge}(t) \leq \mathrm{cost}(t)\) by definition, the third line is due to [lem:32charge32requests32in32J32for32bad32event] [lem:32total32cost32for32good32event] which hold by assumption \(n \geq 2 \cdot 10^6\) and \(\rho, \beta = O(\log{n})\), and the fourth line is due to [lem:maxminregions]. For the second term we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \sum_{t \in [n]: r_t \notin J}\mathrm{charge}(t) \right] &\leq 2(\sup{J} - \inf{J}) + n \cdot \mathop{\mathrm{\mathbb{E}}}_{r \sim \mathcal{D}}\left[\inf_{x \in J} |r - x|\right] \\ &\leq 8 \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_t - \min_{t \in [n]}r_t \right], \end{align}\] where the first line is due to [lem:32charge32requests32outside32J], and the second is due to [lem:maxminregions]. Then we obtain the result by substituting Equations (2a), (2b) to (2) and chaining with (1). ◻

Proof. Let random variables \(r^{(1)}, \dots, r^{(n)}\) such that \(r^{(i)}\) corresponds to the \(i\)-th leftmost request and \(\mathcal{D}^{(i)}\) be its distribution. We condition on \(r^{(1)}, r^{(n)}\) and show that for any point \(x \in \left( r^{(1)}, r^{(n)} \right)\), the probability that an odd number of requests arrive between \(r^{(1)}\) and \(x\) is at least \(\frac{1}{2}\). This implies that with probability \(\frac{1}{2}\), \(x\) can be charged to \(\mathop{\mathrm{\mathrm{\small Opt}}}\). We calculate the expectation of the optimal solution as follows: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}[\mathop{\mathrm{\mathrm{\small Opt}}}(I)] = \mathop{\mathrm{\mathbb{E}}}_{r' \sim \mathcal{D}^{(1)}, r'' \sim \mathcal{D}^{(n)}}\left[ \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n | r^{(1)}, r^{(n)}}\left[\mathop{\mathrm{\mathrm{\small Opt}}}(I) \mid r^{(1)} = r', r^{(n)} = r'' \right] \right]. \end{align}\] We define the number of arrivals left of \(x\) for all \(x \in (r^{(1)}, r^{(n)})\) as \(Y_x\): \[\begin{align} Y_x &= | \{r_1, \dots, r_n\} \cap (r^{(1)}, x) | = \sum_{i \in [n]} \mathbb{1}\{ r_i \in (r^{(1)}, x) \} = \sum_{i \in [n] \setminus \{\arg\min_{t \in [n]}r_t, \arg\max_{t \in [n]}r_t\}} \mathbb{1}\{ r_i \in (r^{(1)}, x) \}. \end{align}\] Notice that for \(p_x(r') = \Pr_{r \sim \mathcal{D}}\left[r \in (r', x) \right]\): \[\begin{align} \Pr_{I \sim \mathcal{D}^n | r^{(1)}, r^{(n)}}\left[ Y_x = k \middle| r^{(1)} = r', r^{(n)} = r'' \right] = \Pr\left[ Bin(n-2, p_x(r')) = k \right] \end{align}\] because for \(i,j \in [n] \setminus \{\arg\min_{t \in [n]}r_t, \arg\max_{t \in [n]}r_t\}\) and conditional on \(r^{(1)}, r^{(n)}\), we know that indicators \(\mathbb{1}\{ r_i \in (r^{(1)}, x) \}, \mathbb{1}\{ r_j \in (r^{(1)}, x) \}\) are independent. Then we have that: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}&_{I \sim \mathcal{D}^n | r^{(1)}, r^{(n)}} \left[\mathop{\mathrm{\mathrm{\small Opt}}}(I) \mid r^{(1)} = r', r^{(n)} = r'' \right] \nonumber \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n | r^{(1)}, r^{(n)}}\left[ \sum_{i=1}^{n/2} \left( r^{(2i)} - r^{(2i-1)} \right) \middle| r^{(1)} = r', r^{(n)} = r'' \right] \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n | r^{(1)}, r^{(n)}}\left[ \int_{r'}^{r''}{\mathbb{1}\{ | \{r_1, \dots, r_n\} \cap [0, x) | \in \{1, 3, \dots, n-1\} \}} \;dx \middle| r^{(1)} = r', r^{(n)} = r'' \right] \\ &= \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n | r^{(1)}, r^{(n)}}\left[ \int_{r'}^{r''}{\mathbb{1}\{ | \{r_1, \dots, r_n\} \cap (r^{(1)}, x) | \in \{0, 2, \dots, n-2\} \}} \;dx \middle| r^{(1)} = r', r^{(n)} = r'' \right] \\ &= \int_{r'}^{r''}{\mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n | r^{(1)}, r^{(n)}}\left[ \mathbb{1}\{ Y_x \in \{0, 2, \dots, n-2\} \} \middle| r^{(1)} = r', r^{(n)} = r'' \right]} \;dx \\ &= \int_{r'}^{r''}{\Pr_{I \sim \mathcal{D}^n | r^{(1)}, r^{(n)}}\left[ Y_x \in \{0, 2, \dots, n-2\} \middle| r^{(1)} = r', r^{(n)} = r'' \right]} \;dx \\ &= \int_{r'}^{r''}{\Pr\left[ Bin(n-2, p_x(r') \in \{0, 2, \dots, n-2\} \right]} \;dx \\ &= \int_{r'}^{r''}{ \left( \frac{1}{2} + \frac{(2p_x(r') - 1)^{n-2}}{2} \right) } \;dx \\ &= \int_{r'}^{r''}{ \left( \frac{1}{2} + \frac{\left( (2p_x(r') - 1)^{\frac{n-2}{2}} \right)^2}{2} \right) } \;dx \\ &\geq \int_{r'}^{r''} \frac{1}{2} \;dx \\ &= \frac{1}{2} \cdot \left(r''-r'\right), \end{align}\] where (1) is due to [lemma:32OPT32structure], (2) is because the sum is only paying for the segments between \(r^{(2i-1)}\) and \(r^{(2i)}\) so only for \(x \in (r^{(1)}, r^{(n)})\) such that there is an odd number of requests that arrived in \([0, x]\), (3) is by excluding \(r^{(1)}\), (4) is by definition of \(Y_x\), (5) is due to the indicator, (6) is because the conditional distribution of \(Y_x\) is \(Bin(n-2, p_x(r'))\), (7) is due to 16 since \(n\) is even, (8) is because \(n-2\) is even, (9) is because \(\left( (2p_x(r') - 1)^{\frac{n-2}{2}} \right)^2 \geq 0\) and (**) is by integration. Substituting (**) in (*) we have: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}[\mathop{\mathrm{\mathrm{\small Opt}}}(I)] \geq \mathop{\mathrm{\mathbb{E}}}_{r' \sim \mathcal{D}^{(1)}, r'' \sim \mathcal{D}^{(n)}}\left[ \frac{1}{2} \cdot \left( r'' - r' \right) \right] = \frac{1}{2} \cdot \mathop{\mathrm{\mathbb{E}}}_{I \sim \mathcal{D}^n}\left[ \max_{t \in [n]}r_t - \min_{t \in [n]}r_t \right]. \end{align}\] ◻

Proof. Let the cost of a matching \(M\) be \(\mathrm{cost}(M) = \sum_{\{r, r'\} \in M} |r - r'|\). We show that by iteratively exchanging matched pairs of a matching \(M\), we can construct matching \(\hat{M}^*\): \[\begin{align} \hat{M}^* = \{ \{ r^{(2i)}, r^{(2i-1)} \}: i \in [n/2] \}, \end{align}\] with cost at most that that of \(M\). Notice that \(\mathrm{cost}(\hat{M}^*) = \sum_{i=1}^{n/2}\left( r^{(2i)} - r^{(2i - 1)} \right)\). Now we show the exchange. Let \(k = \min\{ i \in [n/2]: \{ r^{(2i)}, r^{(2i - 1)} \} \notin M \}\) and \(a,b\) such that \(\{r^{(2k)}, r^{(a)}\}, \{ r^{(2k-1)}, r^{(b)} \} \in M\), then define: \[\begin{align} M_1 = M \setminus \{ \{r^{(2k)}, r^{(a)}\}, \{ r^{(2k-1)}, r^{(b)} \} \} \cup \{ \{ r^{(2k)}, r^{(2k-1)} \}, \{ r^{(a)}, r^{(b)} \} \}. \end{align}\] Then we have: \[\begin{align} \mathrm{cost}(M) - \mathrm{cost}(M_1) &= \left( |r^{(2k)} - r^{(a)}| + |r^{(2k-1)} - r^{(b)}| \right) - \left( |r^{(2k)} - r^{(2k-1)}| + |r^{(a)} - r^{(b)}| \right) \\ &= \left( r^{(a)} - r^{(2k)} + r^{(b)} - r^{(2k-1)} \right) - \left( r^{(2k)} - r^{(2k-1)} + |r^{(a)} - r^{(b)}| \right) \\ &= r^{(a)} + r^{(b)} - |r^{(a)} - r^{(b)}| - 2r^{(2k)} \\ &= 2 \left( \min\left( r^{(a)}, r^{(b)} \right) - r^{(2k)} \right) \\ &\geq 0, \end{align}\] where the first line is because \(M_1\) differs from \(M\) in exactly two pairs, the second line is because by definition of \(k\) we have \(a, b > 2k\) so \(r^{(a)}, r^{(b)} \geq r^{(2k)} \geq r^{(2k-1)}\), the third line is by cancelling \(r^{(2k-1)}\), the fourth line is because \(r^{(a)} + r^{(b)} - |r^{(a)} - r^{(b)}| = \min\left( r^{(a)}, r^{(b)} \right)\) and the fifth line is because \(r^{(a)}, r^{(b)} \geq r^{(2k)}\). By repeating the exchange we can obtain \(M_2, M_3, \dots, \hat{M}^*\) so: \[\begin{align} \mathrm{cost}(M) \geq \mathrm{cost}(M_1) \geq \mathrm{cost}(M_2) \geq \dots \geq \mathrm{cost}(\hat{M}) = \sum_{i=1}^{n/2}\left( r^{(2i)} - r^{(2i - 1)} \right). \end{align}\]

Let \(M^*\) be a perfect matching of \(r^{(1)}, \dots, r^{(n)}\) of minimum cost. i.e. \(\mathrm{cost}(M^*) = \mathop{\mathrm{\mathrm{\small Opt}}}(I)\), then for \(M = M^*\) we obtain the statement. ◻

Proof. Let \(a, b \in \mathbb{R}\), then: \[\begin{align} (a + b)^m + (a - b)^m = \sum_{k=0}^{m} {m \choose k} a^k (b)^{m-k} + \sum_{k=0}^{m} {m \choose k} (-1)^{m-k} a^k (b)^{m-k} = 2 \sum_{k \in \{0, 2, \dots, m\}} {m \choose k} a^k (b)^{m-k}. \end{align}\]

Then we have that: \[\begin{align} \Pr\left[ Y \in \{0, 2, \dots, m\} \right] = \sum_{k \in \{0,2, \dots, m\}} \Pr\left[ Y = k \right] = \sum_{k \in \{0,2, \dots, m\}} {m \choose k} p^k (1 - p)^{m-k} = \frac{1}{2} + \frac{(2p - 1)^m}{2}, \end{align}\] where the last equality is due to (*) for \(a = p, b = 1 - p\). ◻

Proof of 4. For the first inequality in the lemma statement, let \[\mu = \frac{t_0}{n} \cdot \frac{\beta}{8} \cdot \left(\frac{n}{2t_0} +1\right) = \frac{\beta}{16} +\frac{\beta}{8}\cdot \frac{t_0}{n} \implies \frac{\beta}{16} \leq \mu \leq \frac{\beta}{12},\] which follows from \(t_0\leq \frac{n}{6}\). Then, let \[\begin{align} \delta = \frac{\frac{\beta}{8}}{\mu}-1 = \frac{\frac{\beta}{8}-\mu}{\mu} \geq \frac{\frac{\beta}{8}-\frac{\beta}{12}}{\frac{\beta}{12}} = \frac{1}{2}. \end{align}\] So, we have \[\begin{align} &\Pr\left[Y \sim \textrm{NegativeHypergeometric}\left(n, n - t_0, \frac{\beta}{8}\right) \leq \frac{n}{2t_0} \cdot \frac{\beta}{8}\right]\\ = \;&\Pr\left[X \sim \textrm{Hypergeometric}\left(n, t_0, \frac{\beta}{8} \cdot \left(\frac{n}{2t_0}+1\right)\right) \geq \frac{\beta}{8}\right]\\ \leq \;&\Pr\left[X \geq (1+\delta) \mu\right]\\ \leq \;&\exp\left(-\frac{\delta^2 \mu}{2+\delta}\right) \\ = \;&\exp\left(-\frac{\mu}{10}\right)\\ \leq \;&\exp\left(- \frac{\beta}{160}\right)\\ \leq \;&\frac{1}{n^3}, \end{align}\] where the second line follows from Lemma 2, the fourth line follows from Lemma 1, the sixth line follows from \(\mu \geq \frac{\beta}{16}\), and the last line follows from \(\beta \geq 500 \log n\).

For the second inequality in the lemma statement, let \(\mu = \frac{t_0}{n} \cdot \frac{\beta}{8} \cdot \left(\frac{2n}{t_0} +1\right) > \frac{t_0}{n} \cdot \frac{\beta}{8} \cdot \frac{2n}{t_0} = \frac{\beta}{4}\). Then, let \[\begin{align} \delta = 1-\frac{\frac{\beta}{8}}{\mu} = \frac{\mu - \frac{\beta}{8}}{\mu} \geq \frac{\frac{\mu}{2}}{\mu} = \frac{1}{2}, \end{align}\] where the inequality follows from \(\mu \geq \frac{\beta}{4}\) which implies \(\frac{\mu}{2} \geq \frac{\beta}{8}\). So, we have \[\begin{align} &\Pr\left[Y \sim \textrm{NegativeHypergeometric}\left(n, n - t_0, \frac{\beta}{8}\right) \geq \frac{2n}{t_0} \cdot \frac{\beta}{8}\right]\\ = \;&1-\Pr\left[Y \sim \textrm{NegativeHypergeometric}\left(n, n - t_0, \frac{\beta}{8}\right) \leq \frac{2n}{t_0} \cdot \frac{\beta}{8}\right]\\ = \;&1-\Pr\left[X \sim \textrm{Hypergeometric}\left(n, t_0, \frac{\beta}{8} \cdot \left(\frac{2n}{t_0}+1\right)\right) \geq \frac{\beta}{8}\right]\\ = \;&\Pr\left[X \sim \textrm{Hypergeometric}\left(n, t_0, \frac{\beta}{8} \cdot \left(\frac{2n}{t_0}+1\right)\right) \leq \frac{\beta}{8}\right]\\ = \;&\Pr\left[X \leq (1-\delta) \mu\right]\\ \leq \;&\exp\left(-\frac{\delta^2 \mu}{2}\right) \\ \leq \;&\exp\left(-\frac{\mu}{8}\right)\\ = \;&\exp\left(-\frac{\beta}{32}\right)\\ \leq \;&\frac{1}{n^3}, \end{align}\] where the first line follows the law of total probability, the second line from Lemma 2, the third line from the law of total probability, the fourth line follows from Lemma 1, the fifth line follows from \(\delta \geq \frac{1}{2}\), the sixth line follows from \(\mu \geq \frac{\beta}{4}\), and the last line follows from \(\beta \geq 500 \log n\). ◻

Proof of 8. Let \(X(I) = \sum_{t = 1}^{k} \mathbb{1}\{ r_t \leq r_{(m:n)} \}\) be the number of requests among the first \(k\) that arrive before the \(m\)-th largest request. We now show that the distribution of \(X(I)\) is \(Hypergeometric(n, m, k)\). An equivalent way to interpret \(X\), is that we sample \(k\) indices (the indices correspond to the order statistics) out of \(n\) without replacement and we count how many of the first \(m\) indices we get, so: \[\begin{align} \Pr_{I \sim \mathcal{D}^n}\left[ \min_{t \in [k]}r_t > r_{(m:n)} \right] = \Pr_{I \sim \mathcal{D}^n}\left[ X(I) = 0 \right] = \frac{{n - m \choose k}}{{n \choose k}} = \prod_{i = 0}^{k-1} \frac{n - i - m}{n - i} \leq \left( 1 - \frac{m}{n} \right)^{k} \leq e^{- \frac{km}{n}}. \end{align}\] For the second part of the statement, let \(Y(I) = \sum_{t = 1}^{k} \mathbb{1}\{ r_t \geq r_{(n - m:n)} \}\) and similarly \(Y(I)\) is \(Hypergeometric(n, m, k)\), therefore: \[\begin{align} \Pr_{I \sim \mathcal{D}^n}\left[ \max_{t \in [k]}r_t < r_{(n - m:n)} \right] = \Pr_{I \sim \mathcal{D}^n}\left[ Y(I) = 0 \right] = \Pr_{I \sim \mathcal{D}^n}\left[ X(I) = 0 \right] = \Pr_{I \sim \mathcal{D}^n}\left[ \min_{t \in [k]}r_t > r_{(m:)} \right]. \end{align}\] ◻

Proof of 10. Fix an arbitrary sequence of ordered requests \(\left\{r_{(1)}, \dots, r_{(n)}\right\}\). Fix \(k \in [\rho], j \in \left[\beta^{\rho+1-k}\right]\). By the tower rule, we have \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\left[X^k_j < \beta\right] &= \mathop{\mathrm{\mathbb{E}}}\left[X^k_j < \beta \middle| E_M\right] \cdot \Pr\left[E_M\right] + \mathop{\mathrm{\mathbb{E}}}\left[X^k_j < \beta \middle| \bar{E}_M\right] \cdot \Pr\left[\bar{E}_M\right]\\ &\leq \mathop{\mathrm{\mathbb{E}}}\left[X^k_j < \beta \middle| E_M\right] + n \cdot \Pr\left[\bar{E}_M\right]\\ &\leq \Pr\left[X^k_j < \beta \middle| E_M\right] + \frac{1}{n}, \end{align}\] where the second line follows from that fact that at most \(n\) requests can arrive in a bucket, and the last line follows from Lemma 5.

Next, recall that, as shown in the proof of Lemma 6, \(X^k_j \sim \textrm{Hypergeometric}\left(n-t_0, \sum_{j' \in \mathcal{B}_j} Y_{j'}, t_k - t_{k-1}\right)\), where \(Y_{j'}\) is the number of non-learning phase requests between the endpoints of the \(j'\)-th bucket from the first phase and \(\mathcal{B}_j = \left\{j' \cdot \frac{\beta}{8} : (j-1) \cdot \frac{\beta^k}{8} \leq j' \cdot \frac{\beta}{8} \leq j \cdot \frac{\beta^k}{8}\right\}\) is the set of indices of buckets from the first phase that are combined to form the \(j\)-th bucket in the \(k\)-th phase. . Therefore, \[\begin{align} E\left[X^k_j \middle| E_M \right] &= E\left[X^k_j \sim \textrm{Hypergeometric}\left(n-t_0, \sum_{j' \in \mathcal{B}_j } Y_{j'}, t_k - t_{k-1}\right) \middle| E_M \right]\\ &\leq E\left[X^k_j \sim \textrm{Hypergeometric}\left(n-t_0, \frac{n \beta^k}{4t_0}, t_k - t_{k-1}\right) \right]\\ &= \frac{t_k - t_{k-1}}{n - t_0} \cdot \frac{\beta^k n}{4t_0}\\ &\leq \frac{t_k - t_{k-1}}{2 t_0} \cdot \beta^k\\ &= \begin{aligned} \begin{cases} \frac{n-3\beta^{\rho} - \beta^{\rho+1}/8}{2 \cdot \frac{\beta^{\rho+1}}{8}} \cdot \beta^k , \quad &\textrm{ if } k=1\\ \\ \frac{3\beta^{\rho+1-k} (\beta-1)}{2 \cdot \frac{\beta^{\rho+1}}{8}} \cdot \beta^k, & \textrm{else} \end{cases} \end{aligned}\\ &< \begin{align} \begin{cases} \frac{4n}{\beta^{\rho}} - 1, \quad &\textrm{ if } k=1\\ 12\beta -1 , & \textrm{else}, \end{cases} \end{align} \end{align}\] where the second line follows from stochastic dominance since \(E_M\) implies \(\sum_{j' \in \mathcal{B}_j} Y_{j'} \leq \frac{n \beta}{4t_0} \cdot \beta^{k-1} = \frac{n\beta^{k}}{4}\) non-learning phase requests. The the third line follows from the expectation of hypergeometric random variables, and the remaining lines follow from algebra. Therefore, we have \[\begin{align} E\left[X^k_j\right] &\leq \frac{1}{n} + \begin{aligned} \begin{cases} \frac{4n}{\beta^{\rho}} - 1, \quad &\textrm{ if } k=1\\ 12\beta -1, & \textrm{else}, \end{cases} \end{aligned} \quad\\ &\leq \quad \begin{align} \begin{cases} \frac{4n}{\beta^{\rho}} , \quad &\textrm{ if } k=1\\ 12\beta , & \textrm{else} \end{cases} \end{align} \end{align}\] We can now use the hypergeometric tail bounds from Lemma 1. Let \(\delta = 1\). For \(j \in \left[\beta^{\rho}\right]\) let \(\mu = \mathop{\mathrm{\mathbb{E}}}\left[X^1_j\right]\). By the above calulation, \(\mu \leq \frac{4n}{\beta^{\rho}}\), and by the proof of Lemma 6, \(\mu \geq \frac{5}{4}\beta\). Then, we have \[\begin{align} \Pr\left[X^1_j \geq \frac{8n}{\beta^{\rho}}\right] \leq \Pr\left[X^1_j \geq (1+\delta) \mu\right] \leq \exp\left(-\frac{\delta^2 \mu}{2+\delta}\right) = \exp\left(-\frac{\mu}{3}\right) \leq \exp\left(-\frac{\frac{5}{4}\beta}{3}\right) \leq \frac{1}{n^2}, \end{align}\] where the last inequality follows from \(\beta \geq 500\log n\).

Similarly, for \(k \in [2..\rho]\) and \(j \in \left[\beta^{\rho+1-k}\right]\), the above computations and the proof of Lemma 6 prove \(\frac{5}{4}\beta \leq \mu \leq 12\beta\), where \(\mu = \mathop{\mathrm{\mathbb{E}}}\left[X^k_j\right]\). Then, we have \[\begin{align} \Pr\left[X^k_j \geq 24\beta\right] \leq \Pr\left[X^1_j \geq (1+\delta) \mu\right] \leq \exp\left(-\frac{\delta^2 \mu}{2+\delta}\right) = \exp\left(-\frac{\mu}{3}\right) \leq \exp\left(-\frac{\frac{5}{4}\beta}{3}\right) \leq \frac{1}{n^2}. \end{align}\]

Since \(\frac{n}{\beta^{\rho}} \leq 4\beta^2\), we conclude \[\begin{align} \Pr\left[\cup_{j \in \left[\beta^{\rho}\right]} \left\{X^1_j \geq 32\beta^2\right\}\right] \geq \Pr\left[\cup_{j \in \left[\beta^{\rho}\right]} \left\{X^1_j \geq \frac{8n}{\beta^{\rho}}\right\}\right] \leq \sum_{j \in \left[\beta^{\rho}\right]} \Pr\left[X^1_j \geq \frac{8n}{\beta^{\rho}}\right] \leq \beta^{\rho} \cdot \frac{1}{n^2} < \frac{1}{n}, \end{align}\] and \[\begin{align} \Pr\left[\cup_{k \in [2..\rho]}\cup_{j \in \left[\beta^{\rho+1-k}\right]} \left\{X^k_j \geq 24\beta\right\}\right] \leq \sum_{k \in [2..\rho]} \sum_{j \in \left[\beta^{\rho+1-k}\right]} \Pr\left[X^k_j \geq 24\beta\right] \leq \sum_{k \in [2..\rho]} \beta^{\rho+1-k} \cdot \frac{1}{n^2} \leq \beta^{\rho} \cdot \frac{1}{n^2} < \frac{1}{n}. \end{align}\] ◻