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.
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!} $$