2
$\begingroup$

I'm reading a book on Randomized Algorithms by Raghawan and Motwani and I don't understand the algebra/calculus of a step in the analysis of Karger's algorithm(Randomized min-cut).

They have the following: $$Pr[\cap_{i=1}^{n-2} E_{i}] \geq \Pi_{i=1}^{n-2}(1-\frac{2}{n-i+1}) = \frac{2}{n(n-1)}$$

This part in particular: $\Pi_{i=1}^{n-2}(1-\frac{2}{n-i+1}) = \frac{2}{n(n-1)}$ is hard for me to see when i try to write it out. I know that for example

$$ 1 + 2 + 3 + 4 + \ldots + n = \frac{n(n+1)}{2}$$ which can be figured out by adding two series together. But I actually don't know a lot about long products like $\Pi_{i=1}^{n-2}(1-\frac{2}{n-i+1})$ is there any good place to start if I had to find $\frac{2}{n(n-1)}$ ?

$\endgroup$

1 Answer 1

3
$\begingroup$

$$ \begin{align*} \prod_{i=1}^{n-2} \left( 1-\frac{2}{n-i+1} \right) &= \prod_{i=1}^{n-2} \frac{n-i-1}{n-i+1} \\ &= \frac{\color{red}{n-2}}{n} \cdot \frac{\color{blue}{n-3}}{n-1} \cdot\frac{n-4}{\color{red}{n-2}} \cdot \frac{n-5}{\color{blue}{n-3}} \cdots \frac{\color{purple}{4}}{6} \cdot \frac{\color{green}{3}}{5} \cdot \frac{2}{\color{purple}{4}} \cdot \frac{1}{\color{green}{3}}\\ & = \frac{2}{n(n-1)}. \end{align*} $$

Where we used the fact that the product is telescopic. Notice how, after simplifying, the only surviving terms from the numerators are $2$ and $1$ while the only surviving terms from the denominators are $n$ and $n-1$.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. So the denominator $n(n-1)$ comes from the first two terms where $n$ and $n-1$ does not get cancelled, and then the $2$ and $1$ for the enumerator survives from the last 2 terms and everything else gets cancelled out? $\endgroup$ Oct 4, 2021 at 22:26
  • 1
    $\begingroup$ Exactly.$\phantom{}$ $\endgroup$
    – Steven
    Oct 4, 2021 at 22:29

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.