I have been given an assignment for my Randomized Algorithms class. We begin with a graph and start removing vertices step by step. On each step we randomly select 1 vertix and remove that vertix plus some other vertices which are a function of the removed vertix. The goal is to calculate the expected number of steps before the graph is empty.
I have a neat way of doing this (which I know gives the correct result since we have been told what the expection is and we actually just need to prove it). However it is somewhat "cheating". Because to calculate the expectation I change the strategy in which we remove vertices. Instead of picking at random one of the remaining vertices at each step, I pick at random a permutation $π$ of all the vertices at the very beginning. At step $i$ I remove $π(j)$ where $j = min\{k \ge i : π(k) \in G\}$. Intuitively this should equivalent to the first strategy but I need a way to prove that.
So my question is: Are they actually equivalent or not? And if they are can you give any tips as to how I should go about proving that? One idea I have is using induction and showing that by adding one vertix, the probability that it will be picked during the $i$-th step is the same in both strategies.
I would do it in several steps, which simplifies the argument:
Show that the random-selection procedure is equivalent to the following: at each step, randomly select any vertex that hasn't been selected before (even if it's been deleted). If it has been deleted, do nothing; otherwise, delete it, and all the vertices that must be deleted as a consequence.
Show that the procedure in step 1 is equivalent to the following: randomly select a permutation $\pi$. On the $i^{\text{th}}$ step, if $\pi(i)$ has already been deleted, do nothing. Otherwise, delete $\pi(i)$, and all the vertices that must be deleted as a consequence.
Show that the procedure in step 2 is equivalent to your random-permutation procedure.
Here, we add fictional do-nothing steps that don't change anything (and steps 1 and 3 are to check that they don't change anything). What this accomplishes is that every run through the procedure in step 1 actually selects every vertex once by the end, which is equivalent to choosing a random permutation.
And that's the motivation for doing this: choosing a random permutation is morally equivalent to a procedure that looks at random vertices until it looks at every vertex once. The original deletion procedure doesn't quite have that form, but it can be modified to have that form.
(But your induction idea should also work, it's just a bit more complicated.)