# On uniform randomness of the weight of the remaining edges of a graph after deleting some of them

Suppose we have a graph $$G(V,E,W)$$, where $$V$$ and $$E$$ are the set of vertices and edges and $$W$$ is non-negative weight on the edges. Let $$w(e)$$ be the weight of edge $$e$$ and $$N(e)$$ be the neighboring edges of $$e$$. An edge $$e$$ is locally subdominant if its weight is smaller than all of its neighbors. With this background Let we have the following algorithm,

for e in E
if w(e) is locally sub-dominant
delete e from the graph G
double weights of all e in  N(e)


My question is after this loop ends what can we say about uniform randomness of the remaining edges. Are they still uniform random?

• What do you mean by "uniform randomness"? – Yuval Filmus Oct 8 '18 at 16:55

Let us consider the simplest case, that of a path of length two edges, which are drawn uniformly and independently from $$[0,1]$$. Let us suppose that the first edge is sub-dominant, which happens with probability 1/2. The probability that the weight of second edge is at most $$t \in [0,1]$$ is $$\Pr[x \leq y \leq t \mid x \leq y] = \Pr[x,y \leq t] = t^2.$$ Here $$x$$ is the weight of the first edge, and $$y$$ is the weight of the second edge. We see that even before doubling, the distribution of $$y$$ is non-uniform.
Next, let us examine the case of a star with three edges, again drawn uniformly and independently from $$[0,1]$$. Again suppose that the first edge is sub-dominant, which happens with probability 1/3. The probability that the weight of the second edge is at most $$t \in [0,1]$$ while that of the third edge is at most $$u \in [0,1]$$ is $$\Pr[y \leq t, z \leq u \mid x \leq y,z] = 3 \int_0^{\min(t,u)} (t-x)(u-x) \, dx = \\ 3tum - \frac{3}{2}(t+u)m^2 + m^3.$$ Here $$x,y,z$$ are the weights of the first, second, and third edges, respectively, and $$m = \min(t,u)$$. Substituting $$u = 1$$, we obtain $$\Pr[y \leq t \mid x \leq y,z] = \frac{3t^2-t^3}{2}.$$ Calculation shows that for generic $$t,u$$, $$\Pr[y \leq t, z \leq u \mid x \leq y,z] \neq \Pr[y \leq t \mid x \leq y,z] \Pr[z \leq u \mid x \leq y,z],$$ that is, the remaining weights are no longer independent.