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.

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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.