Research proof index

Proves that a do block sampling two independent uniform distributions is equal to the single uniform distribution over the product type.

Pushforward of PMF.uniformOfFintype α under a map f : α → β whose fibers over the image all have the same cardinality k > 0 is the uniform distribution on the image of f. Useful when f is an affine-linear surjection: every fiber is a translate of the kernel and hence has constant cardinality. The proximity-gap proofs use this to bridge the coeff...

Law of Total Probability (Partitioning an Event) The probability of an event f r occurring can be calculated by summing the probabilities of two disjoint cases: 1. f r occurs AND g r occurs. 2. f r occurs AND g r does NOT occur. Good to be used with Pr_multi_let_equiv_single_let

Monotonicity of Probability If event A (defined by predicate f) implies event B (defined by predicate g) for all outcomes r, then the probability of A is less than or equal to the probability of B.

Helper lemma for probability marginalization. Pr_{ (x, y) ← D₁ × D₂ }[ P x ] = Pr_{ x ← D₁ }[ P x ]

Schwartz-Zippel Lemma (Probability Form): For a non-zero multivariate polynomial P of total degree at most d over a finite field L, the probability that P(r) evaluates to 0 for a uniformly random r is at most d / |L|.