Expectation of sinks in a random directed d-regular graph Given an arbitrary graph $G = (V,E)$, that is d-regular, so every vertex has degree d. An edge (u,v) is directed towards u or v with equal probability, mutually independently. A sink is a vertex U with all incident edges pointing towards itself.
S denotes the number of sinks in a random orientation of edges.
What is the expectation and variance of S?
I am working under the assumption that each choice is independent, but when combined, each edge effects more than one vertex, so I am quite lost.
 A: In general, if we have a random variable $\mathbf X$ that is the sum of random variables $\mathbf X_1, \mathbf X_2, \dots, \mathbf X_n$, then we have
$$
   \operatorname{Var}[\mathbf X] = \sum_{i=1}^n \operatorname{Var}[\mathbf X_i] + 2\sum_{i=1}^n \sum_{j=i+1}^n \operatorname{Cov}[\mathbf X_i, \mathbf X_j]
$$
where $\operatorname{Cov}[\mathbf X_i, \mathbf X_j]$ is the covariance.
In this case, you want $\mathbf X_1, \dots, \mathbf X_n$ to be indicator random variables: $\mathbf X_i$ is $1$ if the $i^{\text{th}}$ vertex is a sink, and $0$ is not. For indicator random variables, variance and covariance are simpler. If $\mathbf X_i$ is the indicator random variable of event $A_i$, then

*

*$\operatorname{Var}[\mathbf X_i] = \Pr[A_i] \cdot \Pr[\neg A_i]$, and

*$\operatorname{Cov}[\mathbf X_i, \mathbf X_j] = \Pr[A_i \land A_j] - \Pr[A_i] \cdot \Pr[A_j]$.

In particular, if $A_i$ and $A_j$ are independent events, then $\operatorname{Cov}[\mathbf X_i, \mathbf X_j] = 0$.

In this problem, almost all pairs $(\mathbf X_i, \mathbf X_j)$ are independent. The exception is adjacent vertices, which cannot be sinks at the same time. With $m$ edges, the second sum will have $m$ pairs of adjacent vertices (for which you should compute the covariance, and at the end multiply by $2$) and all other covariances will be $0$.
