0
$\begingroup$

In our textbook "Algorithm Design" we are given an example of a deck of $n$ cards and we have to guess the correct card, and every time a card is drawn, we remember that cards so we are uniformally guessing only among the cards not yet seen. I don't understand the final part of the following summation, where the authors reduce the summation to a harmonic number... note: the random variable $X_i$ takes on 1 if the ith value is correct or 0 otherwise: $$\Pr[X] = \sum\limits_{i=1}^n E[X_i] = \sum\limits_{i=1} ^n \frac {1}{n-i+1} = \sum\limits_{i =1}^n \frac {1}{i}$$ I don't see how they derived $\sum\limits_{i =1}^n \frac {1}{i}$, which I know becomes a harmonic number [Ideally someone might show this without calculus]... Thanks

$\endgroup$
1
  • $\begingroup$ I think what you have written is incorrect... It should be $\sum_{i=1}^{n-2}i$, no? $\endgroup$
    – K.defaoite
    May 31 '20 at 13:58
1
$\begingroup$

They reindexed the sum. As $i$ runs from $1$ to $n$, $j=n-i+1$ runs from $n$ to $1$, so

$$ \sum_{i=1}^n\frac1{n-i+1}=\sum_{j=1}^n\frac1j=\sum_{i=1}^n\frac1i\;. $$

$\endgroup$

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.