# Expected number of ordered sub-sequences in a sequence

Let $S$ be a sequence of integers, of length $n$. Compute the expected value of ordered sub-sequences contained with-in it.

Am I correct in assuming, that there is a need for a set $N$, from which the elements of $S$ are picked, in order to be able do draw conclusions about the expected value? Can we make the set $\mathbb{N}$? How does the problem change if we expand our set to $\mathbb{Q}$?

How may I go about constructing a distribution, that allows such computations?

My attempt, falls short.

Let $E_l$ be the event of picking an ordered sequence of length $l$. Let $c_l$ be the last integer chosen.

$\mathrm{p(E_{l+1} | E_l)} = \mathrm{p(E_l)}\mathrm{p(\mathbb{1}_{n>c})}$

$\mathrm{p(\mathbb{1}_{n>c})} = 1- \frac{c_l}{|N|}$

$\mathrm{p(E_{l+1} | E_l)} = \mathrm{p(E_l)} - \frac{c_l\mathrm{p(E_l)}}{|N|}$

As the $c_l$ is unknown, I am unable to solve the recurrence. Should I treat it like a random variable as well (similar to how the variance is taken as a random variable in $T$ distribution)?

Example:

Let $N\subset\mathbb{N}$, and the sequence chosen at random (with repetition) is

$S=\{3,2,4,2,4,3,4,5\}$

S contains two ordered sub-sequences, namely

$sS_1=\{2,4\}$ , $sS_2=\{2,4\}$, $sS_3=\{3,4,5\}$

The number of ordered sub-sequences is three.

Please forgive any non-formalities, I am an amateur exploring his interest.

• You might clarify what you mean by an "ordered subsequence." What exactly are you counting? For example, for $n=8$, consider the sequence $\{3, 2, 4, 2, 4, 3, 4, 5\}$. How may "ordered subsequences" are there? Of course, you would also need to specify a probability model for how the original sequence is chosen. – Michael Mar 26 '16 at 12:50
• Also, I do not know what you mean by "Let $E_l$ be the event of picking an ordered sequence of length $l$." In what sense are we picking an ordered sequence? Do we only care about its length, but not its contents? How does this relate to the original length-$n$ sequence? – Michael Mar 26 '16 at 12:52
• If we choose increasing order, there are 2, {2,4} and {3,4,5}. We only care about the length of the sequence. In your case, the lengths are 2 and 3. Thus, the sequence contains 2 ordered sub-sequences. This number, is what I want to compute, how many of such sub-sequences might I expect, at random. I will add your example to the question. – LeastSquaresWonderer Mar 26 '16 at 13:31
• Sorry, it contains 3, as {2,4} is repeated. – LeastSquaresWonderer Mar 26 '16 at 13:37

Here are two approaches to solve (the second one changes the question but gives more intuition):

## Problem:

Let $\{X_1, X_2, X_3, ...\}$ be an infinite sequence of independent and identically distributed (i.i.d.) random variables with cumulative distribution function (CDF) $F_X(x) = P[X_i\leq x]$ for all $x \in \mathbb{R}$. We want to count runs of increasing subsequences, not counting subsequences of size 1 (and not counting overlaps).

### Approach 1 (dynamic programming):

Define $m[k]$ as the expected number of increasing subsequenes (of size at least 2) within a random string of length $k$. How do we find $m[k]$?

For each integer $l>0$, define: \begin{align} \theta[l] &= P[\{X_1 < X_2 < ... < X_l\} \cap\{X_l \geq X_{l+1}\}]\\ z[l] &= P[\{X_1 < X_2 < ... < X_l\}] \end{align} Assuming the $\theta[l]$ and $z[l]$ values are known, we get a recursion for $m[k]$:

\begin{align} m[0]&=0\\ m[1]&=0\\ m[k]&= \theta[1]m[k-1] + \left[\sum_{l=2}^{k-1}\theta[l](1+m[k-l])\right] + z[k]\quad \forall k \geq 2 \end{align} Explanation: The first term of the above equation considers the situation when the first increasing subsequence has length 1. In that case, we do not count it, and the total number of increasing subsequences in the sequence is the same as the total number in the remaining $k-1$ numbers. The second term considers the cases when the first increasing subsequence is size $l \in \{2, ..., k-1\}$. In that case we count it, and the total number is 1 plus the number in the remaining $k-l$ numbers of the sequence. The last term considers the situation when the entire $k$-length sequence is increasing (so we count it as "1").

With this approach, the $m[k]$ values can be computed recursively in terms of $m[i]$ values for $i \in\{0, ..., k-1\}$. This assumes we know $\theta[l]$ and $z[l]$ for all relevant $l$. These can be computed in terms of the particular CDF function $F_X(x)$ that you have. The simplest case is when $F_X(x)$ is continuous for all $x \in \mathbb{R}$, since all continuous CDF functions give rise to the same $\theta[l]$ and $z[l]$ values. Indeed, a continuous CDF ensures the probability of two numbers being exactly the same is 0. Hence, (with prob 1) all numbers are distinct. Since all permutations are equally likely, we get $z[l]=1/l!$ in that case. (Similarly, you can compute $\theta[l]$ by counting the number of orderings associated with its event.)

Here are particular values computed from the above recursion (for the continuous CDF case): \begin{align} m[30] &=8.608011\\ m[40] &= 11.517894\\ m[50] &= 14.427778 \\ m[100] &=28.977195\\ m[500] &= 145.372537 \end{align}

### Approach 2 (renewal theory):

Let's change the question to the following:

1) What is $\lim_{k\rightarrow\infty} \frac{m[k]}{k}$?

2) Consider a "frame" as a run length of increasing numbers (including frames of size 1). What is the average frame length?

By renewal theory we can say: $$\lim_{k\rightarrow\infty} \frac{m[k]}{k} = \frac{P[\mbox{frame length \geq 2}]}{E[\mbox{frame length}]} = \frac{1-\theta[1]}{E[\mbox{frame length}]}$$

If the CDF $F_X(x)$ is continuous then $\theta[1]=1/2$ (since the events $\{X_1<X_2\}$ an $\{X_1>X_2\}$ are equally likely). If we define $L$ as the random run length then $L=\sum_{i=1}^{\infty}X_i$ where $X_i$ is an indicator function that is 1 if $\{X_1<X_2 < ...< X_i\}$, and 0 else. So: $$E[\mbox{frame length}]=E[L]=\sum_{i=1}^{\infty} E[X_i] = \sum_{i=1}^{\infty} \frac{1}{i!} = e-1$$ Thus, with a continuous CDF we get: $$\lim_{k\rightarrow\infty} \frac{m[k]}{k} = \frac{1/2}{e-1} = \frac{1}{2(e-1)} \approx 0.290988353$$

• Thank you for a detailed answer. If I may pose a question. I do not understand "since all continuous CDF functions give rise to the same θ[l]θ[l] and z[l]z[l] values". How do all continuous CDFs give rise to the same values? – LeastSquaresWonderer Mar 27 '16 at 20:53
• How might I go about counting the number of orderings associated with θ[l]s event in general? Again, why do all CDFs give rise tot he same value? Also, I really liked the second calculation. (despite this two comments, I accepted the answer, as the fault for sub-questions lies with me, and not the answer) – LeastSquaresWonderer Mar 27 '16 at 21:02
• We have $P[X_1<X_2]=P[X_2<X_1]=1/2$ (since $P[X_1=X_2]=0$). If we write the $X_i$ in increasing order, there are only two permutations possible: $(X_1, X_2)$ or $(X_2, X_1)$, both equally likely. So $z[2] = \frac{1}{2}$. In general, since no permutation is more likely than any other, we get $$z[l] = \frac{\mbox{Number of length-l permutations that increase}}{\mbox{Number of length-l permutations}} = \frac{1}{l!}$$ For example, for $l=3$ we have $3!=6$ equally-likely permutations $\{(X_1,X_2,X_3), (X_1, X_3, X_2), (X_2, X_1, X_3), (X_2, X_3, X_1), (X_3, X_1, X_2), (X_3, X_2, X_1)\}$. – Michael Mar 28 '16 at 3:21
• Now you can compute $\theta[2]$ by: $$\theta[2]=\frac{\mbox{Number of length-3 permutations with X_1<X_2, X_3\leq X_2}}{\mbox{Number of length-3 permutations}}$$ In general, $$\theta[l] = \frac{\mbox{Number of length-(l+1) permutations with X_1<X_2<...<X_l, X_{l+1}\leq X_l}}{\mbox{Number of length-(l+1) permutations}}$$ And of course you can double-check that $\sum_{l=1}^{\infty} \theta[l]=1$. – Michael Mar 28 '16 at 3:32
• In the discrete case we have $P[\mbox{First$l$numbers are distinct}]=d_l<1$, and the probability of getting $l$ numbers that are all distinct and in an increasing order is $z[l]=d_l/l! < 1/l!$. You can see why the continuous case is easier, since $d_l=1$ in that case, for all $l$. – Michael Mar 28 '16 at 3:52