I have to do the following exercise.
Suppose that we have a 3-regular graph (i.e. each vertex is connected with an edge to three other vertices) with n vertices in total. To each vertex, we assign a random number from a uniform distribution over [0,1]. Then we select a set of vertices using the following rule: a vertex will be selected if its random number is greater than the random numbers of all of its three neighbors.
I need to write a function in Python called "vertices_selected" that takes the number of vertices, n, as an input and returns the expected number of vertices that will be selected. For this question, the input n will always be such that a 3-regular graph is possible.
I have a hint that I need to use the following property:
Best Answer
Let $X_i$ be $1$ if the vertex $i$ is selected, $0$ otherwise. It is easy to see that $E(X_i)=1/4$ for all $i$. Namely, the random number on the vertex $i$ must be the largest out of four independently chosen numbers - that of the vertex $i$ and of its three neighbours, so the probability that this happens is $1/4$.
So, $\sum_{i=1}^{n} X_i$ is the total number of chosen vertices. Its expectation is:
$$E\left(\sum_{i=1}^{n}X_i\right)=\sum_{i=1}^{n}E(X_i)=\sum_{i=1}^{n}\frac{1}{4}=\frac{n}{4}$$