LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The CHSH bound and the finite-sampling law for independent trials

Statement

No choice principle is used. Let $(Ω, F, P)$ be a probability space (Probability measures and probability spaces).

(a) CHSH bound. Let $A_{0}, A_{1}, B_{0}, B_{1} : Ω \to {- 1, 1}$ be random variables with values in ${- 1, 1}$ (Random elements and real random variables). Then the four expectations exist and

$∣ E [A_{0} B_{0}] + E [A_{0} B_{1}] + E [A_{1} B_{0}] - E [A_{1} B_{1}] ∣ \leq 2.$

(b) Positive-probability sequences. Let $N \geq 1$ , $m \geq 1$ , $p_{1}, \dots, p_{m} \geq 0$ with $\sum_{j = 1}^{m} p_{j} = 1$ , and let $X_{1}, \dots, X_{N} : Ω \to {1, \dots, m}$ be mutually independent with $P (X_{k} = j) = p_{j}$ for all $k, j$ (Pairwise and mutual independence of finite-valued random variables). Then for every sequence $(j_{1}, \dots, j_{N}) \in {1, \dots, m}^{N}$ with $p_{j_{k}} > 0$ for every $k$ ,

$P (X_{k} = j_{k} for every k) = \prod_{k = 1}^{N} p_{j_{k}} > 0.$

Consequently every event disjoint from this outcome has probability at most $1 - \prod_{k} p_{j_{k}} < 1$ : any criterion that rejects at least one such sequence has positive failure probability under this sampling model.

(c) Binomial frequency. Let $S$ be binomial $(N, p)$ with $N \geq 1$ and $p \in [0, 1]$ (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials). Then the frequency $S / N$ satisfies $E [S / N] = p$ , $Var (S / N) = p (1 - p) / N$ , and for every $ε > 0$

$P (∣ S / N - p ∣ \geq ε) \leq \frac{p (1 - p)}{N ε^{2}} .$

(d) Multinomial count law. The number of sequences $(j_{1}, \dots, j_{N})$ with prescribed fibre sizes $n_{j} : = # {k : j_{k} = j}$ is the multinomial coefficient $(\binom{N}{n_{1}, \dots, n_{m}})$ (The multinomial coefficient $(\binom{n}{k_{0}, \dots, k_{m - 1}})$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes), and each such sequence has probability $\prod_{j = 1}^{m} p_{j}^{n_{j}}$ ; in this displayed product use the zero-count convention $p^{0} : = 1$ for every $p \in [0, 1]$ , including $p = 0$ . Hence the probability that the count vector equals $(n_{1}, \dots, n_{m})$ is $(\binom{N}{n_{1}, \dots, n_{m}}) \prod_{j} p_{j}^{n_{j}}$ .

No statistical inference, empirical claim or measured frequency is asserted; the lemma only computes probabilities of an explicitly specified independent sampling model.

Facts & Assumptions

Given: A probability space $(Ω, F, P)$ ; variables $A_{i}, B_{j}$ with values in ${- 1, 1}$ ; independent ${1, \dots, m}$ -valued $X_{1}, \dots, X_{N}$ ; a binomial $(N, p)$ variable $S$ .

[F1]

A probability measure $P$ is countably additive on disjoint families, hence finitely additive (Measures on sigma-algebras, Probability measures and probability spaces); a real random variable is a measurable $Ω \to R$ (Random elements and real random variables).

[F2]

$E [a X + b Y] = a E [X] + b E [Y]$ for integrable $X, Y$ and scalars $a, b$ ; $E [X] \leq E [Y]$ almost surely for integrable real $X \leq Y$ ; $∣ E [X] ∣ \leq E [∣ X ∣]$ (Linearity, monotonicity, and the modulus bound for expectation, Expectation of a nonnegative or integrable random variable).

[F3]

A finite family $(X_{i})$ of finite-valued random variables is mutually independent when $P (X_{j} = x_{j} for all j \in J) = \prod_{j \in J} P (X_{j} = x_{j})$ for every nonempty $J$ and every selection $x_{j} \in X_{j} (Ω)$ (Pairwise and mutual independence of finite-valued random variables).

[F4]

A binomial $(N, p)$ variable is a sum of $N$ mutually independent Bernoulli $(p)$ variables; $E [S] = N p$ and $Var (S) = N p (1 - p)$ (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials, A Bernoulli $(p)$ variable has mean $p$ and variance $p (1 - p)$ ; a binomial $(n, p)$ variable has mean $n p$ and variance $n p (1 - p)$ ).

[F5]

For a real random variable, $Var (X) = E [(X - E [X])^{2}]$ when $X$ is square-integrable, and $P (∣ X - E [X] ∣ \geq a) \leq Var (X) / a^{2}$ for $a > 0$ (Moments, variance, and covariance on a probability space, Chebyshev's inequality for random variables).

[F6]

The multinomial coefficient $(\binom{N}{n_{1}, \dots, n_{m}})$ is the number of colourings $c : {1, \dots, N} \to {1, \dots, m}$ with $∣ c^{- 1} [{j}] ∣ = n_{j}$ for every $j$ , defined only when $\sum_{j} n_{j} = N$ (The multinomial coefficient $(\binom{n}{k_{0}, \dots, k_{m - 1}})$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes).

Proof

1.1givenF2algebra

[Pointwise CHSH identity] Fix $ω \in Ω$ . Since $B_{0} (ω), B_{1} (ω) \in {- 1, 1}$ , the numbers $B_{0} (ω) + B_{1} (ω)$ and $B_{0} (ω) - B_{1} (ω)$ are $\pm 2$ or $0$ , and exactly one of them is nonzero: the first is $0$ precisely when $B_{1} (ω) = - B_{0} (ω)$ , in which case the second is $\pm 2$ , and otherwise the first is $\pm 2$ and the second $0$ . Hence $A_{0} (B_{0} + B_{1}) + A_{1} (B_{0} - B_{1})$ equals $\pm 2$ at every $ω$ , so its absolute value is bounded by $2$ pointwise and $E [A_{0} B_{0}] + E [A_{0} B_{1}] + E [A_{1} B_{0}] - E [A_{1} B_{1}] = E [A_{0} (B_{0} + B_{1}) + A_{1} (B_{0} - B_{1})]$ by linearity [F2], the variables being bounded hence integrable. The monotonicity and modulus bound of [F2] applied to the pointwise bound $- 2 \leq A_{0} (B_{0} + B_{1}) + A_{1} (B_{0} - B_{1}) \leq 2$ give the stated $\leq 2$ bound.

1.2givenF1F3algebra

[Positive-probability sequences] Since $p_{j_{k}} > 0$ , each event ${X_{k} = j_{k}}$ is nonempty and $j_{k} \in X_{k} (Ω)$ . By mutual independence [F3] applied to the full index set $J = {1, \dots, N}$ and the selection $x_{k} = j_{k}$ , $P (X_{k} = j_{k} for all k) = \prod_{k} P (X_{k} = j_{k}) = \prod_{k} p_{j_{k}}$ , which is a product of positive reals and hence positive. If an event $R$ is disjoint from ${X_{k} = j_{k} for all k}$ , then $P (R) \leq 1 - \prod_{k} p_{j_{k}} < 1$ by additivity and complementation [F1].

1.3givenF2F4F5algebra

[Binomial frequency moments] By [F4], $S$ is a sum of $N$ mutually independent Bernoulli $(p)$ variables, with $E [S] = N p$ and $Var (S) = N p (1 - p)$ . Linearity [F2] gives $E [S / N] = \frac{1}{N} E [S] = p$ ; and by the definition of variance [F5], $Var (S / N) = E [(S / N - p)^{2}] = \frac{1}{N^{2}} E [(S - N p)^{2}] = \frac{1}{N^{2}} Var (S) = \frac{p (1 - p)}{N}$ . Applying the Chebyshev inequality [F5] to the square-integrable variable $S / N$ with parameter $ε > 0$ gives $P (∣ S / N - p ∣ \geq ε) \leq p (1 - p) / (N ε^{2})$ .

2.1givenF1F3F6algebra∎

[Multinomial count law] A sequence $(j_{1}, \dots, j_{N})$ is exactly a function $c : {1, \dots, N} \to {1, \dots, m}$ , with fibre sizes $n_{j}$ ; by [F6] the number of such functions with prescribed fibre sizes is $(\binom{N}{n_{1}, \dots, n_{m}})$ . If some $j_{k} \notin X_{k} (Ω)$ , the sequence event is empty, and $p_{j_{k}} = P (X_{k} = j_{k}) = 0$ , so its probability and $\prod_{k} p_{j_{k}}$ are both zero. Otherwise every selected label lies in the corresponding image, and independence [F3] gives probability $\prod_{k} p_{j_{k}}$ . Thus in either case each sequence has probability $\prod_{k} p_{j_{k}} = \prod_{j} p_{j}^{n_{j}}$ , because the exponent of $p_{j}$ is the number of $k$ with $j_{k} = j$ , namely $n_{j}$ ; when $n_{j} = 0$ the sequence contains no factor $p_{j}$ , and the displayed product convention in (d) assigns that factor the value $1$ , also when $p_{j} = 0$ . The count event is the disjoint union of the corresponding sequence events, so finite additivity [F1] gives probability $(\binom{N}{n_{1}, \dots, n_{m}}) \prod_{j} p_{j}^{n_{j}}$ .

The CHSH bound and the finite-sampling law for independent trials

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources