I have a solution, but I want to understand it - why is this a Markov chain? In the era of the modern internet, many students, myself and my cohort all included, are exposed to answers to homework nearly as quickly as we are assigned it. Obviously this can be very detrimental.
Through a peer I do homework with I was presented this solution which neither of us understands.
The question is thus:
If $\zeta_1 , \zeta_2 , ...$ are independent identically distributed values in ${1,2,...,N}$ with uniform probability each taking probability $1/N$, consider the range of distinct values taken up to time $n: X_n := |{\zeta_1, ..., \zeta_n}|$. Show that ${X_n}$ is a Markov chain.
The solution is that
$P(X_n+1 = j | X_n = i, ..., X_0 = i_0) = 1 - i/N$ for $j = i+1$ and $i/N$ for $j=i$ and that this equals $p(i,j)$.
Why is this the case at all? It seems to understand it I would need to first understand conditional probability for a uniformly distributed sequence of values. But I didn't really know how to begin the problem, and the solution provides no insight.
Any such insight would be helpful.
 A: The conditional probabilities are easier than they look.  Suppose $X_n=i$, so you've seen $i$ distinct values by time $n$.  The number of distinct values you've seen by time $n+1$, ie, $X_{n+1}$, is either the same (if the new number is a number you've already seen, or greater by 1 (if the new number is one you hadn't previously seen).  So, $p(i,i)$ and $p(i+1,i)$ are non-zero and all the other transition probabilities are zero.
To show the process is a Markov chain, you need to show that $p(i,i)$ and $p(i+1,i)$ depend only on $X_n$, not on any earlier values of the process.  You don't have to work them out, but working them out is one way to do it.
$p(i,i)$ is the probability that the $n+1$th observation is the same as one of the $i$ values you've already seen. There are $N$ possible values, all equally likely, so the probability you pick one of the $i$ you've already seen is $i/N$. $p(i+1,i)$ has to be $1-p(i,i)$ because $i$ and $i+1$ are the only two possible values, so $p(i+1,i)=1-i/N$.
So, if you know $X_n$ these two probabilities are functions of $i$ (that is, $X_n$) and of $N$, which is a constant. They don't depend on $X_m$ for any earlier $m<n$, and so $X_n$ is a Markov Chain.
If the $N$ observations weren't equally likely this argument would break down: the chance of seeing one you had seen before would depend on which values you had seen before, so you'd suspect that it might depend on $X_m$ for   $m<n$ (and I think you'd be correct to suspect).
