I am working on understanding a proof for a randomized algorithm from http://cs.brown.edu/~claire/Publis/sigactnews08.pdf I am looking at page 5, Lemma 5 which states:
Lemma 5. Let $x_t$ denote the probability over $\sigma$ that the vertex of $V$ of rank $t$ is matched by the algorithm. Then $1-x_t\leq (1/n)\sum_{1\leq s\leq t}x_s$
Then a few lines later:
We rewrite Lemma 5 as $S_t(1+1/n)\geq 1+ S_{t-1}$ where $S_t=\sum_{1\leq s \leq t}x_s$
I am attempting to reconstruct some intermediary steps in order to understand this rewrite. Here's what I have so far:
$1/n \sum_{1\leq s\leq t}x_s \geq 1-x_t$
$1/n \sum_{1\leq s\leq t}x_s + \sum_{1\leq s\leq t}x_s \geq 1-x_t +\sum_{1\leq s\leq t}x_s$
$S_t(1+1/n) \geq 1-x_t +\sum_{1\leq s\leq t}x_s$
So I have taken care of the left hand side of the equation, but the right hand side remains. There are a few facts that I know are true, which I am trying to piece together in order to complete the transformation.
$1-t_{t-1}\leq 1-x_t$
$\sum_s^n x_s = 1$
I am aiming to show $1+S_{t-1}\geq 1-x_t +\sum_{1\leq s\leq t}x_s$