diff f6bf760..6fbd3ac k_server_squared_log_v2.txt
diff --git a/k_server_squared_log_v2.txt b/k_server_squared_log_v2.txt
index 865f58f..49e0f7d 100644
--- a/k_server_squared_log_v2.txt
+++ b/k_server_squared_log_v2.txt
@@ -37,7 +37,7 @@ every x, y, z in X:
(Distance does not care which end is which.)
(M3) d(x, z) <= d(x, y) + d(y, z).
- (The "triangle inequality": going straight is never more
+ (The "triangle ineuality": going straight is never more
expensive than going via a detour.)
Examples:
@@ -564,7 +564,7 @@ still contains r_t. Now consider the quantity
By an elementary comparison (the server we just moved was matched
to a specific occurrence of r_t in C_t, and after the move the
SAME matching still matches A_t to C_t, so the two distances agree
-up to the moved amount), we get the pathwise inequality
+up to the moved amount), we get the pathwise ineuality
cost_t + M(A_t, C_t) <= M(A_{t-1}, C_t).
@@ -601,7 +601,7 @@ every subsequent budget about "sum_{t} M(C_{t-1}, C_t)" IS a budget
on the real algorithm's cost. Good.
Similarly: the paper sometimes compares two OFFLINE optima
-(solution Z vs. solution Z'). Then only the pathwise inequality is
+(solution Z vs. solution Z'). Then only the pathwise ineuality is
used, not causality. This is fine because offline comparisons are
just for identifying which configuration is cheaper.
@@ -669,7 +669,7 @@ So an affine functional's expected filtering change is ZERO. Nice.
A concave functional has conditional expected value that does NOT
increase under filtering. (Because E[f(X)|more info] >= f(E[X|less
-info]) for concave f, up to the Jensen inequality direction.)
+info]) for concave f, up to the Jensen ineuality direction.)
A convex functional has conditional expected value that does not
DECREASE under filtering.
@@ -801,7 +801,7 @@ Three reasons:
"how much mass is below this vertex?" question hierarchically.
- Posterior subtree counts are natural on a tree: N_v(t) is just
"the number of hidden servers whose leaf is below v". There
- is a clean inequality (superadditivity) linking parent's "rank
+ is a clean ineuality (superadditivity) linking parent's "rank
distribution" to children's, which is what the allocation
theorem exploits.
@@ -1025,7 +1025,7 @@ The local drift budget E_v at an internal vertex v is
E_v := E sum over t of [ sum_{i child of v} sum_a |delta_t p_{ia}|
+ sum_a |delta_t p_{va}| ] .
-The paper proves a clean coupling inequality:
+The paper proves a clean coupling ineuality:
sum over internal vertices v of r_{|v|} E_v <= 6 P.
@@ -1093,7 +1093,7 @@ distributed" measure at v.
Here is the key structural lemma. For any internal vertex v, its
children i, and its rank function (either family), the following
-inequality holds WITHOUT assuming independence between children:
+ineuality holds WITHOUT assuming independence between children:
sum_{i child of v} L_i^beta <= L_v^beta,
sum_{i child of v} M_i <= M_v <= m_v.
@@ -1101,7 +1101,7 @@ inequality holds WITHOUT assuming independence between children:
Why? Two facts:
- Convexity of l^beta and l^{siz}, plus an "increasing hinge"
- majorization argument (Karamata's inequality applied to convex
+ majorization argument (Karamata's ineuality applied to convex
hinges (b - p)_+): the sum of a convex function over child
rank probabilities is at most its value on the parent's rank
probabilities, adjusted by (d - 1)k padding ones for "missing"
@@ -1287,7 +1287,7 @@ L_i^{beta_i}. This translates to:
S alpha_i <= (1 + eta_i) B_i where eta_i := c_t h_i / ell,
c_t > 0 small absolute.
-The last inequality is a per-child upper bound. When S = 0, we have
+The last ineuality is a per-child upper bound. When S = 0, we have
S alpha_i = 0 = B_i at every child, and the constraint is trivial.
We want alpha_i to change SLOWLY when B and S change rapidly. That
@@ -1428,7 +1428,7 @@ Net change is at most epsilon (gamma_j - gamma_i + 2S)
< -epsilon gamma_i < 0 (since gamma_i > 0), contradicting global
minimality of alpha^1. So every other active j has gamma_j >= -2S.
-Now sum the inequalities gamma_j >= -2S over all positive
+Now sum the ineualities gamma_j >= -2S over all positive
coordinates j. For each positive j:
S alpha_j - (1+eta_j) B_j >= -(2S/(C_alpha ell)) alpha_j F_j.
Summing over j with sum alpha_j = 1 and sum B_j = S:
@@ -2020,7 +2020,7 @@ Each entry has:
- A RADIUS V drawn from [r, 2 r] with a specific density.
Set K_h = ceil(e^{C_K h}) for an absolute constant C_K chosen
-large enough that, for every h >= 1, the two inequalities
+large enough that, for every h >= 1, the two ineualities
e^{-K_h / 2} <= (c/2) e^{-h} and e^{-K_h} <= (c/2) e^{-2h}
hold simultaneously, where c > 0 is a fixed small absolute
constant. The point is that tier-h retirement probabilities
@@ -2203,7 +2203,7 @@ least r * int (F_z^{g_old} - F_z^{g_new}) dmu^+. The paper
estimates this from below as (c e^{-h} - C/sqrt(K_h)) r W.
With K_h = ceil(e^{C_K h}) and C_K large enough, the C/sqrt(K_h)
-error is absorbed by the c e^{-h} leading term The final inequality:
+error is absorbed by the c e^{-h} leading term The final ineuality:
r W / K_h <= e^{-h} * (pilot potential drop).
So the pilot potential provides at least r W / K_h of drop per
@@ -2292,7 +2292,7 @@ so p_{t,leaf}^circ = q_{t,leaf}. The whole subtree sums to q_v:
14.2 Variation of parked masses.
-By taking differences and using the triangle inequality (a short
+By taking differences and using the triangle ineuality (a short
computation), one gets
sum_v r_{|v|} |Delta p_v^circ| <= (1 + 1/tau) V,
@@ -2985,7 +2985,7 @@ Summing expectations:
= (1/N) E[ (sum F_i) + (sum_{i < N} Z_i) ]
<= (1/N) E[ cost_{A_N, s}(sigma_N) ].
-The last inequality drops the H_i and Z_N terms because they are
+The last ineuality drops the H_i and Z_N terms because they are
nonnegative.
Plugging in the total bound:
@@ -3239,7 +3239,7 @@ This section tells the "money chain" of the proof. Each link is a
lemma we have already explained. Read top-down for the composite;
read bottom-up for the money flow.
-17.1 The three budget inequalities.
+17.1 The three budget ineualities.
The three moving pieces are: