# 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.

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$$.

• You want $(\frac12)^d$ rather than $d^{1/2}$. For expectation, you can add up these probabilities as though they were independent, which is why I focused on the variance. – Misha Lavrov May 4 at 17:15
• With $m$ edges don't we have $m$ pairs of adjacent vertices? Your formula for the variance is only taking the vertices in increasing order. – saulspatz May 4 at 17:17
• @saulspatz Good point, I had forgotten that I had made that decision. Either way, we need to multiply by $2$ at some point, but I'll edit. – Misha Lavrov May 4 at 17:18
• @PaulRoberts $\land$ is AND, not OR. If $v$ and $u$ are adjacent, the probability is $0$. Otherwise, the events are independent. – saulspatz May 4 at 17:27
• The probability $\Pr[A_i \land A_j]$ is $0$, which gives a covariance of $-(\frac12)^{2d}$. – Misha Lavrov May 4 at 17:54