Using indicator random variables on random number generation Suppose a computer is generating a number at random from 1 to n, and can not generate the same number twice.
A) You try to guess the number, without knowing that it can not generate the same number twice (So you are just guessing a number from 1 to n). What is the expected number of predictions that you get correct? Prove your answer is correct using indicator random variables.
Answer: $E[X]= E\Big[\sum_{i=1}^n X_i\Big] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n 1/n = 1$
B) You try to guess the number, this time having a record of all numbers generated previously (So you are not guessing a number already generated). What is the expected number of predictions that you get correct? Prove your answer is correct using indicator random variables.
This is the question I am struggling on, I don't know if I am not setting something up right, or missing some obvious mathematical answer. I have:
$E[X]= E\Big[\sum_{i=1}^n X_i\Big] = \sum_{i=1}^n E[X_i] = \sum_{i=1}^n 1/(n-i) = $
and I have no idea where to go next. My best guess would be using something like so:
$= \sum_{i=1}^n 1/n - \sum_{i=1}^n 1/i = 1 - \sum_{i=1}^n 1/i = 1 - H_n$
Which can't be right because it is less then A, when you should have a better chance in B.
 A: For the question in A) you need to take in account that the numbers doesn't repeat, then the probability to correctly guess the $j$-th time is given by $\Pr [X_j=P_j]$
where $P_j$ is your $j$-th guessing and $X_j$ is the r.v. of possible values at time $j$. Then, as you dont know that the numbers doesn't repeat, $P_j$ is distributed uniformly in $\{1,\ldots ,n\}$ but $X_j$ is distributed uniformly in some random subset $S_j\subset \{1,\ldots ,n\}$ with $|S_j|=n-(j-1)$, thus
$$
\Pr [X_j=P_j]=\Pr [X_j=P_j|P_j\in S_j]\Pr [P_j\in S_j]+\Pr [X_j=P_j|P_j\notin S_j]\Pr [P_j\notin S_j]\\
=\frac1{n-(j-1)}\cdot \frac{n-(j-1)}{n}+0\cdot \frac{j-1}{n}=\frac1{n}
$$
And the expected number of correct predictions is given by
$$
\operatorname{E}\left[\sum_{j=1}^n\mathbf{1}_{X_j=P_j}\right]=\sum_{j=1}^n \operatorname{E}[\mathbf{1}_{X_j=P_j}]=\sum_{j=1}^n \Pr [X_j=P_j]=1
$$
Now for part B) this time $P_j$ is uniformly distributed in $S_j$ for each $j$, so $\Pr [X_j=P_j]=\frac1{n-(j-1)}$, therefore as you guessed correctly you have that
$$
\operatorname{E}\left[\sum_{j=1}^n \mathbf{1}_{X_j=P_j}\right]=\sum_{j=1}^n \operatorname{E}[\mathbf{1}_{X_j=P_j}]=\sum_{j=1}^n\frac1{n-(j-1)}=\sum_{j=1}^n\frac1{j}=H_n
$$
There $H_n$ stay for the $n$-th harmonic number (it is not less than the result in A) as you supposed, note that for $j=1$ you have that $\tfrac1j=1$).
