Definition 35.1 (Indicator variable) An indicator variable \(\mathbb{I}_A\) for an event \(A\) is a random variable defined as: \[\mathbb{I}_A =
\begin{cases}
1 & \text{if event } A \text{ occurs}, \\
0 & \text{if event } A \text{ does not occur}.
\end{cases}
\]
The indicator variable \(\mathbb{I}_A\) “indicates” whether the event \(A\) happens (1) or not (0).
The expected value of an indicator variable is equal to the probability of the event \(A\): \[E[\mathbb{I}_A] = 1 \cdot P(A) + 0 \cdot P(A^c) = P(A)\] This is known as the fundamental bridge, as it allows us to convert between probability and expectation.
Indicator variables are often used in linearity of expectation calculations. This allows us to break down a problem into easy-to-solve small problems. For example, if \(X = \sum_{i=1}^n \mathbb{I}_{A_i}\), then: \[E[X] = \sum_{i=1}^n E[\mathbb{I}_{A_i}] = \sum_{i=1}^n P(A_i)\]
Example 35.1 In a group of \(n\) people, what is the expected number of distinct birthdays among the \(n\) people (the expected number of days on which at least one of the people was born)? What is the expected number of people sharing a birthday (any day)?
Solution. Let \(X\) be the number of distinct birthdays, and write \(X=I_{1}+\cdots+I_{365}\), where \[I_{j}=\begin{cases}
1 & \textrm{if someone was born on day }j\\
0 & \textrm{otherwise}
\end{cases}.\] Then \[\begin{aligned}
E(I_{j}) & =P(\textrm{someone was born on day }j)\\
& =1-P(\textrm{no one was born on day }j)\\
& =1-\left(\frac{364}{365}\right)^{n}.\end{aligned}\] Then by linearity, \[E(X)=365\left(1-\left(\frac{364}{365}\right)^{n}\right).\] Let \(Y\) be the number of people sharing a birthday, and \(Y=J_{1}+\cdots+J_{n}\) where \(J_{k}\) is an indicator that the \(j\)-th person shares his birthday with somebody else. \[\begin{aligned}
E(J_{k}) & =P(\textrm{someone shares birthday with }k)\\
& =1-P(\textrm{no one shares birthday with }k)\\
& =1-\left(\frac{364}{365}\right)^{n-1}.\end{aligned}\] Therefore, \[E(Y)=\sum_{k=1}^{n}E(J_{k})=n\left(1-\left(\frac{364}{365}\right)^{n-1}\right).\]
For some numeric values, \(E(Y)=2.3\) if \(n=30\); \(E(Y)=6.3\) if \(n=50\).
Example 35.2 Let \(\Pi\) be a permutation over \(\{1,2,\dots,n\}\). That is a reordering of the numbers. A fixed point of a permutation are the points not moved by the permutation. For example, in the permutation below \[\begin{array}{ccccc}
& 1 & 2 & 3 & 4\\
\Pi & 2 & 4 & 3 & 1
\end{array}\]
The fixed point is 3. Find the expected number of fixed points of a random permutation.
Solution. Let \(X\) be the number of fixed points of a random permutation. Then \(X=\sum_{k=1}^{n}\boldsymbol{1}_{\Pi(k)=k}\) where \(\boldsymbol{1}_{\Pi(k)=k}\) indicates the \(k\)-th number stays the same after the permutation. By linearity, \[E(X)=E\left(\sum_{k=1}^{n}\boldsymbol{1}_{\Pi(k)=k}\right)=\sum_{k=1}^{n}E\left(\boldsymbol{1}_{\Pi(k)=k}\right)=\sum_{k=1}^{n}\frac{1}{n}=1.\]
Example 35.3 (Buffon’s needle) A plan is ruled by the lines \(y=0,\pm 1,\pm 2,...\) and a needle of unit length is cast randomly on to the plane. What is the probability that it intersects some line?
Solution. Here we sketch an intuitive approach. A more rigorous one will be given in Example 44.2.
Let \(X\) be the number of times the needle crosses a line. The needle can cross a line either \(1\) or \(0\) times. Thus, \(P(\text{intersection})=E(X)\).
Consider dropping any (continuous) curve of unit length onto the surface. Divide the curve into \(N\) straight line segments, each of length \(1/N\). Let \(X_{i}\) be the indicator for the \(i\)-th segment crossing a line. Then, \[E(X)=E\left(\sum X_{i}\right)=\sum E(X_{i})=N\cdot E(X_{i}).\] We don’t necessarily have to compute this expectation, but by this line of reasoning: \(E(X)\) is proportional to the length of the curve, regardless the shape of the curve. If we can compute \(E(X)\) for some curve, then \(E(X)\) is the same for all curves with the same length.
Consider a circle of diameter \(d=1\). The circle always crosses the lines twice for sure. That is, \(E(X_{\textrm{circle}})=2\). The length of the circle is \(\pi\). Therefore, for any curve (including a needle) of length \(\pi\) we have \(E(X_\pi)=2\).
For a needle of unit length, scale it down by \(\pi\), we have \(E(X)=2/\pi\). Therefore, \[P(\text{intersection})=\frac{2}{\pi}.\]
# number of simulationsN <-10000# number of crossingsX <-numeric(N)set.seed(0)# run simulationfor (i in1:N) {# randomly generate the position of the needle's midpoint# distance from the nearest line y <-runif(1, min =0, max =1/2) # randomly generate the angle of the needle (in radians) θ <-runif(1, min =0, max = pi/2) # check if the needle crosses a lineif (y <=1/2*sin(θ)) X[i] <-1else X[i] <-0}π <-2/mean(X)cat("Estimated value of π:", π)