# Help needed solving for bounded random walk expectation; problem involves strange (to me) Factorial/Gamma-function summation

Posted this at math overflow, but they redirected me here.

I'm currently trying to solve for the expectation of a bounded Gaussian random walk. That is to say, each step is a random variable with $u=0$ and $\sigma=s$. With the help of monte-carlo analysis and drawn-out path trees, I've thus far deduced about the problem that:

1. That I can look at solving the problem for steps that follow a standard normal distribution, as opposed to an arbitrary normal distribution, as sigma just scales the final expectation, which makes sense, as it scales every step as well.
2. Thanks to the central-limit theorem, the expectation of a regular-old 1D random walk will eventually converge to the same value as the expectation of a Gaussian random walk for even small values of $N$, the number of steps in the walk. (e.g. $N>10$). So, if I solve the problem for a 1D random walk, I'll have my answer for a gaussian random walk.
3. As opposed to a 1D Random Walk develops according to Pascal's Triangle, with the walk destinations following a normal distribution, a bounded random walk develops according to a folded Pascal's Triangle, and approximates a half-normal distribution. A folded pascal's triangle means that rather from ranging from $-N$ to $N$, evens or odds and $0$ only, as Pascal's Triangle does, it ranges from $0$ to $N$, evens and odds inclusive; the evens $(N, N-2)$ will be the same as they were in the regular Pascal's Triangle, and the odds will have the same value as does $i+1$. (e.g. $N-1$ has the same value as $N$, $N-3$ the same value as $N-2$, etc). The rest of the problem thus becomes pretty similar to solving for the expectation of a non-bounded 1D random walk. You just have to sum up everything while multiplying by weight (e.g. the step) and divide by the total possible number of walks. I've found that mathworld has a really great resource for this. However, I am stuck on solving the summation involving the two factorials and the flipped gamma function, #22/#29 from this link.

http://mathworld.wolfram.com/RandomWalk1-Dimensional.html

After carrying you the derivation step-by-step, it just does this in one simple line like its so obvious... and I'm not quite sure what to make of it! And unfortunately, although the bounded random walk is very similar up to this point, one of its terms looks just #22 except it has a "2d-1" term in the numerator of the summation, like #29, instead of a "2d" term. (the 2 is factored to the outside of the summation in #22). The other term is just like #29, except the second factorial on the bottom is $(w-k-1)!$ instead of $(w-k)!$.

Can anyone help me here? If not on how to solve my current problem, then least what the heck is going on in that original derivation !!! I feel like I'm so close, and this is driving me up the wall.

-
You might want to consider what the distribution of positions looks like after 1 step, after 2 steps, after 3 steps... Check it out and see if you can generalize / prove by induction. This is a lot easier than you think it is. –  Craig Sep 15 '11 at 23:17
Well, like I said in my original post, the distribution of positions after N steps results in a folded Pascal's triangle. Trying to generalize this result is the exact question that I'm trying to solve. If you have any insight, why are you being so coy? –  Joseph Ryan Sep 15 '11 at 23:26
Ah, nevermind. Thanks anyways guys. –  Joseph Ryan Sep 16 '11 at 7:17
If you figured out the answer to your question, you should post it here so that other people who come across it can see. If not, I can close or delete the question if that's what you prefer. –  Zev Chonoles Sep 16 '11 at 7:40
You're basically saying that each step is an independent random normal variable drawn from $N(0,\sigma)$. So the probability density for $x_1 + x_2 = X$ is $\int_{-\infty}^{\infty} dx_1 \frac{1}{\sqrt{2\pi \sigma^2}} e^{-x_1^2/2\sigma^2} * \frac{1}{\sqrt{2\pi \sigma^2}} e^{-(X - x_1)^2/2\sigma^2}$ = $\frac{1}{\sqrt{2\pi (2\sigma^2)} e^{-X^2/2(2\sigma^2}$. And the probability density for the position after 3 steps is the same with $(2\sigma^2)$ replaced by $(3\sigma^2)$. I'm not sure where you are getting a "folded Pascal triangle" from. –  Craig Sep 16 '11 at 17:09