5 Perturbation Analysis

Lemma 22 Perturbation Bounds

✓

Let \(\Pi \) be a finite nonempty set, and \(S_A, S_B : \Pi \to \mathbb {R}\) be functions. Suppose \(\pi ^*\) maximizes \(S_A\). Define:

\(M_A = S_A(\pi ^*)\)
\(M_{A+B} = \max _{\pi \in \Pi } (S_A(\pi ) + S_B(\pi ))\)
\(m_B = \min _{\pi \in \Pi } S_B(\pi )\)
\(M_B = \max _{\pi \in \Pi } S_B(\pi )\)

Then:

\[ m_B \leq S_B(\pi ^*) \leq M_{A+B} - M_A \leq M_B \]

Proof ▶

The first inequality is immediate. For the second, note that \(M_{A+B} \geq S_A(\pi ^*) + S_B(\pi ^*) = M_A + S_B(\pi ^*)\). For the third, let \(\pi '\) maximize \(S_A + S_B\). Then:

\[ M_{A+B} - M_A = S_A(\pi ') + S_B(\pi ') - S_A(\pi ^*) \leq S_B(\pi ') \leq M_B \]

where we used \(S_A(\pi ^*) \geq S_A(\pi ')\).

5.1 Coupling Bounds

Theorem 23 Coupling Upper Bound

✓

For \(N \geq 1\), a Gumbel grid \(Y\), and \(n \in \mathbb {N}\):

\[ T_{\text{Approx}}^N(n) - T_{\text{Gumbel}}(n) \leq \frac{1}{N} \cdot L_{\text{Exp}}(n) \]

where \(L_{\text{Exp}}(n)\) is computed with weights \(E_e = e^{-Y_e}\).

Proof ▶

Let \(\pi ^*\) be the maximizing path for \(T_{\text{Gumbel}}\). By Lemma 17, for each edge \(e\):

\[ h_N(Y_e) \leq \frac{e^{-Y_e}}{N} \]

Summing over the maximizing path for \(T_{\text{Approx}}^N\) and using Lemma 22 gives the result.

Theorem 24 Coupling Lower Bound

✓

For \(N \geq 1\), a Gumbel grid \(Y\), and \(n \in \mathbb {N}\):

\[ 2n \cdot h_N\left(\frac{T_{\text{Gumbel}}(n)}{2n}\right) \leq T_{\text{Approx}}^N(n) - T_{\text{Gumbel}}(n) \]

Proof ▶

Let \(\pi ^*\) be the geodesic for \(T_{\text{Gumbel}}\), which has length \(2n\). By Jensen’s inequality applied to the convex function \(h_N\):

\[ \frac{1}{2n} \sum _{e \in \pi ^*} h_N(Y_e) \geq h_N\left(\frac{1}{2n} \sum _{e \in \pi ^*} Y_e\right) = h_N\left(\frac{T_{\text{Gumbel}}(n)}{2n}\right) \]

The result follows since \(T_{\text{Approx}}^N(n) \geq \sum _{e \in \pi ^*} (Y_e + h_N(Y_e))\).