What is my mistake in this probability problem? I am taking a class on discrete probability and one question is as follows:
Suppose someone roles an n-sided die once. Now you repeatedly roll the die until you roll a number at least as large as the person rolled. What is the expected number of rolls you will have to make?
My answer was as follows
$$\begin{align}& \mathrm{Let\ }d_1\ \mathrm{be\ the\ other\ persons\ roll}\\
&\mathrm{Let\ }d_2\ \mathrm{be\ my\ roll}\\&P(d_1=k)=\frac{1}{n}\\
&P(d_2\geq d_1)=P(d_2\geq d|d_1=1)P(d_1=1)+...+P(d_2\geq d|d_1=n)P(d_1=n)\\
&P(d_2\geq d_1)=\frac{1}{n}\left(P(d_2\geq d|d_1=1)+...+P(d_2\geq d_1|d_1=n)\right)\\
&P(d_2\geq d_1)=\frac{1}{n}\left(\frac{n}{n}+...+\frac{1}{n}\right)=\frac{1}{n^2}\left(\sum_{k=1}^nk\right)=\frac{n(n+1)}{2n^2}=\frac{n+1}{2n}\\
&X=\mathrm{number\ of\ rolls}\\
&E[X]=\sum_{k=1}^\infty k\left(1-\frac{n+1}{2n}\right)^k\left(\frac{n+1}{2n}\right)
\end{align}$$
However, the solutions say that the answer is $H_n$
What am I doing wrong?
 A: You have $\mathsf P(d_1=d)~=~\tfrac 1n$, for $d\in\Bbb Z\cap[1..n]$
Then you should go: $\mathsf P(d_2\geq d_1\mid d_1=d) ~=~ \dfrac{n+1-d}{n}$, for $d\in\Bbb Z\cap[1..n]$ 
So then let $X$, when conditioned on $d_1$, be the count of independent Bernoulli trials until a success with this rate.   The distribution of $X$ conditioned on $d_1$, is thus recognisably geometric, and so $$\mathsf E(X\mid d_1) = \dfrac{n}{n+1-d_1}$$ 
From here it will be an application of the Law of Total Expectation:

 $$\begin{align}\mathsf E(X) ~&=~ \mathsf E(\mathsf E(X\mid d_1)) \\[1ex] &=~ \mathsf E(\tfrac{n}{n+1-d_1})\\[1ex] & =~ \sum_{d=1}^n\tfrac 1{n+1-d} \\[1ex] &=~ \sum_{k=1}^n\tfrac 1k \\[1ex] &=~ H_n\end{align}$$

A: Denote by $E_r$ the expected number of rolls for the second player when the first player has rolled $r\in[n]$. Then
$$E_r=1+{r-1\over n}E_r\ ,$$
hence
$$E_r={n\over n+1-r}\ .$$
Given that $r$ is  uniformly distributed in $[n]$ the a priori expectation $E$ of the number of rolls for the second player comes to
$$E={1\over n}\sum_{r=1}^n E_r=\sum_{r=1}^n{1\over n+1-r}=H_n\ .$$
A: Your $P(d_2 \ge d)$ is correct (though it should be $d_1$, not $d$).  Your error is then assuming you could use that to get the expected time to exceed $d_1$.  The expected time depends on $d_1$.  A simple example:  assume the first player rolls $1$ with probability $2/3$ and $3$ with probability $1/3$.  Assume the second player always rolls $2$.  Then $P(d_2 \ge d_1)=2/3$ but the expected number of rolls for player $2$ to exceed player $1$s roll is infinite, not $3/2$, because player $2$ can never beat a $3$.
