TheoremStatement: Literature-sourcedProof: 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.

Uniform counting is finite indicator expectation

Statement

Let $X$ be a finite nonempty set with $p_{x} = 1 / ∣ X ∣$ for each $x$ , let $S \subseteq X$ , and define $g (x) = 1$ for $x \in S$ and $g (x) = 0$ otherwise. Then the expectation task for $(X, p, g)$ has target $μ = E [g] = \frac{∣ S ∣}{∣ X ∣} .$

Facts & Assumptions

Given: The finite nonempty set $X$ , its uniform probability law, and the indicator function $g = 1_{S}$ of a subset $S$ .

[F1]

Finite expectation-estimation task: the target is the weighted finite sum $\sum_{x \in X} p_{x} g (x)$ .

[F2]

Finite probability spaces, outcome weights, events, and event probabilities: an event probability is the sum of the weights of its outcomes.

[F3]

Expectation of a real random variable on a finite probability space: expectation is the finite weighted sum over outcomes.

Proof

1.1givenF1algebra

For the uniform law, $p_{x} = 1 / ∣ X ∣$ for every $x \in X$ . By [F1], $μ = \sum_{x \in X} ∣ X ∣^{- 1} 1_{S} (x)$ .

2.1givenF2F3step 1.1algebra∎

The summand is $∣ X ∣^{- 1}$ exactly for $x \in S$ and zero otherwise. The sum therefore has $∣ S ∣$ equal terms, so $μ = ∣ S ∣ / ∣ X ∣$ . By [F2]–[F3] this is also $\Pr (S)$ .

Depends on

Used by

Quantum counting as an expectation special case Algorithm

Dependency tree · two levels

8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum Amplitude Amplification and Estimation, Section 4 (standard reference, not scraped)
Andrew M. Childs, Lecture Notes on Quantum Algorithms, Section 19.3 (standard reference, not scraped)