Consider a sequence of continuous random variables $(X_n)_{n \geq 1}$. Let $Y_n$ denote the longest increasing subsequence in the tuple $(X_1,\dots,X_n)$. Does $Y_n$ form a martingale? If not, can I form a martingale using $Y_n$?
It is clear that $Y_n$ has finite expectation, but I do not know how is the expectation like precisely. I'm skeptical that $\mathrm{E}[Y_{n+1} - Y_n \mid X_1,\dots,X_n] = 0$. Note that since $X_n$ are all continuous, two of them are equal with probability $0$ so we can treat them to be pairwise distinct.
It is clear here that if $Y_n = k$, then $Y_{n+1} \in \{k,k+1\}$, and $Y_{n+1} = k+1$ iff the longest subsequence in $(X_1,\dots,X_n)$ lies on its tail. Surely that occurs with non-zero probability, and since $Y_n \not< k$, I doubt that $Y_n$ itself forms a martingale. I therefore suspect that $Y_n - c$ forms a martingale for some constant $c$, or possibly some slight variations, such as $Y_n - cn$.
Thanks in advance.
EDIT: As pointed out by @Nate, since $Y_n$ is non-decreasing and is not a constant, it itself can't be a martingale. My ultimate goal is to prove the following inequality: $$ \mathrm{P}[Y_n - \mathrm{E}[Y_n] \geq t]\leq e^{-\frac{2t^2}{n}} $$ If $Y_n$ is a martingale, then it is a very simple application of the Azuma-Hoeffding Inequality. However, this is clearly not the case, and the main problem I'm facing lies in the construction of the martingale.