PropositionStatement: AI-generatedProof: AI-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.

Indicator expectations and exceptional-vertex probabilities

Statement

Let $n \in N$ with $n \geq 1$ , and let $D_{1}, \dots, D_{n}$ be integer-valued random variables on a common finite probability space with identical distributions: $P (D_{v} = j) = P (D_{1} = j)$ for every $v$ and integer $j$ . No independence is assumed. For an integer $k$ , define $X_{k} = \sum_{v = 1}^{n} 1_{{D_{v} = k}}$ , $X_{\leq k} = \sum_{v = 1}^{n} 1_{{D_{v} \leq k}}$ , and $X_{\geq k} = \sum_{v = 1}^{n} 1_{{D_{v} \geq k}}$ . Then $E X_{k} = n P (D_{1} = k)$ , and $P (\min_{v} D_{v} \leq k) \leq E X_{\leq k}$ and $P (\max_{v} D_{v} \geq k) \leq E X_{\geq k}$ . These identities and bounds do not by themselves approximate the law of $X_{k}$ .

Statement references

The natural numbers ℕ (von Neumann)

Finite probability spaces, outcome weights, events, and event probabilities

Real random variables on finite probability spaces and their finite distributions

Expectation of a real random variable on a finite probability space

The indicator random variable of an event

Facts & Assumptions

Given: The positive integer $n$ , finite probability space, variables $D_{1}, \dots, D_{n}$ , and integer $k$ in the statement.

Goal: Establish the expectation identity and both exceptional-count bounds.

[F1]

A finite probability space has finitely many outcomes with nonnegative weights summing to one; events are subsets, and their probabilities are sums of their weights (Finite probability spaces, outcome weights, events, and event probabilities). A real random variable is a function on the outcomes, and its distribution records the probabilities of its values (Real random variables on finite probability spaces and their finite distributions).

[F2]

Expectation is the finite weighted sum of the values of a random variable (Expectation of a real random variable on a finite probability space). The indicator of an event is one on that event and zero elsewhere (The indicator random variable of an event).

[F3]

The expectation of an event indicator equals the probability of that event; a finite sum of indicators counts the events occurring at an outcome (Indicators turn event probabilities, intersections, and finite counts into expectations and products).

[F4]

Expectation is linear for finite families of random variables, without an independence assumption (Expectation is linear for every finite family of random variables, without any independence hypothesis).

[F5]

If $Y$ is nonnegative and $a > 0$ on a finite probability space, then $P (Y \geq a) \leq E Y / a$ (Markov's inequality on a finite probability space).

Proof

technique · direct

1.1givenF1F2F3F4

Each event ${D_{v} = k}$ is a subset of the finite outcome space, and its indicator is a real random variable. By finite linearity and the indicator expectation identity, $E X_{k} = \sum_{v = 1}^{n} P (D_{v} = k) = n P (D_{1} = k)$ , where the last equality uses identical distributions.

1.2givenF2F3

At each outcome, $X_{\leq k}$ counts the indices with $D_{v} \leq k$ , while $X_{\geq k}$ counts those with $D_{v} \geq k$ . Thus both counts are nonnegative, and, since $n \geq 1$ , the events ${\min_{v} D_{v} \leq k}$ and ${X_{\leq k} \geq 1}$ coincide, as do ${\max_{v} D_{v} \geq k}$ and ${X_{\geq k} \geq 1}$ .

2.1step 1.1step 1.2F5∎

Applying the nonnegative Markov bound with $a = 1$ to each count and using the event identities in step 1.2 gives both claimed inequalities. Together with step 1.1 this proves the result; no independence was used.

Depends on

Used by · 5

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.