Let $G= (V,E)$ be an undirected graph with real-valued edge weights. Let $W$ denote the total sum of edge weights. Suppose we color all of the vertices either red or blue, independently at random. We say that an edge is ”bichromatic” if its endpoints have two colors, and ”monochromatic” if both its endpoints have the same color. We say that an edge is ”monochromatically red” if both endpoints are red
$a)$ What is the expected total weight of bichromatic edges (as a function of $W$?
$b)$ What is the expected total weight of monochromatically red edges?
$c)$ What is the expected total weight of monochromatically blue edges?
$d)$ What is the expected total weight of monochromatic edges?
I can't figure out this question.
I tried taking the graph as square and tried taking cases as follows:
- When all are red/blue – weight fo bio is zero
- When one is red and all others are blue(the same when one is blue and other are red) – we have two biochromatic weights
- When there are two blue and two red: We can have two different cases where we have "two"( when the same color is one edge) or four(alternate red-blue).
That gives a total of 10 total biochromatic edges and we know that total weight of the graph is $W$, but how can I possibly relate this to W if I don't know the individual weights of the edges?
Best Answer
All you need is linearity of expectation. Each edge has four equiprobable possibilities: monochromatic red, monochromatic blue, and two versions of bichromatic, so it contributes $\frac14$ of its weight to each of those cases. Thus the expected weight of monochromatic red edges is $\frac W4$, the same for monochromatic blue, and the expected weight of bichromatic edges is $\frac W2$ (and the same for monochromatic red and blue together).