consider following persudocode:

while(i< k):
    uniformly pick u,v in V
    if(uv in E):
        remove uv form E;

let $T$ be the number of iteration of this process, I know how to compute the expectation, but what is well bound for $P(|T -E[T]|)$? And is this process independent?

  • $\begingroup$ The geometric random variables do seem independent. Have you tried using a Chernoff bound? $\endgroup$ – Yuval Filmus May 6 at 21:04

No. It is not true. If the uniformly picked edge $u$ have more neighbors, the probability of edges which have $u$ is more than others! Hence, it's not uniform. Moreover, the number of neighbors of each node is changing over time, and this can be more unbiased over the time. Therefore, your selections are not independent of each other.

A solution to uniformly removing an edge can be indexing all edges from $1$ to $|E|$ (using an adjacency list for example) and then pick a random number from $1$ to $|E|$ as your uniformly picking edge in your graph. And do it for the new graph after removing the randomly picked edge.

Hint: As uniform version will remove an edge each time, the probability in this version can be an upper-bound for the $\mathbb{P}(|E[T]-T|)$ in your solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.