The Indicator Counting Trick
How can a difficult global count be built from small yes-or-no questions?
How this lesson unfolds.
Begin with How can one idea count many different things? The sequence then connects A truth value becomes a number and builds toward The complete indicator pipeline.
How can one idea count many different things?
Turn each candidate object into a precise yes-or-no question, encode yes as 1 and no as 0, then add the answers. The surrounding story may change, but the counting engine stays the same.
- Learning goalExplain indicator counting hook and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionA truth value becomes a number
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
What exactly is an indicator?
For any condition C, the indicator 1{C} equals 1 when C is true and 0 otherwise. An indicator is a numbered truth value, not a mysterious extra object.
For any condition C, the indicator 1{C} equals 1 when C is true and 0 otherwise.
- Learning goalExplain indicator definition and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionA snapshot is not yet probability
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
What changes when one observed count becomes an expectation?
A realized graph gives one value X(omega). A random graph model describes many possible graphs, and E[X] is the probability-weighted average across those possible worlds—not necessarily a value observed in this snapshot.
- Learning goalExplain observation versus random model and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionMeet one world with many questions
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
What will we count in the five-person app?
Use V={A,B,C,D,E} and observed friendships E={AB,AC,BC}. The same world supports questions about Alice's degree, total friendships, triangles, isolated people, premium revenue, and badge types.
Use V={A,B,C,D,E} and observed friendships E={AB,AC,BC}.
- Learning goalExplain shared five person world and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionChoose the building block first
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
What should one indicator represent?
Match the global target to one local candidate: a neighbour, unordered pair, unordered triple, person, customer, or badge type. The formula becomes natural only after this unit is chosen.
- Learning goalExplain local building block and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionIndices reveal the question
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
Why do some indicators have one, two, or three indices?
One index tests one person, two indices test one pair, and three indices test one triple. For unordered objects, restrictions such as i<j and i<j<k give one representation and prevent duplicate counting.
- Learning goalExplain indicator indices and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionCoverage plus uniqueness gives an exact count
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
How does a checklist prevent counting mistakes?
List every possible candidate and list each exactly once. Coverage prevents omissions; uniqueness prevents duplicates such as counting AB and BA as two friendships.
- Learning goalExplain coverage and uniqueness and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionSigma simply adds local answers
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
What does summation notation mean here?
For every possible neighbour u of Alice, I_Au contributes either 1 or 0. The sum over u not equal to A is the mathematical version of a loop that adds every successful local answer.
The sum over u not equal to A is the mathematical version of a loop that adds every successful local answer.
- Learning goalExplain indicator summation and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionCount Alice's friends
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
How do four neighbour questions become one degree?
Alice's indicators against B,C,D,E are 1,1,0,0, so deg(A)=2. If every possible Alice-edge has marginal probability p, linearity gives E[deg(A)]=4p; independence is not needed for this expectation.
Alice's indicators against B,C,D,E are 1,1,0,0, so deg(A)=2.If every possible Alice-edge has marginal probability p, linearity gives E[deg(A)]=4p; independence is not needed for this expectation.
- Learning goalExplain degree by indicators and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionCount every friendship once
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
How do pair indicators count all edges?
Five people create C(5,2)=10 unordered pairs. Summing I_ij over i<j gives M=3 in the observed graph and E[M]=10p when each pair has marginal friendship probability p.
Five people create C(5,2)=10 unordered pairs.Summing I_ij over i<j gives M=3 in the observed graph and E[M]=10p when each pair has marginal friendship probability p.
- Learning goalExplain edge count by pairs and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionCount completely connected triples
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
When does one triple form a triangle?
For i<j<k, the triangle indicator is T_ijk=I_ij I_ik I_jk. Only ABC succeeds in the observed graph. With independent edges of common probability p, E[T]=C(5,3)p^3=10p^3.
For i<j<k, the triangle indicator is T_ijk=I_ij I_ik I_jk.With independent edges of common probability p, E[T]=C(5,3)p^3=10p^3.
- Learning goalExplain triangle count by products and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionCount people with no friends
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
Can an indicator test a property of an entire person?
Let J_i=1 when deg(i)=0. Diana and Ethan are isolated, so the observed total is 2. Under independent edge probability p, E[sum_i J_i]=5(1-p)^4; the J_i themselves need not be independent for linearity.
Let J_i=1 when deg(i)=0.Under independent edge probability p, E[sum_i J_i]=5(1-p)^4; the J_i themselves need not be independent for linearity.
- Learning goalExplain isolated vertex count and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionLet each yes carry a weight
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
How can indicators total premium revenue?
Multiply customer i's purchase indicator by value w_i. The observed weighted sum is 500+300+400=1200. In general E[R]=sum_i w_i p_i; with common purchase probability p and total value 2800, E[R]=2800p.
The observed weighted sum is 500+300+400=1200.In general E[R]=sum_i w_i p_i; with common purchase probability p and total value 2800, E[R]=2800p.
- Learning goalExplain weighted indicator sum and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionCount missing badge types
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
What is the right indicator when the target is a type?
Attach K_j to badge type j, not to each award: K_j=1 when type j never appears. Types 3 and 5 are missing in the snapshot. With n independent uniform awards among five types, E[X]=5(4/5)^n.
Attach K_j to badge type j, not to each award: K_j=1 when type j never appears.With n independent uniform awards among five types, E[X]=5(4/5)^n.
- Learning goalExplain missing types indicators and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionCount the complement when it is simpler
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
How can missing types reveal observed types?
Every type is either observed or missing, so Y=5-X. The snapshot has 3 observed types, and the random model gives E[Y]=5-E[X]=5[1-(4/5)^n]. Complement counting replaces a difficult direct event with a simpler absence event.
Every type is either observed or missing, so Y=5-X.The snapshot has 3 observed types, and the random model gives E[Y]=5-E[X]=5[1-(4/5)^n].
- Learning goalExplain complement counting and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionOne world supports four counting lenses
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
What changes when the question changes?
Alice's degree uses neighbours, total friendships use unordered pairs, revenue uses customers with weights, and missing badges use types. The people stay fixed; the local building block and indicator change.
- Learning goalExplain compare counting lenses and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionThe complete indicator pipeline
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.
How can the counting trick be reused safely?
Define the global target, choose all valid local blocks, ask one precise condition per block, encode it as an indicator, sum once over the candidate set, then use linearity of expectation when an average count is needed.
- Learning goalExplain indicator counting pipeline and identify the local candidate set before summing.
- Helpful foundationsfinite sets · basic probability · summation notation
- Common trapLinearity of expectation does not require independence, although product probabilities such as p^3 and (1-p)^4 do require the stated independent-edge model.
- Next connectionUse indicators in a new probability model
More context
The portrait diagram reads from the defining formula through three checks, a concrete five-person visual, and one conclusion.