co.combinatorics - Random Alternating Permutations

Below is Mathematica code based on Igor Pak's answer. To get a random downup permutation on $[n]$, start by choosing the first entry $p_1$ with the appropriate probability; then randomly choose an updown permutation of size $n-1$ from the updown permutations with first entry $< p_1$; then join them together (incrementing entries $ge p_1$ in the updown permutation).

To implement this method, we actually need code to generate a random downup permutation with first entry $ge$ a specified number $k$ and the code below does so. It uses the ComplementPermutation operation to interchange updown and downup permutations.

(* e[n,k] is the Entringer number *)

e[0,0] = 1;
e[n_,0]/;n>=1 := 0;
e[n_,k_]/;k>n || k<0 := 0
e[n_,k_] := e[n,k] = e[n,k-1] + e[n-1,n-k]

ComplementPermutation[perm_] := Module[{n=Length[perm]}, n+1-perm];

incrementSpecifiedAndUp[perm_,k_]:=perm/.{i_/;i>=k :> i+1};

partialSums[list_] := Drop[FoldList[Plus,0,list],1];

RandomUpDownPermFirstEntryAtMostk[n_,k_]/;k==n :=
RandomUpDownPermFirstEntryAtMostk[n,n-1];
RandomUpDownPermFirstEntryAtMostk[n_,k_]/;1<=k<n :=
ComplementPermutation[RandomDownUpPermFirstEntryAtLeastk[n,n+1-k]]

RandomDownUpPermFirstEntryAtLeastk[1,1]={1};
RandomDownUpPermFirstEntryAtLeastk[2,2]={2,1};

RandomDownUpPermFirstEntryAtLeastk[n_,k_]/; n>=3 && 2<=k<=n :=
Module[{keys,m,i,firstEntry,restOfPerm},

(* pick first entry using the Entringer distribution *)
keys=partialSums[Table[e[n-1,j],{j,k-1,n-1}]];
m=Random[Integer,{1,Last[keys]}];
i=1;
While[Not[ m<=keys[[i]] ],i=i+1];
firstEntry=k-1+i;

(* choose restOfPerm uniformly from updowns with their first entry < firstEntry *)
restOfPerm=RandomUpDownPermFirstEntryAtMostk[n-1,k-2+i];

(* amalgamate firstEntry and restOfPerm *)
Join[{firstEntry},incrementSpecifiedAndUp[restOfPerm,firstEntry]] ]

RandomDownUpPerm[1]={1};
RandomDownUpPerm[n_]/;n>=2 := RandomDownUpPermFirstEntryAtLeastk[n,2]

Sample output:
In[264]:=RandomDownUpPerm[15]
Out[264]=
{8, 2, 4, 1, 15, 6, 7, 3, 10, 9, 13, 11, 14, 5, 12}