The binary median dynamics: one round as a sum of independent coordinates #
With two values, the median rule keeps a node's value unless both sampled nodes
hold the other one; a node holding true ends true unless both samples are
false, and vice versa. The number of true nodes after one round is therefore
a sum over the nodes of independent {0,1} coordinates, one per node, each
depending only on that node's own pair of samples. This file develops the
corresponding bookkeeping:
med3onBoolismax/minof the two sampled values;- the counts as real sums (
ones,falsesR,gapR); - the exact one-round expectations: with
atruenodes,mfalsenodes and gapg = a - m,𝔼[ones'] = a + a m g / n²and𝔼[m'] = m - a m g / n²(thep ↦ 3p² - 2p³map, withp = a/n); - Hoeffding and Bernstein tails for the two counts (
Dynamics.Concentration), and Markov's inequalityP[m' ≥ 1] ≤ 𝔼[m'](Dynamics.avg_markov_one).
The median of three Bools #
Counts as real sums #
The gap ones - falses, as a real.
Equations
- Median.gapR x = ↑(Median.ones x) - Median.falsesR x
Instances For
One round as a sum of independent coordinates #
The complementary coordinate: whether v holds false after one round.
Equations
- Median.fcoord x v p = 1 - Median.coord x v p
Instances For
Per-node expectations #
Expectation bounds #
Concentration for one round #
Markov's inequality: the probability of a false node after one round is
at most the expected number of false nodes (Dynamics.avg_markov_one).