Define a graph $G_n$ whose vertices are the points in $\mathbb{R}^n$ with an edge connecting any two points that are one unit apart. Such a graph is called the unit distance graph in $\mathbb{R}^n$. Let's consider a random walk of $s$ steps on $G_n$, beginning at the origin. Let $P=P(n,s)$ be the probability that the last point in the walk is within one unit of the origin.
The answer for the degenerate case $n=1$:
$$P(1,s)=\begin{cases}\frac{\displaystyle\binom{s}{s/2}}{\displaystyle 2^{s+1}}&s\text{ even}\\\frac{\displaystyle\binom{s}{(s+1)/2}}{\displaystyle 2^{s-1}}&s\text{ odd}\end{cases}$$
Some other initial results:
- $P(n,1)=1$
- In the answer to this problem, we see that $P(2,s)=\frac{1}{s+1}$ for $s\ge 2$.
- Intuitively, for fixed $n$, $\lim_{s\to\infty}P(n,s)=0$
It also shouldn't be that hard to compute $P(n,2)$. Take two unit hyperspheres whose centers are one unit apart. If $A_n$ is the surface area of one sphere contained in the other, then
$$P(n,2)=\frac{A_n}{|S_{n-1}|}\frac{A_n\Gamma(\frac{n}{2}+1)}{n\pi^{n/2}}$$
Three related questions:
- What is the general expression for $P(n,s)$?
- Can the problem for $n=2$ be solved without integration? The simple answer provided above suggests there might be a more elementary method than the one given in the link.
- Can the general problem be solved without integration?