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

  • 1
    $\begingroup$ 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. $\endgroup$ – Misha Lavrov May 4 at 17:15
  • $\begingroup$ 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. $\endgroup$ – saulspatz May 4 at 17:17
  • $\begingroup$ @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. $\endgroup$ – Misha Lavrov May 4 at 17:18
  • $\begingroup$ @PaulRoberts $\land$ is AND, not OR. If $v$ and $u$ are adjacent, the probability is $0$. Otherwise, the events are independent. $\endgroup$ – saulspatz May 4 at 17:27
  • $\begingroup$ The probability $\Pr[A_i \land A_j]$ is $0$, which gives a covariance of $-(\frac12)^{2d}$. $\endgroup$ – Misha Lavrov May 4 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy