Proof. It is clear that whenever the “if” condition in [line:odd95cycle] of 1 is satisfied, the algorithm has found an odd cycle in \(G\), which means \(G\) cannot be bipartite. ◻

Proof of 3 assuming 9. Fix a positive integer \(t\) and a parameter \(\varepsilon\in (0,1)\). Let \(\varepsilon'=\varepsilon^{4}/9\) and \(k=\left\lceil 10^{3}\varepsilon'^{-1}\sqrt{n}\right\rceil\). Consider the algorithm \(\mathrm{\small BipTest}(G,4t,\varepsilon')\). We claim that all \(\lceil 4/\varepsilon'\rceil\cdot k\) random walks in \(\mathrm{\small BipTest}(G,4t,\varepsilon')\) can be simulated by a streaming algorithm in parallel. Indeed, to advance one step in all the random walks, it clearly suffices to take 2 additional passes over the stream of edges. Therefore the algorithm \(\mathrm{\small BipTest}(G,4t,\varepsilon)\) can be implemented in \(8t+O(1/\varepsilon')\) passes and \(O(\varepsilon'^{-1}k\log n)\) space.

Plugging 9 into the above, we obtain a streaming algorithm for \(\mathsf{MaxCut}[1,1-\varepsilon]\) using \(O(\varepsilon^{-8}\log n)\) passes and \(O(\varepsilon^{-8}\sqrt{n}\log n)\) bits of memory. ◻

Proof of 1 assuming 9. Fix a parameter \(\varepsilon\in (0,1)\). Let \[\varepsilon'=\varepsilon^{4}/9,\qquad k=\left\lceil 10^{3}\varepsilon'^{-1}\sqrt{n}\right\rceil,\qquad\text{and}\qquad t=\left\lceil 200\varepsilon^{-8}\log_{2}n\right\rceil.\] On any \(n\)-vertex simple graph \(G\) with no isolated vertices, the algorithm of Eden and Rosenbaum [29] is able to produce an edge of \(G\) that is \((\varepsilon'/40)\)-close to uniformly random (in total variation distance) over \(E\), using \(O(\varepsilon'^{-2}\sqrt{n})\) queries in the adjacency-list model. Using the Eden–Rosenbaum algorithm as a subroutine on [line:sample95edge] of 1, we can thus approximately simulate \(\mathrm{\small BipTest}(G,4t,\varepsilon')\) in the adjacency-list model with additive error at most \[\frac{\varepsilon'}{40}\cdot \lceil4/\varepsilon'\rceil\leqslant\frac{1}{5}.\] Furthermore, this approximate simulation of \(\mathrm{\small BipTest}(G,4t,\varepsilon')\) still accepts with probability 1 if \(G\) is bipartite. Therefore, by 9, this approximate simulation is a one-sided-error \(\varepsilon\)-tester for the bipartiteness of \(G\) with no-case rejection probability at least \(\frac{2}{3}-\frac{1}{5}=\frac{7}{15}\). Repeating the simulation twice yields a one-sided-error \(\varepsilon\)-tester with rejection probability at least \[1-\left(1-\frac{7}{15}\right)^{2}\geqslant\frac{2}{3}.\]

The final algorithm performs \(2k\cdot \lceil 4/\varepsilon'\rceil=O(\varepsilon^{-8}\sqrt{n})\) random walks of length \(4t=O(\varepsilon^{-8}\log n)\), and has total query complexity at most \(O(\varepsilon'^{-2}\sqrt{n})+8kt\cdot\lceil 4/\varepsilon'\rceil=O(\varepsilon^{-16}\sqrt{n}\log n)\). ◻

Proof. For any vertex \(u\), the probability of \(u\) under the distribution \((P^{r}\delta_{v})\,\mathrm{d}\mu\) is \[\begin{align} \sum_{\substack{(v_{0},v_{1},\dots,v_{r})\in [n]^{r+1}\\ v_{0}=u}}\frac{\prod_{i=0}^{r-1}A_{v_{i}v_{i+1}}}{\prod_{i=0}^{r-1}\deg_{G}(v_{i})}\delta_{v}(v_{r})\mu(\{u\})&=\sum_{\substack{(v_{0},v_{1},\dots,v_{r})\in [n]^{r+1}\\ v_{0}=u,\; v_{r}=v}}\frac{\prod_{i=0}^{r-1}A_{v_{i}v_{i+1}}}{\prod_{i=1}^{r}\deg_{G}(v_{i})}}\\ &=\sum_{\substack{(v_{r},v_{r-1},\dots,v_{0})\in [n]^{r+1}\\ v_{r}=v,\; v_{0}=u}}\prod_{i=0}^{r-1}\frac{A_{v_{r-i}v_{r-i-1}}}{\deg_{G}(v_{r-i})},\end{align}\] which clearly equals the probability that a simple random walk of length \(r\) starting from \(v\) ends at \(u\). ◻

Proof. The number of non-lazy steps in a lazy random walk of length \(m\) follows the binomial distribution \(\mathrm{Bin}(m,\frac{1}{2})\), and hence is even with probability exactly \(\frac{1}{2}\). Furthermore, using 10, it is easy to see that conditioned on the number of non-lazy steps being even, the distribution of the endpoint is given by the probability density function \[\left(\left(\frac{I+P}{2}\right)^{m}+\left(\frac{I-P}{2}\right)^{m}\right)\delta_{v}=Q_{m}\delta_{v}.\] Similarly, conditioned on the number of non-lazy steps being odd, the distribution of the endpoint is \(R_{m}\delta_{v}\,\mathrm{d}\mu\). Since the total variation distance between the two conditional distribution is \[\left\|Q_{m}\delta_{v}\,\mathrm{d}\mu -R_{m}\delta_{v}\,\mathrm{d}\mu\big.\right\|_{\mathrm{TV}}=\frac{1}{2}\left\|Q_m\delta_v-R_m\delta_v\big.\right\|_1\leqslant 1-\frac{\varepsilon}{2},\] the desired conclusion follows from standard birthday paradox arguments (4). ◻

Proof. Assume that the conclusion does not hold. Since \(\left\|Q_m\delta_v-R_m\delta_v\big.\right\|_1\leqslant 2\) for any \(v\in [n]\),¹¹ it follows that \[\underset{ v\sim \mu }\mathbb{P}\left[ 2-\left\|Q_m\delta_v-R_m\delta_v\big.\right\|_1\geqslant\varepsilon\Big. \right]\geqslant\frac{\varepsilon}{2}.\] Therefore, when \(v\) is sampled from \(\mu\), with probability at least \(\varepsilon/2\) the conclusion of 1 holds for \(v\). This implies that in each iteration of the “for” loop on [line:each95vertex95v] of 1, the algorithm rejects on with probability at least \(\varepsilon/3\) on [line:reject]. Since there are \(\lceil 4/\varepsilon\rceil\) iterations of this “for” loop, and each iteration uses independent randomness, it follows that \(\mathrm{\small BipTest}(G,m,\varepsilon)\) accepts with probability at most \((1-\varepsilon/3)^{4/\varepsilon}<1/3\). This contradicts the assumption that \(\mathrm{\small BipTest}(G,m,\varepsilon)\) accepts with probability at most \(2/3\). ◻

Proof. For any vector \(a\in \mathbb{R}^{n}\), we have \[a^{T}Xa=\underset{v\sim\mu} \mathbb{E}\left[ \left(\sum_{i=1}^{n}a_{i}f^{(r)}_{v}(i)\right)^{2} \right] \geqslant 0.\] Combined with the obvious fact that \(X\) is symmetric, this implies \(X\) is positive semi-definite.

For any \(i\in [n]\), we have \[X_{ii}=\underset{v\sim \mu} \mathbb{E}\left[ f_{v}^{(r)}(i)^{2} \right] \leqslant\underset{v\sim \mu} \mathbb{E}\left[ \frac{1}{2}Q_{r}\delta_{v}(i)+\frac{1}{2}R_{r}\delta_{v}(i) \right] = \underset{v\sim \mu} \mathbb{E}\left[ W^{r}\delta_{v}(i)\Big. \right] =W^{r}\mathbf{1}(i)=1.\]

We also have the direct calculation \[\begin{align} \mathrm{tr}(AX)&=\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}\underset{v\sim\mu} \mathbb{E}\left[ f_{v}^{(r)}(i)f_{v}^{(r)}(j) \right] }\\ &=\underset{v\sim\mu} \mathbb{E}\left[ 2|E|\cdot\underset{i\sim \mu} \mathbb{E}\left[ f_{v}^{(r)}(i)\cdot \frac{\sum_{j=1}^{n}A_{ij}f_{v}^{(r)}(j)}{\sum_{j=1}^{n}A_{ij}} \right] \right] }\\ &=2|E|\cdot \underset{v\sim\mu} \mathbb{E}\left[ \left\langle f_{v}^{(r)}, Pf_{v}^{(r)} \right\rangle \right] ,} \end{align}\] which proves the desired identity in the third item. ◻

Proof. For any positive integer \(r\), the matrix \(X\in \mathbb{R}^{n\times n}\) defined in 4 is a feasible solution to \(\mathrm{\small BasicSDP}_{A}\), due to the first and second conclusions of 11. The value achieved by this matrix \(X\) is \[\frac{1}{2}-\frac{1}{4|E|}\cdot\mathrm{tr}(AX)\geqslant 1-\frac{1}{2}\cdot \underset{v\sim \mu} \mathbb{E}\left[ \left\langle f_{v}^{(r)}, Pf_{v}^{(r)} \right\rangle+1 \right] ,\] where the inequality follows from the third conclusion of 11. Therefore, the optimal value of \(\mathrm{\small BasicSDP}_{A}\) is at least \[\label{eq:opt95at95least} 1-\frac{1}{2}\cdot \underset{v\sim \mu} \mathbb{E}\left[ \left\langle f_{v}^{(r)}, Pf_{v}^{(r)} \right\rangle+1 \right]\tag{5}\] for any positive integer \(r\), as desired. ◻

Proof. Recall from the proof of 1 that \(Q_{2t}\delta_{v}\,\mathrm{d}\mu\) (respectively, \(R_{2t}\delta_{v}\,\mathrm{d}\mu\)) is the distribution of the endpoint of the length-\(2t\) lazy-random walk starting at \(v\) conditioned on the number of non-lazy steps being even (respectively, odd). It follows from 5 (and 10) that the total variation distance between \(Q_{2t}\delta_{v}\,\mathrm{d}\mu\) and \(PR_{2t}\delta_{v}\,\mathrm{d}\mu\) is at most \((2t)^{-1/2}\), and hence \(\big\|Q_{2t}\delta_{v}-PR_{2t}\delta_{v}\big\|_{1}\leqslant\sqrt{2/t}\). Due to the reflection symmetry of the binomial distribution \(\mathrm{Bin}(2t,\frac{1}{2})\) about \(t\), it also follows from 5 that the total variation distance between \(PQ_{2t}\delta_{v}\,\mathrm{d}\mu\) and \(R_{2t}\delta_{v}\,\mathrm{d}\mu\) is at most \((2t)^{-1/2}\), and hence \(\big\|Q_{2t}\delta_{v}-PR_{2t}\delta_{v}\big\|_{1}\leqslant\sqrt{2/t}\). ◻

Proof. In this proof, we write \(g=\frac{1}{2}Q_{2t}\delta_{v}\) and \(h=\frac{1}{2}R_{2t}\delta_{v}\). Then by [def:Q_r_and_R_r,def:f_r] we have \[\label{eq:root95g-root95h} \left\langle f_{v}^{(2t)}, Pf_{v}^{(2t)} \right\rangle=\left\langle \sqrt{g}-\sqrt{h}, P\left(\sqrt{g}-\sqrt{h}\right) \right\rangle\tag{6}\] and \[\label{eq:root95g43root95h} \left\langle \sqrt{W^{2t}\delta_{v}}, P\sqrt{W^{2t}\delta_{v}} \right\rangle=\left\langle \sqrt{g+h}, P\sqrt{g+h} \right\rangle\leqslant\left\langle \sqrt{g}+\sqrt{h}, P\left(\sqrt{g}+\sqrt{h}\right) \right\rangle.\tag{7}\] Adding 6 and 7 together yields \[\left\langle f_{v}^{(2t)}, Pf_{v}^{(2t)} \right\rangle+\left\langle \sqrt{W^{2t}\delta_{v}}, P\sqrt{W^{2t}\delta_{v}} \right\rangle\leqslant 2\left\langle \sqrt{g}, P\sqrt{g} \right\rangle+2\left\langle \sqrt{h}, P\sqrt{h} \right\rangle.\] Therefore, it suffices to show that both \(\left\langle \sqrt{g}, P\sqrt{g} \right\rangle\) and \(\left\langle \sqrt{h}, P\sqrt{h} \right\rangle\) are at most \(\left(\sqrt{\gamma}+(2/t)^{1/4}\right)/2\). We next prove \(\left\langle \sqrt{g}, P\sqrt{g} \right\rangle\leqslant\left(\sqrt{\gamma}+(2/t)^{1/4}\right)/2\); the other one can be proved in a similar way.

First note that by 10, for any \(i\in [n]\) we have \[\label{eq:P95rootg95root95Pg} P\sqrt{g}\,(i)=\frac{\sum_{j=1}^{n}A_{ij}\sqrt{g(j)}}{\sum_{j=1}^{n}A_{ij}}\leqslant\sqrt{\frac{\sum_{j=1}^{n}A_{ij}\,g(j)}{\sum_{j=1}^{n}A_{ij}}}=\sqrt{Pg}\,(i),\tag{8}\] where we used Cauchy-Schwarz in the second transition. Therefore, we have \[\begin{align} \left\langle \sqrt{g}, P\sqrt{g} \right\rangle&\leqslant\left\langle \sqrt{g}, \sqrt{Pg} \right\rangle}\\ &\leqslant\left\langle \sqrt{g}, \sqrt{h} \right\rangle+\big\|\sqrt{g}\big\| _{2}\cdot\left\|\sqrt{h}-\sqrt{Pg}\right\|_{2}\\ &\leqslant\frac{1}{2}\left\langle \sqrt{2g}, \sqrt{2h} \right\rangle+\frac{1}{\sqrt{2}}\cdot \sqrt{\big\|h-Pg\big\|_{1}}(1)}\\ &\leqslant\frac{1}{2}\sqrt{2-\big\|2g-2h\big\|_{1}}+\frac{1}{2}\sqrt{\big\|2h-P(2g)\big\|_{1}}(2)}\\ &\leqslant\frac{1}{2}\sqrt{\gamma}+\frac{1}{2}\left(\frac{2}{t}\right)^{1/4},} \end{align}\] as desired. ◻

Proof. For any nonnegative function \(g:[n]\rightarrow [0,+\infty)\), define its relative entropy to be \[\mathrm{Ent}_{\mu}(g):=\underset{i\sim\mu} \mathbb{E}\left[ g(i)\log_{2}g(i)\big. \right] .\] For any probability density function \(g\), we have \(\mathrm{Ent}_{\mu}(g)\geqslant 0\).¹⁴ The goal is to prove that for any probability density function \(g:[n]\rightarrow [0,+\infty)\), we have¹⁵ \[\label{eq:JS95Hellinger} 1-\left\langle \sqrt{g}, P\sqrt{g} \right\rangle\leqslant\mathrm{Ent}_{\mu}(g)-\mathrm{Ent}_{\mu}(Wg).\tag{9}\] Once we have 9 , we can replace \(g\) with \(W^{r}\delta_{v}\) and sum over all nonnegative integers \(r\), yielding \[\sum_{r=0}^{+\infty}\left(1-\left\langle \sqrt{W^{r}\delta_{v}}, P\sqrt{W^{r}\delta_{v}} \right\rangle\right)\leqslant\sum_{r=0}^{+\infty}\Big(\mathrm{Ent}_{\mu}\big(W^{r}\delta_{v}\big)-\mathrm{Ent}_{\mu}\big(W^{r+1}\delta_{v}\big)\Big)\leqslant\mathrm{Ent}_{\mu}(\delta_{v})=\log_{2}\frac{1}{\mu(\{v\})}.\]

It remains to prove that 9 holds for any probability density function \(g\).¹⁶ We denote \(\varphi:[0,+\infty)\rightarrow\mathbb{R}\) to be the convex function \(\varphi(x)=x\log_{2}x\). For any \(i\in [n]\), by [def:Markov_operator,def:Q_r_and_R_r] we have \[\varphi\big(Wg(i)\big)=\varphi\left(\frac{\sum_{j=1}^{n}A_{ij}(g(i)+g(j))/2}{\sum_{j=1}^{n}A_{ij}}\right)\leqslant\frac{\sum_{j=1}^{n}A_{ij}\,\varphi\big((g(i)+g(j))/2\big)}{\sum_{j=1}^{n}A_{ij}}.\] Now we apply 7 to the numerator and get \[\varphi\big(Wg(i)\big)\leqslant\frac{1}{\sum_{j=1}^{n}A_{ij}}\cdot \sum_{j=1}^{n}A_{ij}\left(\frac{1}{2}\varphi\big(g(i)\big)+\frac{1}{2}\varphi\big(g(j)\big)+\sqrt{g(i)g(j)}-\frac{1}{2}g(i)-\frac{1}{2}g(j)\right).\] Taking expectation over \(i\sim \mu\) yields \[\big\|\varphi\circ (Wg)\big\|_{1}\leqslant\frac{1}{2}\big\|\varphi\circ g\big\|_{1}+\frac{1}{2}\big\|P(\varphi\circ g)\big\|_{1}+\left\langle \sqrt{g}, P\sqrt{g} \right\rangle-\frac{1}{2}\big\|g\big\|_{1}-\frac{1}{2}\big\|Pg\big\|_{1}\] Since the operator \(P\) preserves \(L^{1}\)-norm of nonnegative functions, the above can be rewritten as \[\mathrm{Ent}_{\mu}(Wg)\leqslant\mathrm{Ent}_{\mu}(g)+\left\langle \sqrt{g}, P\sqrt{g} \right\rangle-1,\] which is exactly the desired inequality 9 . ◻

Proof. For any \(r\in\{t,t+1,\dots,2t-1\}\), due to the fact that the operator \(S=\frac{1}{2}(I-P)\) contracts \(L^{1}\)-norm, we have \[\big\|Q_{2r}\delta_{v}-R_{2r}\delta_{v}\big\|_{1}=2\big\|S^{2r}\delta_{v}\big\|_{1}\geqslant 2\big\|S^{4t}\delta_{v}\big\|_{1}=\big\|Q_{4t}\delta_{v}-R_{4t}\delta_{v}\big\|_{1}=2-\gamma.\] It then follows from 3 that \[\label{eq:average95first95part} \frac{1}{t}\sum_{r=t}^{2t-1}\left(\left\langle f_{v}^{(2r)}, Pf_{v}^{(2r)} \right\rangle+\left\langle \sqrt{W^{2r}\delta_{v}}, P\sqrt{W^{2r}\delta_{v}} \right\rangle\right)\leqslant 2\sqrt{\gamma}+2\left(\frac{2}{t}\right)^{1/4}.\tag{11}\] On the other hand, 3 clearly implies \[\label{eq:average95second95part} \frac{1}{t}\sum_{r=t}^{2t-1}\left(1-\left\langle \sqrt{W^{2r}\delta_{v}}, P\sqrt{W^{2r}\delta_{v}} \right\rangle\right)\leqslant\frac{1}{t}\log_{2}\frac{1}{\mu(\{v\})}.\tag{12}\] Adding 11 and 12 together yields the conclusion. ◻

Proof. Suppose \(\mathrm{\small BipTest}(G,4t,\varepsilon)\) (1) rejects with probability at most \(2/3\). By 1, it follows that \[\underset{v\sim \mu} \mathbb{E}\left[ 2-\left\|Q_{4t}\delta_v-R_{4t}\delta_v\big.\right\|_1\Big. \right] \leqslant 2\varepsilon.\] Applying Cauchy-Schwarz yields \[\underset{v\sim \mu} \mathbb{E}\left[ \sqrt{2-\left\|Q_{4t}\delta_v-R_{4t}\delta_v\big.\right\|_1} \right] \leqslant\sqrt{2\varepsilon}.\] It then follows from 4 that \[\begin{align} \frac{1}{t}\sum_{r=t}^{2t-1}\underset{v\sim \mu} \mathbb{E}\left[ \left\langle f_{v}^{(2r)}, Pf_{v}^{(2r)} \right\rangle+1 \right] &\leqslant 2\sqrt{2\varepsilon}+2\left(\frac{2}{t}\right)^{1/4}+\frac{1}{t}\underset{v\sim \mu} \mathbb{E}\left[ \log_{2}\frac{1}{\mu(\{v\})} \right] \\ &\leqslant 2\sqrt{2\varepsilon}+2\left(\frac{2}{t}\right)^{1/4}+\frac{1}{t}\log_{2}\left(\underset{v\sim \mu} \mathbb{E}\left[ \frac{1}{\mu(\{v\})} \right] \right)\\ &=2\sqrt{2\varepsilon}+2\left(\frac{2}{t}\right)^{1/4}+\frac{\log_{2}n}{t}\\ &\leqslant 2\sqrt{2\varepsilon}+2\sqrt{\varepsilon}+\frac{\varepsilon^{2}}{2}\leqslant 6\sqrt{\varepsilon}. \end{align}\] Therefore, there exists an \(r\in \{t,t+1,\dots,2t\}\) such that \[\underset{v\sim \mu} \mathbb{E}\left[ \left\langle f_{v}^{(2r)}, Pf_{v}^{(2r)} \right\rangle+1 \right] \leqslant 6\sqrt{\varepsilon},\] and hence the desired conclusion follows from 2. ◻

Proof of 9. Apply 12 to conclude that the value of \(\mathrm{\small BasicSDP}_{A}\) is at least \(1-\varepsilon^{2}\). It then follows from 7 that the the Max-Cut value of \(G\) is at least \(1-\varepsilon\). ◻

Proof. The given conditions imply \[\sum_{i=1}^{n}\min\left\{\frac{1}{2}p^{(0)}_{i},\frac{1}{2}p^{(1)}_{i}\right\}=\sum_{i=1}^{n}\frac{1}{4}\left(p^{(0)}_{i}+p^{(1)}_{i}-\left|p^{(0)}_{i}-p^{(1)}_{i}\right|\right)\geqslant\frac{\varepsilon}{4}.\] The conclusion then follows [30], or any of the standard birthday-paradox arguments. ◻

Proof. For each \(i\in \{0,1,\dots,2t\}\), write \[p_i:=\mathbb{P}\left[ X=i \right]=2^{-2t}\binom{2t}{i}\] The total variation distance between \(\nu_{0}\) and \(\nu_{1}\) equals \[\begin{align} \frac{1}{2}\sum_{i=0}^{t}\big|\nu_{0}(\{2i\})-\nu_{1}(\{2i\})\big|&=\frac{1}{2}\cdot2p_{0}+\frac{1}{2}\sum_{i=1}^{t}|2p_{2i}-2p_{2i-1}|\\ &=p_{0}+\sum_{i=1}^{\lfloor t/2\rfloor}(p_{2i}-p_{2i-1})+\sum_{i=0}^{\lceil t/2\rceil-1}(p_{2t-2i-1}-p_{2t-2i})\\ &=p_{0}+\sum_{i=1}^{\lfloor t/2\rfloor}(p_{2i}-p_{2i-1})+\sum_{i=0}^{\lceil t/2\rceil-1}(p_{2i+1}-p_{2i})\\ &=p_{t}=2^{-2t}\binom{2t}{t}.\qedhere \end{align}\] ◻

Proof. The first item follows from pointwise comparison: \[\left\|\sqrt{f}-\sqrt{g}\right\|_{2}^{2}=\underset{i\sim \mu} \mathbb{E}\left[ \left(\sqrt{f(i)}-\sqrt{g(i)}\right)^{2} \right] \leqslant\underset{i\sim \mu} \mathbb{E}\left[ \left|f(i)-g(i)\right|\big. \right] =\|f-g\|_{1}.\] For the second item, by Cauchy-Schwarz we have \[\begin{align} \left\langle \sqrt{f}, \sqrt{g} \right\rangle^{2}&=\underset{i\sim \mu} \mathbb{E}\left[ \sqrt{f(i)g(i)} \right] ^{2}\leqslant\underset{i\sim \mu} \mathbb{E}\left[ \min\{f(i),g(i)\}\big. \right] \cdot \underset{i\sim \mu} \mathbb{E}\left[ \max\{f(i),g(i)\}\big. \right] \\ &=\underset{i\sim \mu} \mathbb{E}\left[ \frac{f(i)+g(i)-|f(i)-g(i)|}{2}\big. \right] \cdot \underset{i\sim \mu} \mathbb{E}\left[ \max\{f(i),g(i)\}\big. \right] \\ &\leqslant\left(1-\frac{1}{2}\|f-g\|_{1}\right)\cdot \|f+g\|_{1}\leqslant 2-\|f-g\|_{1}.\qedhere \end{align}\] ◻

Proof. Without loss of generality assume \(a\geqslant b\). We re-parameterize by letting \(a=\lambda (1+x)\) and \(b=\lambda(1-x)\), where \(\lambda\in [0,+\infty)\) and \(x\in [0,1]\). For fixed \(x\), both sides of 13 scales linearly in \(\lambda\), so we may assume \(\lambda=\frac{1}{2}\). The desired inequality 13 thus reduces to \[\label{eq:two95point95ineq95reduces} \varphi\left(\frac{1+x}{2}\right)+\varphi\left(\frac{1-x}{2}\right)+1\geqslant 1-\sqrt{1-x^{2}},\qquad\text{for all }x\in [0,1].\tag{14}\]

We first apply 8 to get that the function \[x\mapsto \frac{\int_{0}^{x}(1-t^{2})^{-1}\,\mathrm{d}t}{\int_{0}^{x}(1-t^{2})^{-3/2}\,\mathrm{d}t}=\frac{\frac{1}{2}\ln\frac{1+x}{1-x}}{x(1-x^{2})^{-1/2}}\] is nonincreasing in \((0,1)\). Applying 8 again yields that the function \[x\mapsto \frac{\int_{0}^{x}\frac{1}{2}\ln\frac{1+t}{1-t}\,\mathrm{d}t}{\int_{0}^{x}t(1-t^{2})^{-1/2}\,\mathrm{d}t}=\frac{\frac{1}{2}(1+x)\ln (1+x)+\frac{1}{2}(1-x)\ln (1-x)}{1-\sqrt{1-x^{2}}}\] is nonincreasing in \((0,1)\). This function converges to \(\ln 2\) as \(x\) goes to 1. Therefore, for any \(x\in (0,1)\) we have \[\frac{\frac{1}{2}(1+x)\ln (1+x)+\frac{1}{2}(1-x)\ln (1-x)}{1-\sqrt{1-x^{2}}}\geqslant\ln 2,\] which rearranges to \[\frac{1+x}{2}\log_{2}\frac{1+x}{2}+\frac{1-x}{2}\log_{2}\frac{1-x}{2}+1\geqslant 1-\sqrt{1-x^{2}}.\] Since both sides of the above inequality are continuous functions on \([0,1]\), this proves 14 . ◻

Proof. Fix \(x,y\in (0,1)\) such that \(x<y\), and let \[a_{i}=\int_{0}^{x}f_{i}(t)\,\mathrm{d}t,\qquad b_{i}=\int_{x}^{y}f_{i}(t)\,\mathrm{d}t,\qquad\text{for each }i\in \{1,2\}.\] Since \(f_{1}/f_{2}\) is nonincreasing, it is easy to see that \(a_{1}/a_{2}\leqslant f_{1}(x)/f_{2}(x)\leqslant b_{1}/b_{2}\). Therefore \[\frac{a_{1}}{a_{2}}\leqslant\frac{a_{1}+b_{1}}{a_{2}+b_{2}},\] as desired. ◻