Probability of alternating sequence from uniform distribution

Question

Say I sample a discrete uniform distribution $U$ (say $U$ has a support of $N$ elements, and there is a total order on the elements) a number $K$ times, resulting in a random sequence $A_{i}$. What can I say about the probability that $A_{i}$ follows an alternating "up-down-up-down" pattern (or "down-up-down-up"), i.e. $A_{i} \ge A_{i+1} \mbox{ iff. } A_{i+1} \le A_{i+2}$ for all $i$?

Or, if there is a way to compute it exactly in my case $N = 20$ and $K = 18$. And, in my case $support(U) = {1,2,3,...N}$.

EDIT: Good approximations are OK.

Answer 1

A simpler dynamic programming approach is to keep a single vector of counts of zig-zag sequences that ended at a certain value in, say, a down movement, and invert it in each update. Then with $a_{ki}$ denoting the number of zig-zag sequences of length $k$ ending in $i$ on a down movement, we have

$$ a_{k+1,N+1-i}=\sum_{j=1}^ia_{kj} $$

(or with upper limit $i-1$ for strict inequality). Thus the update is described by a matrix of the form

$$ \pmatrix{ 1&1&1&1&1&1\\ 1&1&1&1&1&0\\ 1&1&1&1&0&0\\ 1&1&1&0&0&0\\ 1&1&0&0&0&0\\ 1&0&0&0&0&0 } $$

(or with zeros on the antidiagonal for strict inequality). We need to multiply by this matrix $K-1$ times, starting with initial values $a_{1i}=1$, then add all entries of the resulting vector and multiply by $2$ to also count zig-zag sequences ending in an up movement.

This is easily computed; the result, for $K=18$ and $N=20$, is $308129261694893525406$ for weak inequalities and $125294419211622187098$ for strict inequalities. (Here's the code.)

Thus the probability of obtaining a zig-zag sequence is

$$ \frac{308129261694893525406}{20^{18}}=\frac{154064630847446762703}{131072000000000000000000}\approx1.18\cdot10^{-3} $$

for weak inequalities and

$$ \frac{125294419211622187098}{20^{18}}=\frac{62647209605811093549}{131072000000000000000000}\approx4.78\cdot10^{-4} $$

for strict inequalities.

For $N\to\infty$, we can replace the discrete distribution by a continuous one. Then we're simply counting the alternating permutations of $K$ elements. This is OEIS sequence A001250 (the entry contains a lot of information about generating functions and the like), and the count for $K=18$ is $4809759350882$. Thus in this case the probability of obtaining a zig-zag sequence is

$$ \frac{4809759350882}{18!}=\frac{2404879675441}{3201186852864000}\approx7.51\cdot10^{-4}\;, $$

which is approximately the geometric mean of the other two probabilities. For finite $N$, this corresponds roughly to having $\frac12$ on the antidiagonal, i.e. letting each equality count as a satisfied inequality with probability $\frac12$. This yields a probability of obtaining a zig-zag sequence of

$$ \frac{25601115678617843777394720}{20^{18}\cdot2^{17}}=\frac{160006972991361523608717}{214748364800000000000000000}\approx7.45\cdot10^{-4}\;. $$

Answer 2

If $K$ is even, the probability of "up-down-up..." pattern, i.e. for $$B=\{A_1<A_2,A_3<A_2\wedge A_4,\dots, A_{K-1}<A_{K-2}\wedge A_K\}$$

can be calculated as

$$ P\{B\}=\sum_{1\le a_2,a_4,\dots a_K\le N}P\{A_1<a_2\}\cdots P\{A_{K-1}<a_{K-2}\wedge a_K\}\prod_{i \text{ is even}}P\{A_i=a_i\} \\ =N^{-K}\sum_{1\le a_2,a_4,\dots a_K\le N}(a_2-1)(a_2\wedge a_4-1)\cdots(a_{K-2}\wedge a_K-1) . $$

Similarly, for

$$C=\{A_1>A_2,A_3>A_2\wedge A_4,\dots, A_{K-1}>A_{K-2}\wedge A_K\}$$

$$ P\{C\}=N^{-K}\sum_{1\le a_2,a_4,\dots a_K\le N}(N-a_2)(N-a_2\vee a_4)\cdots(N-a_{K-2}\vee a_K) . $$

Also, $B\cap C=\emptyset$.

---

For $N=20$ and $K=18$, $P\{B\}=P\{C\}\approx 2.39\times 10^{-4}$.

Answer 3

This describes a dynamic programming approach to compute it.

1) Come up with a $N \times N \times 2 \times 2 $ matrix $T_K$ so that $T_K[i][j][a][b]$
(where $i,j \in support(U), a,b \in \{down, up\}$) is the probability a sequence of length $K$ being alternating AND starting with $i$, ending with $j$, and where the first change is $a$ and the last change is $b$ (this only makes sense if $K \ge 2$.) This can be done by hand somewhat easily.

Notation: $down^{-1} = up, up^{-1} = down.$

2) Let $K' = 2K - 1$ and we can then compute $$T_{K'}[i][j][a][b] = \sum_{k\in support(U),u \in\{down, up\}}{T_K[i][k][a][u] \cdot T_K[k][j][u^{-1}][b]}$$

3) Repeat step 2, this gives matrices for $K=2,3,5,9,17$ and 17 is close enough to what I want. Finally, sum over the elements of $T_{17}$ to compute the probability of any alternating sequence.