Area under random walk

Question

The problem - we have random walk set of functions such that: $$ f(0) = 0, f(x) = f(i) + \alpha_i(x-i), x \in (i,i+1], i=0,\dots,n-1 $$ where $\alpha_i \in \{-1, +1\}$ choosed uniformly with plobability $\dfrac{1}{2}$.

Need to find probability that $P(\int\limits_0^n f(x) dx = 0)$.

Thank you

Answer 1

As results above justify, consider sum $S = \sum\limits_{i=0}^{n-1}(n-i+\frac{1}{2})\alpha_i = (n+\frac{1}{2})\sum\limits_{i=0}^{n-1}\alpha_i - \sum\limits_{i=0}^{n-1}i \alpha_i$

Denote as $n^{+}$ and $n^{-}$ number of steps up and down respectively. Clear, $n=n^{+}+n^{-}$. Then:

$$ (n+\frac{1}{2})\sum\limits_{i=0}^{n-1}\alpha_i = (n+\frac{1}{2})(n^{+}-n^{-}) $$

Also, we can work around another term:

$$ \sum\limits_{i=0}^{n-1}i\alpha_i = \sum\limits_{i: \alpha_i = 1}i - \sum\limits_{j: \alpha_j = -1}j = \frac{n(n-1)}{2}-2\sum\limits_{j: \alpha_j = -1}j $$

Therefore:

$$ S = (n+\frac{1}{2})[n^{+}-n^{-}] - \frac{n(n-1)}{2} + 2\sum\limits_{j: \alpha_j = -1}j $$

$$ P(S=0) = P\left(\frac{n(n-1)}{2} - (n+\frac{1}{2})[n^{+}-n^{-}]= 2\sum\limits_{j: \alpha_j = -1}j \right) = P\left(\frac{1}{4}(n(n-1) - (2n+1)(n^{+}-n^{-})) = \sum\limits_{j: \alpha_j = -1}j\right) $$

Also, $P(S=0) = \sum\limits_{k=0}^{n-1}P(S=0|n^{-}=k)P(k)$ Fix $n^{-}=k$ first. Then we have:

$P(S=0|k) = P\left(\frac{1}{4}(n(n-1) - (2n+1)(2n-k)) = \sum\limits_{j: \alpha_j = -1}j\right)$

Denote $G(k) = \frac{1}{4}(n(n-1) - (2n+1)(2n-k)$, as $k$ fixed it's fixed number. And $\sum\limits_{j: \alpha_j = -1}j$ is sum of positive $k$ terms. The number of ways to present $G(k)$ in the form of sum positive k terms is $$\binom{G(k)+k-1}{G(k)-k}$$ Number of all possible ways to choose $k$ moments of decreasing from $n$ moments is $$\binom{n}{k}$$

Hence

$$ P(S=0|k) = \frac{\binom{G(k)+k-1}{G(k)-k}}{\binom{n}{k}} $$

And

$$ P(S=0) = \sum\limits_{k=0}^{n-1} \frac{\binom{G(k)+k-1}{G(k)-k}}{\binom{n}{k}} P(k) = \sum\limits_{k=0}^{n-1} \frac{\binom{G(k)+k-1}{G(k)-k}}{\binom{n}{k}} \binom{n}{k}\frac{1}{2^n} = \frac{1}{2^n}\sum\limits_{k=0}^{n-1}\binom{G(k)+k-1}{G(k)-k} $$

Answer 2

Partial result: Computation of the integral, first we compute the integral $$\int_i^{i+1} f(x)dx = f(i)+\frac12\cdot \alpha_i = \sum_{j=0}^i \alpha_j +\frac12\alpha_i$$

So the total integral is $$\sum_{i=0}^n \sum_{j=0}^i\alpha_j +\frac12\alpha_i=\sum_{i=0}^n(n-i+\frac12)\cdot\alpha_i$$

From this we see, that if $n$ is uneven, then the result is not an integer. Hence for those cases the probability is 0.

Answer 3

The area is only an integer after an even number of steps, so the probability of being exactly $0$ is zero if $n$ is odd. There is a simply expressed approximation for large even $n$.

The expectation of the area is $0$ and the variance of the area after $n$ steps is $\sigma^2_n = \dfrac{n(4n^2 - 1)}{12}$. Suitably rescaled, the distribution of the area converges in distribution to a normal distribution as the number of steps increase.

So, for even $n$, you should expect the probability of the area being exactly $0$ to be about $\dfrac{1}{\sqrt{2 \pi \sigma^2_n}}$. Ignoring the $-1$ term in the expression for the variance, this suggests about $\sqrt{\dfrac{3}{2 \pi n^3}}$, and it turns out this is a reasonable approximation for large $n$:

n   Pr(Area=0)  sqrt(3/(2*pi*n^3))
0   1           -
2   0           0.244301256
4   0.125       0.086373537
6   0.03125     0.047015799
8   0.03125     0.030537657
10  0.01953125  0.021850969
12  0.016601563 0.016622595
14  0.012573242 0.013191028
16  0.010559082 0.010796692
18  0.008796692 0.009048195
20  0.007562637 0.007725484
22  0.006554604 0.006696327
24  0.005769253 0.005876975
26  0.005121082 0.005212075
28  0.004589304 0.004663733
30  0.004142066 0.004205221
32  0.003763687 0.003817207
34  0.003439294 0.003485398
36  0.003159102 0.003199020
38  0.002914922 0.002949819
40  0.002700683 0.002731371
42  0.002511444 0.002538615
44  0.002343323 0.002367509
46  0.002193152 0.002214797
48  0.002058364 0.002077824
50  0.001936837 0.001954410