Let $ \Theta \ge 1 $ and $n \ge 1 $ be integers. Consider integer sequences of length $n$ composed of entries each one running independently over the range ${\mathfrak R}_\Theta:=\left\{-\Theta,-\Theta+1,\cdots,-2,-1,+1,+2,\cdots,+\Theta-1,+\Theta \right\}$. Clearly the total number of such sequences reads $(2 \Theta)^n$. My question is the following: What is the number of sequences of that kind that have the property that all entries of the cumulative process are strictly positive. We will denote this number as ${\mathfrak B}_n^{(\Theta)} := \sum\limits_{x_1 \in {\mathfrak R}_\Theta} \sum\limits_{x_2 \in {\mathfrak R}_\Theta} \cdots \sum\limits_{x_n \in {\mathfrak R}_\Theta} \prod\limits_{i=1}^n 1_{\sum\limits_{\xi=i}^n x_\xi > 0} $.
Clearly one approach to this problem is to find the joint probability distribution of the cumulative process at all possible times and then , by using the integral representation of the Kronecker delta function do the sums over the entries as geometric series and express the sought after quantity as a multivariate integral over a hypercube. We have done that and produced the formula below:
\begin{eqnarray} {\mathfrak B}_n^{(\Theta)} &=& \frac{1}{\pi^n} \int\limits_{[0,2\pi]^n} \prod\limits_{i=1}^n \left[ e^{\frac{\imath}{2} \phi_i (1+(n-i+1) \Theta)} \frac{\sin(\frac{\phi_i}{2}(n-i+1) \Theta)}{\sin(\frac{\phi_i}{2})} \cdot \cos\left( \frac{1+\Theta}{2} \cdot \Phi_i\right) \cdot \frac{\sin(\frac{\Theta}{2} \Phi_i)}{\sin(\frac{1}{2} \Phi_i)} d\phi_i \right] \\ &=& \left( \begin{array}{cccc} 1 & 1 & 2 & 3 & \cdots \\ 2 & 5 & 17 & 58 & \cdots \\ 3 & 12 & 60 & 311 & \cdots\\ \vdots \end{array} \right) \end{eqnarray} where $\Phi_i:= \phi_1+\cdots+\phi_i$ for $i=1,\cdots,n$. In the second line above the rows are labelled by $\Theta \ge 1$ and the columns by $n \ge 1$.
The code below verifies the result:
(** Here the increments have 2 Theta discrete values : -Theta, \
-Theta+1,..,-2,-1, 1,2,....,Theta-1,+Theta **)
Theta =.;
Table[Sum[Product[If[Sum[x[xi], {xi, i, n}] > 0, 1, 0], {i, 1, n}],
Evaluate[Sequence @@
Table[{x[xi], Join[Range[-Theta, -1], Range[1, Theta]]}, {xi, 1,
n}]]], {Theta, 1, 3}, {n, 1, 4}]
Table[1/(Pi)^(n) NIntegrate[
Product[Exp[
I/2 phi[i] (1 + (n - i + 1) Theta)] (Sin[
phi[i]/2 (n - i + 1) Theta])/(
Sin[phi[i]/2]) Cos[ (1 + Theta)/2 Sum[phi[xi], {xi, 1, i}]] Sin[
Theta/2 Sum[phi[xi], {xi, 1, i}]]/
Sin[1/2 Sum[phi[xi], {xi, 1, i}]], {i, 1, n}],
Evaluate[
Sequence @@ Table[{phi[xi], 0, 2 Pi}, {xi, 1, n}]]], {Theta, 1,
3}, {n, 1, 4}]
Now, if $\Theta=1$ (first row in the table) the problem in question is equivalent to the Bertrand's ballot theorem and admits a closed form solution $ {\mathfrak B}_n^{(1)} = \sum\limits_{q=0}^{\lfloor n/2 \rfloor} \binom{n}{q} (n-2q)/n $. As a matter of fact the Wikipedia website on that gives several proofs of that result one of which is particularly elegant because it uses the reflection principle.
Another application of this problem is to determine the probability distribution of the running supremum of a random walk. We know very well that this problem is solved so we suspect that the solution to this problem should exist as well.
In view of all this my question is can we find a closed form expression in the general case $\Theta > 1$. Another question would be can the Proof by reflection from the wiki page be generalized in this setting?
Here is a partial answer to this question. Note the sought after quantity can be written as follows:
\begin{eqnarray} &&{\mathfrak B}_n^{(\theta)}=\\ && \sum\limits_{k_n=1}^\theta \sum\limits_{k_{n-1}=1\vee(k_n-\theta)}^{2 \theta \wedge (k_n+\theta)} \sum\limits_{k_{n-2}=1\vee(k_{n-1}-\theta)}^{3 \theta \wedge (k_{n-1}+\theta)} \cdots \sum\limits_{k_{\xi}=1\vee(k_{\xi+1}-\theta)}^{(n+1-\xi) \theta \wedge (k_{\xi+1}+\theta)} \cdots \sum\limits_{k_{1}=1\vee(k_{2}-\theta)}^{(n) \theta \wedge (k_{2}+\theta)} 1_{k_1 \neq k_2} \wedge 1_{k_2 \neq k_3} \wedge \cdots \wedge 1_{k_{n-1} \neq k_n} % \end{eqnarray} for $\xi = n,\cdots,1$.
The formula above has a following interpretation. We count all random walks where the partial sums $k_\xi:= x_\xi+\cdots+x_n$ are strictly positive , i.e. $k_\xi = 1,\cdots,(n+1-\xi)\theta$, and where the returns $x_\xi:= k_\xi - k_{\xi+1}$ are in the required range, i.e. $x_\xi \in {\mathfrak R}_\theta$.
Now, by evaluating the above for a fixed $n=1,2,3,\cdots$ and an arbitrary $\theta$ we discovered that the result is a polynomial of order $n$ in $\theta$. In other words we have:
\begin{equation} {\mathfrak B}_n^{(\theta)}= \sum\limits_{\xi=0}^{n-1} {\mathfrak A}_{n,\xi} \binom{\theta+\xi}{n} \end{equation}
where
\begin{equation} \left({\mathfrak A}_{n,\xi}\right)_{n=1,\xi=0}^{\cdots, n-1} = \left( \begin{array}{l} \{1\} \\ \{2,1\} \\ \{4,9,2\} \\ \{8,51,43,3\} \\ \{16,240,510,173,6\} \\ \{32,1030,4576,4056,691,10\} \\ \{64,4207,35141,64062,28978,2663,20\} \\ \end{array} \right) \end{equation}
In general:
\begin{eqnarray} {\mathfrak A}_{n,0} &=& 2^n \\ &\vdots& \\ {\mathfrak A}_{n,n-1} &=& {\mathfrak B}_n^{(1)} \end{eqnarray}
As always, the code below verifies the result.