Indicator Variables and Linearity of Expectation

From Graph Events to Counts

A random graph contains many yes-or-no events: a particular edge is present, a vertex is isolated, or a chosen vertex set is independent. An indicator variable records whether one such event occurs. Adding indicators then gives an exact count, graph by graph. The key advantage is that the expected value of this sum is the sum of the individual expectations, even when the events are dependent.

Throughout, graphs are finite and simple. In the Bernoulli random graph \(G(n,p)\), the vertex set is \(\{1,\dots,n\}\), and each of the \(\binom n2\) possible edges is included independently with probability \(p\), where \(0\le p\le1\). Thus a random outcome is one graph on this fixed vertex set. Its probability is determined by the independent edge choices.

Definition: For an event \(A\) in a finite probability space, its indicator variable is \(I_A=1\) if \(A\) occurs and \(I_A=0\) otherwise. Its expectation is \(\mathbb{E}[I_A]=\mathbb{P}(A)\).

The expectation identity follows directly from the two possible values of \(I_A\): the value \(1\) occurs with probability \(\mathbb{P}(A)\), while the value \(0\) occurs with probability \(1-\mathbb{P}(A)\). Therefore \(\mathbb{E}[I_A]=1\cdot\mathbb{P}(A)+0\cdot(1-\mathbb{P}(A))=\mathbb{P}(A)\).

If \(A_1,\dots,A_r\) are events, then for every outcome the sum \(I_{A_1}+\cdots+I_{A_r}\) equals the number of those events that occur. This is a pointwise identity, not a probabilistic approximation. For example, if each \(A_i\) says that a particular candidate edge is present, the sum is exactly the number of present candidate edges.

Linearity of Expectation

Theorem (Linearity of expectation): If \(X_1,\dots,X_r\) are real-valued random variables on a finite probability space, then \(\mathbb{E}[X_1+\cdots+X_r]=\mathbb{E}[X_1]+\cdots+\mathbb{E}[X_r]\). No independence assumption is required.

Proof. Let \(\Omega\) be the finite outcome set and let \(\mathbb{P}(\omega)\) be the probability of outcome \(\omega\). By the definition of expectation and by rearranging finite sums,

\begin{aligned} \mathbb{E}\!\left[\sum_{i=1}^{r}X_i\right] &=\sum_{\omega\in\Omega}\mathbb{P}(\omega) \left(\sum_{i=1}^{r}X_i(\omega)\right)\\ &=\sum_{i=1}^{r}\left(\sum_{\omega\in\Omega} \mathbb{P}(\omega)X_i(\omega)\right)\\ &=\sum_{i=1}^{r}\mathbb{E}[X_i]. \end{aligned}

Every equality uses only the definition of expectation and the fact that finite sums can be reordered. If \(r=0\), both sides are the expectation of the zero random variable, which is \(0\). Independence is not used. \(\square\)

Applying the theorem to event indicators gives a convenient counting rule.

Counting rule: If \(N\) counts how many of the events \(A_1,\dots,A_r\) occur, then \(N=\sum_{i=1}^{r}I_{A_i}\) for every outcome, and \(\mathbb{E}[N]=\sum_{i=1}^{r}\mathbb{P}(A_i)\). The events need not be independent.

The crucial separation is that an expected count uses a sum of event probabilities. Independence may be useful for calculating an individual probability or a joint probability, but it is not a condition for adding expectations.

Worked Examples

Worked Example: Expected Number of Edges

Let \(G\) be sampled from \(G(5,\tfrac13)\). Find and check the expected number of edges.

For each of the \(\binom52\) possible edges \(e\), let \(I_e\) be \(1\) when \(e\) is present and \(0\) otherwise. The edge count is \(M=\sum_e I_e\), and \(\mathbb{E}[I_e]=\tfrac13\) for each edge. There are \(\binom52=5\cdot4/2=10\) possible edges, so linearity gives

\mathbb{E}[M]=\sum_e \mathbb{E}[I_e] =10\cdot\frac13=\frac{10}{3}.

Check: The same count can be obtained by considering each of the ten candidate edges separately: each contributes \(\tfrac13\) to the expectation, for a total of \(10/3\). An expectation need not be an integer; individual outcomes have integer edge counts, but their probability-weighted average need not.

Worked Example: Expected Number of Isolated Vertices

Let \(G\) be sampled from \(G(4,\tfrac12)\). A vertex is isolated if no edge is incident with it. Find the expected number of isolated vertices.

For \(i\in\{1,2,3,4\}\), let \(I_i\) indicate that vertex \(i\) is isolated. Exactly three possible edges are incident with \(i\). All three must be absent, and their edge choices are independent, so

\mathbb{P}(I_i=1)=\left(1-\frac12\right)^3 =\left(\frac12\right)^3=\frac18.

The total number \(Z\) of isolated vertices is \(I_1+I_2+I_3+I_4\). Hence

\mathbb{E}[Z]=\sum_{i=1}^{4}\mathbb{E}[I_i] =4\cdot\frac18=\frac12.

Check: There are \(\binom42=6\) possible edges, so the sample space has \(2^6=64\) equally likely graphs. For a specified vertex to be isolated, its three incident edges must be absent; the other three edges can be chosen freely. Thus \(2^3=8\) of the \(64\) graphs make that vertex isolated, giving probability \(8/64=1/8\), as above. Summing over the four specified vertices again gives \(4/8=1/2\).

Worked Example: Expected Number of Independent Triples

In the same model \(G(4,\tfrac12)\), find the expected number of independent sets of size \(3\). A vertex set is independent if no two of its vertices are joined by an edge.

There are \(\binom43=4\) possible three-vertex sets. For each such set \(S\), let \(J_S\) indicate that \(S\) is independent. It has \(\binom32=3\) possible internal edges, all of which must be absent. Therefore

\mathbb{P}(J_S=1)=\left(1-\frac12\right)^3 =\left(\frac12\right)^3=\frac18.

If \(W\) is the number of independent triples, then \(W=\sum_{|S|=3}J_S\). By linearity,

\mathbb{E}[W]=\sum_{|S|=3}\mathbb{E}[J_S] =4\cdot\frac18=\frac12.

Check: The four candidate triples each have probability \(1/8\) of being independent, so their expected contributions sum to \(4/8=1/2\). Overlap between triples does not change this calculation. For instance, the triples \(\{1,2,3\}\) and \(\{1,2,4\}\) share the edge \(12\). Both are independent exactly when the five distinct edges \(12,13,23,14,24\) are absent. Thus their joint probability is \((1/2)^5=1/32\), whereas the product of their individual probabilities is \((1/8)(1/8)=1/64\). The indicators are not independent, but their expectations can still be added.

Counting Substructures by Indicators

The same construction applies whenever a graph quantity can be written as a sum of yes-or-no contributions. To count occurrences of a chosen type of substructure, index the candidate occurrences and give each candidate an indicator that equals \(1\) exactly when it occurs. The sum then counts the occurrences in each outcome; its expectation is the sum of their probabilities. Care is needed to define what counts as a distinct occurrence—for example, whether two copies with different vertex sets are counted separately.

For a count indexed by vertex sets, the candidate events can overlap substantially. An edge may belong to many candidate sets; one edge choice can therefore affect several indicators at once. This dependence may complicate joint probabilities, but it does not alter the pointwise count identity or the linearity theorem. In practice, the main work is usually to calculate each event probability correctly and to make sure the index set includes each candidate exactly as intended.

For example, in the independent-triple calculation, the index set consists of all four three-element subsets of \(\{1,2,3,4\}\). Each is counted once, regardless of whether another triple is independent in the same graph. The probability that one specified triple is independent depends only on its three internal edges; the remaining edge choices do not affect that event. This is why the single-event probability is easy to compute even though indicators for different triples can be dependent.

Common Pitfall: Assuming Independence

Linearity of expectation is sometimes misapplied by assuming the indicators in a count are independent, or by multiplying probabilities when a joint event is needed. In \(G(4,\tfrac12)\), the probability that vertex \(1\) is isolated is \(1/8\), and the probability that vertex \(2\) is isolated is also \(1/8\). A tempting but wrong calculation for the probability that both are isolated is \((1/8)(1/8)=1/64\).

The correction is to count the required edge choices. Both vertices are isolated exactly when the five edges \(12,13,14,23,24\) are absent; edge \(34\) is unrestricted. Hence

\mathbb{P}(\text{vertices 1 and 2 are both isolated}) =\left(\frac12\right)^5=\frac1{32},

not \(1/64\). In the same graph, there are \(\binom42=6\) candidate pairs of isolated vertices. If \(Y\) counts such pairs, each pair has probability \(1/32\), so \(\mathbb{E}[Y]=6\cdot(1/32)=3/16\). Treating the two isolation events for each pair as independent would instead give \(6\cdot(1/64)=3/32\), which is wrong.

The distinction is useful: use linearity to add the expectations of individual indicators, without an independence requirement. Use independence only when it is actually available and needed to calculate a probability involving multiple events.

Check Your Understanding

For each question, specify the indicators or events being counted before calculating.

In \(G(6,\tfrac14)\), what is the expected number of edges?
In \(G(5,\tfrac12)\), what is the probability that a specified vertex is isolated, and what is the expected number of isolated vertices?
In \(G(5,\tfrac12)\), how many candidate independent sets of size \(2\) are there, and what is their expected number?
Explain why linearity of expectation applies to the independent-triple count even though two triple indicators can be dependent.
In \(G(4,\tfrac12)\), calculate the probability that vertices \(1\) and \(2\) are both isolated by listing the edge constraints. Why is multiplying their individual isolation probabilities invalid?