I have a homework problem that goes as follows:
Let $\xi_i, \ i=0,1,2,\ldots$ be i.i.d. random variables of discrete type. The distribution of $\xi_0$ is given by: $$\mathbb{P}\{\xi_0=i\} = a_i, \ \ \ \ i=0,1,2,\ldots$$ where $\sum_{i=0}^\infty a_i = 1$ Define a Markov chain $X_n, \ n=0,1,2, \ldots$ by $X_n = \text{max}\{\xi_0,\ldots,\xi_n\}$.
Write down the one step transition matrix of $X_n$.
I am not 100% certain that I fully understand what the question is asking. I don't really see how this is a markov process, but regardless, this is my attempt at an answer (note: math exchange doesn't seem to recognize boardermatrix, so pardon the matrix):
$ \textbf{P} = \matrix{~ & 0 & 1 & 2 &3 & 4 & \cdots \cr 0 & 1 & 0 & \cdots & \cdots & \cdots \cr 1 & \frac{1}{2} & \frac{1}{2} & 0 & \cdots & \cdots \cr 2 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & \cdots \cr 3 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 \cr \vdots } $
Here's a hint.
Assume that at some stage $n$, you know that that the maximal value you have observed is $k$.
At the next step $n+1$, what can happen?
Either next $\xi_{n+1}$ is smaller than your observed maximum, in which case your chain remains at the same place. (Can you find the probability of $\xi_{n+1} \leq k$?).
Or $\xi_{n+1}$ can be higher than your observed maximum. That is, it can be one of $\{k+1, k+2, k+3,...\}$ and then your chain updates to $\xi_{n+1}$ because then this new value is the observed maximum. (With what probabilities will it reach any one of those states?)