Return to Answer

Third update. Alas, the conjecture in my second update is false. Unless there is an error in my code, the sequence of coefficients of $N_n(r)$ for $2\leq n\leq 7$ are $(1,2)$, $(1,8,6)$, $(1,25,55,24)$, $(1,69,361,394,120)$, $(1,176,1999,4416,3083,720)$, $(1,426,9836,41019,52193,26620,5040)$. It is easy to see why the leading coefficient of $N_n(r)$ is $n!$.

Theorem. The probability $P_n(r)$ that the walk is proper is given by $$ P_n(r) = \frac{1}{(1+r)^nn!}( \sum r^{1+f(w,\beta)}), $$ summed over all pairs $w=a_1a_2\cdots a_n\in S_n$ and $\beta=(b_1,\dots, b_{n-1})\in \lbrace 0,1\rbrace^n$ satisfying the conditions (b) and (c) above, where $f(w,\beta)$ is the number of integers $1\leq i\leq n-1$ for which either $a_i\lt a_j$ and $b_i=0$, or $a_i\gt a_j$ and $b_i=1$.

Theorem. The probability $P_n(r)$ that the walk is proper is given by $$ P_n(r) = \frac{1}{(1+r)^nn!}\sum r^{1+f(w,\beta)}, $$ summed over all pairs $w=a_1a_2\cdots a_n\in S_n$ and $\beta=(b_1,\dots, b_{n-1})\in \lbrace 0,\pm 1\rbrace^n$ satisfying the conditions (b) and (c) above, where $f(w,\beta)$ is the number of integers $1\leq i\leq n-1$ for which either $a_i\lt a_j$ and $b_i=0$, or $a_i\gt a_j$ and $b_i=1$.

Second update. The method above can be applied to the $[l,r]$ generalization mentioned by Lwins in his comment. By rescaling we may assume $l=-1$. If we are at $y$ sometime during the walk, choose a number $x$ uniformly from $[0,1]$. With probability 1/2 step from $y$ to $y+\frac{r-1}{2}+\frac{r+1}{2}x$. With probability 1/2 step from $y$ to $y-1-\frac{r+1}{2}x$. This gives a uniform probability of stepping from $y$ to a point in the interval $[y-1,y+r]$. It has the property that once $x$ is chosen, the value of $y$ is determined modulo $\frac{r+1}{2}$. Thus the walk can be described as follows: pick uniformly and independently $0\lt x_1\lt \cdots\lt x_n \lt \frac{r+1}{2}$, pick a permutation $w$ uniformly from the symmetric group $S_n$, and a sequence $\epsilon=(\epsilon_1,\dots,\epsilon_n)$ of independently distributed signs, with a probability of $\frac{r}{r+1}$ for a plus sign and $\frac{1}{r+1}$ for a minus sign. Go through the same procedure as above, working mod $\frac{r+1}{2}$ instead of mod 1. Again a proper walk (i.e., one which never becomes negative) depends only on $w$ and $\epsilon$, and we get the following result:

Theorem. The probability $P_n(r)$ that the walk is proper is given by $$ P_n(r) = \frac{1}{(1+r)^nn!}( \sum r^{1+f(w,\beta)}), $$ summed over all pairs $w=a_1a_2\cdots a_n\in S_n$ and $\beta=(b_1,\dots, b_{n-1})\in \lbrace 0,1\rbrace^n$ satisfying the conditions (b) and (c) above, where $f(w,\beta)$ is the number of integers $1\leq i\leq n-1$ for which either $a_i\lt a_j$ and $b_i=0$, or $a_i\gt a_j$ and $b_i=1$.

For instance, $P_2(r)= (r+2r^2)/2(r+1)^2$ and $P_3(r) =(r+8r^2+6r^3)/6(r+1)^3$. I conjecture that the numerator $N_n(r)$ of $P_n(r)$ is just the polynomial $\sum B_{n,i}r^i$ defined by equation (4) of http://math.mit.edu/~rstan/pubs/pubfiles/29.pdf. This paper gives some additional information about the polynomials $\sum B_{n,i}r^i$. Much additional information can be found in the literature on Stirling permutations, e.g., Bona proves in http://wenku.baidu.com/view/dfa70012cc7931b765ce15e4.html that all zeros of this polynomial are real.