# Length of longest subsequence as a martingale

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.

• $Y_n$ is nondecreasing in $n$, is it not? So it certainly can't be a martingale on its own. – Nate Eldredge Nov 3 '19 at 13:45

## 1 Answer

An extended comment: in general, there will not exist any sequence of constants $$c_n$$ such that $$Z_n = Y_n - c_n$$ is a martingale.

Suppose the $$X_i$$ are iid. Let $$A_{n+1}$$ be the event that $$X_1, \dots, X_{n+1}$$ has a strictly longer increasing subsequence than $$X_1, \dots, X_n$$ did. Then $$Y_{n+1} - Y_n = 1$$ on $$A_{n+1}$$, and $$0$$ on $$A_{n+1}^c$$, which is to say $$Y_{n+1} - Y_n = 1_{A_{n+1}}$$. Now if $$Z_n$$ is a martingale then we have $$P(A_{n+1} \mid X_1, \dots, X_n) = E[Y_{n+1} - Y_n \mid X_1, \dots, X_n] = c_{n+1} - c_n.$$ Since the conditional probability is deterministic, we conclude $$A_{n+1}$$ is independent of $$\sigma(X_1, \dots, X_n)$$. But this is absurd - the probability of getting a strictly longer increasing subsequence is clearly influenced by the values you already had. For instance, if it happens that $$X_1, \dots, X_n$$ are all very low values, then it is very likely that $$X_{n+1}$$ will be greater than all of them, which will certainly add to the length of the longest increasing subsequence.