Probability of alternating sequence from uniform distribution 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.
 A: 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}$.
A: 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.
