A different answer from the ones so far: Quantum randomness is another kind of randomness that is a generalization of traditional randomness, i.e. classical or non-quantum probability. I think that it fits the question because you could likewise say that non-Euclidean geometry, interpreted as not-necessarily-Euclidean geometry, is a generalization of Euclidean geometry.
A classical probability space is usually defined as a $\sigma$-algebra $\Omega$ with a normalized measure. From the Bayesian viewpoint the measure could equally well be called a "state". Now, a $\sigma$-algebra is the algebra of Boolean random variables with a certain set of axioms. But you can just as well write down axioms for $L^\infty(\Omega)$, the algebra of bounded complex random variables. In favorable cases, it is a commutative von Neumann algebra. In quantum probability you instead allow a non-commutative von Neumann algebra $\mathcal{M}$. Also, in standard quantum probability you keep the usual completed tensor product $\mathcal{M} \otimes \mathcal{N}$ as the model of a joint system. (Free probability theory is still quantum probability, but with a certain free product instead of a tensor product.) You also still have states, conditional states, joint states, correlations, generalized stochastic maps, etc.
Some of the variant models mentioned so far lead to different theorems, but generally give the same answers in combinatorial probability, questions like the birthday paradox or modeling games of chance. Quantum probability leads to a significantly different picture of combinatorial probability, generalizing the old one, but also allowing new answers such as violation of Bell's inequalities, covariance matrices that are Hermitian rather than real symmetric, new complexity classes such as BQP, etc.
Other variant models mentioned so far no longer give any answers for combinatorial probability, for instance models of forcing. But, part of the interest in probability is that it models real life. Amazingly, so does quantum probability; that was the central discovery of quantum mechanics when it was defined in the 1920s and 1930s.
For $t$ fixed, the count is proportional to $\lambda^n$, where $\lambda = 2 \cos \frac\pi{2t+2}$ is the principal eigenvalue of the adjacency matrix of the path with $2t+1$ vertices. The all-positive (Perron-Frobenius) eigenvector corresponding to $\lambda$ is
$$\bigg(\sin \frac{\pi}{2t+2}, \sin \frac{2\pi}{2t+2},\sin \frac{2\pi}{2t+2},\dots,sin \frac{(2t+1)\pi}{2t+2}\bigg).$$
Since $-\lambda$ is also an eigenvalue, the stable behavior of the distribution of endpoints of paths which stay in $[-t,t]$ is an oscillation between the odd entries
$$\bigg(\sin \frac{\pi}{2t+2}, 0,\sin \frac{3\pi}{2t+2},0,\dots,\sin \frac{(2t-1)\pi}{2t+2},0,\sin \frac{(2t+1)\pi}{2t+2}\bigg).$$
and even entries
$$\bigg(0,\sin \frac{2\pi}{2t+2}, 0,\sin \frac{4\pi}{2t+2},0,\cdots ,0,\sin \frac{2t\pi}{2t+2},0\bigg).$$
The exact count of paths staying in $[-t,t]$ is a sum of signed binomial coefficients.
The number of paths from $0$ to $i$ is 0 if $n \not \equiv i ~\mod 2$, and $n \choose (n\pm i)/2$ when $n \equiv i ~\mod 2$.
The number of paths which never leave $[-t,t]$ from $0$ to $i \in [-t,t]$ with $n \equiv i ~\mod 2$ is
$$ \sum_{j\in \mathbb Z} (-1)^j {n\choose (n +i)/2 + j(t+1)}$$
by the reflection principle applied to the group of isometries of $\mathbb R$ generated by reflecting about $t+1$ and $-t-1$.
If you sum over all $i \in [-t,t]$, then when $n$ is even, you get a signed sum of binomial coefficients with $t+1$ positive signs in a row alternating with $t+1$ negative signs in a row. If $n$ is odd, then you get $t$ positive signs in a row, skip a term (give it a coefficient of $0$ instead of $\pm 1$), then $t$ negative signs in a row, skip a term, etc.
For example, for $n=100, t=2,$ the number of paths is
$$ ... +{100\choose 43} + {100\choose 44} + {100 \choose 45} - {100 \choose 46} - {100 \choose 47} - {100\choose 48} + {100\choose 49} + {100 \choose 50} + {100\choose 51} - ...$$
For $n=101, t=2,$ the number of paths is
$$ ... +{101\choose 44} + {101\choose 45} - {101\choose 47} - {101 \choose 48} + {101\choose 50} + {101\choose 51} - {101\choose 53} - {101\choose 54} + ...$$
These can be summed using the techniques in the answers to the Binomial distribution parity question.
A lot more can be said when $t$ varies, but the answers are more complicated. For $t$ slowly increasing, as $c\sqrt[3]n$, there is enough time for the distribution to stabilize (for each parity) at a given value of $t$, since the ratio between the magnitudes of the largest two eigenvalues and the magnitudes of the next two is about $1+c/t^2$, and the principal eigenvectors have a small $L^1$ distance for adjacent values of $t$. You should pick up a constant factor for each transition. In other words, the number of paths when you spend at least $n_t \gt c t^2$ steps at a given $t$ should be
$$C \prod_{t \le t_{max}} (2 \cos \frac{\pi}{2t+2})^{n_t}$$
where $C$ is between some functions $f_{lower}(t_{max}) \lt C \lt f_{upper}(t_{max})$ which does not depend on the values of $n_t$. I don't think the $n_t \gt c t^2$ condition is sharp for this behavior. Something like $n_t \gt c t^2/\log t$ should work, too. The geometry of the eigenvectors for adjacent values of $t$ lets you estimate $f_{lower}$ and $f_{upper}$.
For $t$ more rapidly increasing, different behaviors occur. By the law of the iterated logarithm, if $t$ increases as $t(n) = \sqrt {(2-\epsilon) n \log\log n},$ random paths will almost surely violate the constraint. I think there are precise versions of the law of the iterated logarithm which may tell you when a positive proportion of random paths do not violate the constraint. I would guess that if $t(n) = \sqrt{(2+\epsilon) n \log\log n}$ then a positive percentage of random paths won't violate the constraint.
Best Answer
A good book:
Lectures on the combinatorics of free probability-A. Nica and R. Speicher
See the following article and the references therein for information on noncommutative ergodic theory:
Noncommutative maximal ergodic theorems-M Junge and Q. Xu
http://arxiv.org/PS_cache/math/pdf/0505/0505308v2.pdf
(see also other articles of these authors)