Bounding average imbalance of auxiliary labels
For integers r>=2 and Q>=1, choose every variable schedule a_v and every nonempty factor schedule d_f independently and uniformly from K=r^Q possibilities; D=K^2 labels are possible. Let c_u count incidences with label u, and set Phi=sum_u(c_u-M/D)^2. Expected value here means the average over all schedule choices. Expanding squares gives Phi=(number of ordered incidence pairs with equal labels)-M^2/D, including self-pairs. Two labels are independent only if their incidences share neither variable nor factor, giving equality probability 1/D. At most b+w incidences per incidence share one of these objects; bound their equality probability by one. Consequently average Phi<=M(b+w), without falsely assuming all incidence labels are independent.
0
1
Tags
Math