0

I'm trying to solve the following counting problem. Let $X_1,X_2,\ldots$ be random process and define:

  • $L_1=1$,
  • $L_k=\min\{n> L_{k-1}:X_n\geq X_1,\ldots,X_{n-1} \}$.

How many permutations of $m$ elements are such that $L_k=m$ for $m\geq k$? For example, one permutation that satisfies $L_4=8$ is

$$X_4\leq X_1\leq X_3\leq X_7\leq X_2\leq X_6\leq X_5\leq X_8.$$ Also note that, $L_2=2$, $L_3=5$ and $L_1<L_2<L_3<L_4$. I have been stuck with this problem for a while.

N. F. Taussig
  • 76,571
Asupollo
  • 185
  • 1
  • 9
  • You count the permutations, not the number of permutations. – joriki Feb 10 '20 at 03:54
  • Why do you introduce a random process and then never mention it again? The title and the rest of the question seem to agree that you want to count deterministic objects. – joriki Feb 10 '20 at 03:55
  • @joriki Because I want the variables to take values in order, $X_1$, then $X_2$ and so on. This is part of another problem in probability. – Asupollo Feb 10 '20 at 04:04
  • But the permutations in $S_m$ also have the values in every order. You don't need randomness for that, as is underlined by the fact that the rest of the question actually never talks about randomness again. You don't ask for a probability, you ask for a count, for "how many". To make sense of the random process, you'd have to give it a distribution – that would presumably be a uniform distribution – but then why bother? – joriki Feb 10 '20 at 04:14
  • @joriki In fact the distribution doesn't matter because the X's are identical and independent. The permutations in $S_m$ have the values in order, but I'm comparing the values of the X's not the indices. Lets just think of $n$ numbers $X_1,\ldots, X_n$ with unknown values. I hope at least it's clear what I'm asking for. And if it's necessary I will rewrite the question. – Asupollo Feb 10 '20 at 05:01
  • See https://math.stackexchange.com/questions/2793065/distribution-of-random-variable-time-to-n-th-maximum/2793190#2793190 – Mike Earnest Feb 10 '20 at 17:25

1 Answers1

0

The exact distribution of the $X_i$ does not matter. All that matters is the relative ordering of the $X_i's$. Therefore, let us consider permutations of $\{1,2,\dots,m\}$, obtained by replacing the smallest value of $X_i$ with $1$, the second smallest value with $2$, and so on.

To simplify the terminology, given a permutation of $\{1,2,\dots,m\}$, let us call the index $i$ a record if the $i^{th}$ entry is larger than everything before it. By convention, $1$ is always a record.

If $L_k=m$, this means the $k^{th}$ record occurs at spot $m$, so that the first $m-1$ entries contain exactly $k-1$ records. So, we need to count permutations of a given length which have a given number of records. To this end, let $R(n,\ell)$ be the number of permtuations of $\{1,2,\dots,n\}$ with exactly $\ell$ records. This means that the solution to your problem is $R(m-1,k-1)/m!$.

Unfortunately, there is no "closed-form" expression for $R(n,\ell)$. It obeys the following recursive formula: $$ \begin{array}{l} R(n,\ell)=R(n-1,\ell-1)+(n-1)R(n-1,\ell), \\R(1,1)=1\\R(1,\ell)=0\qquad \text{when }\ell\neq 1 \end{array} $$ To see this, consider the location of $1$ in the permutation.

  • If $1$ is in the first spot, then $1$ is a record, and among the entries $\{2,3,\dots,m\}$, there are exactly $\ell-1$ records. This can be chosen in $R(n-1,\ell-1)$ ways.

  • If $1$ is not in the first spot, then the index of $1$ is not a record. Deleting $1$ leaves a permutation of $n-1$ symbols which still has $\ell$ records, which can be chosen in $R(n-1,\ell)$ ways. The factor of $(n-1)$ accounts for all the ways $1$ can be inserted into such a permutation of $n-1$ symbols to recover a permutation of $n$ symbols.

It turns out that this is exactly the recursion which the unsigned Stirling number of the first kind satisfy, and that the two have the same base cases. This implies that, letting $c(n,\ell)$ be the number of permutations of $\{1,2,\dots,n\}$ with exactly $\ell$ cycles, then $R(n,\ell)=c(n,\ell)$. Therefore, you can express your probability in terms of these well-known numbers:

$$ P(L_k=m)=\frac{c(m-1,k-1)}{m!} $$

Mike Earnest
  • 75,930