I have a question concerning the removal of samples from a set of uniformly distributed samples.
Let $E = \{ X_{ij} \}, 1 \leq i < j \leq n$ be a set of random variables where each $X_{ij}$ is i.i.d. in $\sim [0,1]$. Clearly, $|E| = \binom{n}{2}$. These are the weights of a complete weighted graph, where $X_{ij}$ is indeed the weight between node $i$ and node $j$.
Now, I repeat the following procedure recursively (say for $n/2$ times):
- Pick a vertex $z \in \{1,n\}$ that verifies the following:
there exists two other vertices, $p, q \in [1,n], p,q \neq z$ s.t.
\begin{align} X_{zp} = \arg\min\{ X_{uv} : u=p \text{ or } v=p \} \text{ and } X_{zq} = \arg\max\{ X_{uv} : u=q \text{ or } v=q \} \end{align} There exists two other vertices $p$ and $q$ s.t. the incident edge between $z$ and $p$ is the minimum value among all incident edges of $p$ and the incident edge between $z$ and $q$ is the maximum value among all incident edges of $q$, or viceversa.
Here a representation
If that's the case, denote $R = \{ X_{uv} \text{ s.t. } z=u \text{ or } z=v \}$.
- Set $E = E \setminus R$, $n = n-1$.
At every step, I choose a vertex $z$ which verifies the property described above. Then I remove it with all its edges, leaving me with a smaller complete graph.
Would $E$ still be uniformly distributed if pick subsets from it, according to the above rule, and remove them?
