A Probability Mass Function of M

Before proving Theorem 1, we will argue regularity. We will establish the three conditions: symmetry, shift-invariance, and monotonicity. Pr[M( q) = r] = Pr[M(Π q) = π(r)], which implies M is symmetric as desired. We first prove two lemmas. The second lemma gives a useful fact about partial sums of a non-decreasing sequence.