For a set T, let
W(T):=\sum_{v \in T} w_{v}
We can modify the above algorithm by changing “randomly choose u or v with equal probability” to “randomly choose u with probability p_{u v} and v with probability 1-p_{u v}.” Redefine C to be any cover of minimal weight, instead of minimal size. Find, with proof, the value of p_{u v} that ensures that for all i \geq 0,
\mathbf{E}\left[W\left(S_{i} \cap C\right)\right] \geq \mathbf{E}[W(S \backslash C)]