# Verify that the successive maxima process is a Markov process

Let $Y_1,Y_2,...,$ random variables i.i.d. with $P(Y_n=k)=a_k; k=0,1,2,...$. Prove the Markov property for the succesive maxima process: $\{X_n\}_{n\geq 0}$, $X_0=0, X_n=max\{Y_1,Y_2,...,Y_n\}$.

${\bf Idea}$

\begin{eqnarray} P(X_{n+1}=x_{n+1}|X_0=x_0,...,X_n=x_n)&=&P(max\{Y_1,Y_2,...,Y_{n+1}\}=x_{n+1}|X_0=0,max\{0,Y_1\}=x_1,...,max\{Y_1,Y_2,...,Y_n\}=x_n)\\ &=&P(max\{x_n,Y_{n+1}\}=x_{n+1}|X_0=0,max\{0,Y_1\}=x_1,...,max\{x_{n-1},Y_n\}=x_n) \end{eqnarray} There is a result for independence of functions ofindependent random variables? I guess that te next step is correct but i'm not sure. \begin{eqnarray} P(X_{n+1}|X_0=x_0,...,X_n=x_n)&=&P(max\{x_n,Y_{n+1}\}=x_{n+1}|max\{x_{n-1},Y_n\}=x_n)\\ &=&P(X_{n+1}=x_{n+1}|X_n=x_n)\square \end{eqnarray} It's correct?

• It's correct, $P(Y_n=k)=a_k$ – User 2014 Oct 18 '16 at 4:47
• Indeed, $$P(X_{n+1}=x_{n+1}\mid X_0=x_0,\ldots,X_n=x_n)=P(\max\{x_n,Y_1\}=x_{n+1})$$ hence $(X_n)$ is Markov with transitions $$P(X_{n+1}=x_n\mid X_0=x_0,\ldots,X_n=x_n)=\sum_{k=0}^{x_n}a_k$$ and, for every $x>x_n$, $$P(X_{n+1}=x\mid X_0=x_0,\ldots,X_n=x_n)=a_x$$ – Did Oct 26 '16 at 23:28

As you indicated, $P(X_{n+1}=x_{n+1}|X_0,\ldots,X_n)=P(max(X_n,Y_{n+1})=x_{n+1}|X_0,\ldots,X_n)$ and since $Y_{n+1}$ is independent of $X_0,\ldots,X_n$, $$P(max(X_n,Y_{n+1})=x_{n+1}\mid X_0,\ldots,X_n)=P(max(x,Y_{n+1})=x_{n+1})\Big|_{x=X_n}\\ =P(Y_{n+1}=x)P(Y_{n+1}\ge x)+P(x=x_{n+1})P(Y_{n+1}<x)\Big|_{x=X_n}\\ =a_k (1-F(X_n))+P(X_n=x_{n+1})F(X_n-1),$$ where $F(y)=\sum_{i=0}^ya_i$ is the cdf of $Y_1$. Since this expression is just a function of $X_n$, $P(X_{n+1}=x_{n+1}\mid X_0,\ldots,X_n)=a_k (1-F(X_n))+P(X_n=x_{n+1})F(X_n-1)=P(X_{n+1}=x_{n+1}\mid X_n).$
• Until the identity $$P(\max(X_n,Y_{n+1})=x_{n+1}\mid X_0,\ldots,X_n)=P(\max(x,Y_{n+1})=x_{n+1})\Big|_{x=X_n}$$ and this identity included, your answer makes sense, but, starting at the very next line, it seems nothing is making sense anymore (to the point that I am unable to explain where the confusion is coming from). – Did Oct 26 '16 at 23:23