Summation coming about in the process of solving a 3d random walk $\sum\limits_{i=0}^n {n \choose i}^2 {2(n-i)\choose (n-i)}$

87 Views Asked by At

I'm looking for a closed form for the summation:

$$S_n = \sum\limits_{i=0}^n {n \choose i}^2 {2(n-i)\choose (n-i)}$$


Why do I care about this summation? It comes about as I'm trying to get a closed form for the 3-d random walk (a drunk bird). This is extending the approach used in example 4.18 of the book Introduction to Probability models by Sheldon Ross (10th edition) for determining if 1-d and 2-d random walks are transient or recurrent.

The probability that a 3-d random walk where the probabilities of moving along the positive and negative x, y and z-axes are equal returning to the origin after taking $2n$ steps is:

$$P^{2n}_{00} = \sum\limits_{i=0}^n \sum\limits_{j=0}^{(n-i)} \frac{(2n)!}{(i!)^2(j!)^2((n-i-j)!)^2}\frac{1}{6^{2n}}$$

The expected number of times the walk comes back to the origin when its run for an infinite number of steps becomes:

$$E_{00} = \sum\limits_{n=1}^\infty \sum\limits_{i=0}^n \sum\limits_{j=0}^{(n-i)} \frac{(2n)!}{(i!)^2(j!)^2((n-i-j)!)^2}\frac{1}{6^{2n}}$$

$$E_{00} = \sum\limits_{n=1}^\infty \frac{(2n)!}{6^{2n}}\sum\limits_{i=0}^n \frac{1}{(i!)^2}\sum\limits_{j=0}^{(n-i)} \frac{1}{(j!)^2((n-i-j)!)^2}$$

$$ = \sum\limits_{n=1}^\infty \frac{(2n)!}{6^{2n}}\sum\limits_{i=0}^n \frac{1}{(i!)^2((n-i)!)^2}\sum\limits_{j=0}^{(n-i)} \frac{((n-i)!)^2}{(j!)^2((n-i-j)!)^2}$$ $$ = \sum\limits_{n=1}^\infty \frac{(2n)!}{6^{2n}}\sum\limits_{i=0}^n \frac{1}{(i!)^2((n-i)!)^2}\sum\limits_{j=0}^{(n-i)} {n-i \choose j}^2$$ $$ = \sum\limits_{n=1}^\infty \frac{(2n)!}{(n!)^2}\frac{1}{6^{2n}}\sum\limits_{i=0}^n \frac{(n!)^2}{(i!)^2((n-i)!)^2}{2(n-i) \choose (n-i)}$$ $$ = \sum\limits_{n=1}^\infty \frac{(2n)!}{(n!)^2}\frac{1}{6^{2n}}\sum\limits_{i=0}^n {n \choose i}^2{2(n-i) \choose (n-i)}$$ $$ = \sum\limits_{n=1}^\infty \frac{(2n)!}{(n!)^2}\frac{1}{6^{2n}}\sum\limits_{i=0}^n {n \choose i}^2{2(n-i) \choose (n-i)}$$ $$ = \sum\limits_{n=1}^\infty \frac{(2n)!}{(n!)^2}\frac{1}{6^{2n}}S_n$$ Where $S_n$ is our summation of interest.

1

There are 1 best solutions below

0
On BEST ANSWER

$$S_n = \sum\limits_{i=0}^n {n \choose i}^2 {2(n-i)\choose (n-i)}$$ $$S_n= \frac{2^{2 n}\, \Gamma (n+1)^2}{\sqrt{\pi }}\sum\limits_{i=0}^n \frac{ \Gamma \left(n+\frac{1}{2}-i\right)}{2^{2i}\,\Gamma (i+1)^2 \,\Gamma (n+1-i)^3}$$ The result will involve an hypergeometric function and effectively $$\sum\limits_{i=0}^n \frac{ \Gamma \left(n+\frac{1}{2}-i\right)}{2^{2i}\,\Gamma (i+1)^2 \,\Gamma (n+1-i)^3}=$$ $$\frac{\Gamma \left(n+\frac{1}{2}\right)}{\Gamma (n+1)^3}\, _3F_2\left(-n,-n,-n;1,\frac{1}{2}-n;\frac{1}{4}\right)$$ Simplifying $$S_n=\binom{2 n}{n} \, _3F_2\left(-n,-n,-n;1,\frac{1}{2}-n;\frac{1}{4}\right)$$

Computing the first terms $$\{1,3,15,93,639,4653,35169\}$$ this is sequence $A002893$ in $OEIS$.

In the formula section, you will notice that, in year $2012$, Vaclav Kotesovec proposed the simple $$S_n \sim \frac{3^{2 n+\frac{3}{2}}}{4 \pi n}$$ which is more than decent (relative error smaller than $1$% if $n>24$).