Random Walks in the Plane

Jonathan M. Borwein<fnref n="1" /> and Dirk Nuyens<fnref n="2" />†and Armin Straub<fnref n="3" /> and James Wan<fnref n="4" />

**Abstract.** We study the expected distance of a two-dimensional walk in the plane with unit steps in random directions. A series evaluation and recursions are obtained making it possible to explicitly formulate this distance for small number of steps. Formulae for all the moments of a 2-step and a 3-step walk are given, and an expression is conjectured for the 4-step walk. The paper makes use of the combinatorical features exhibited by the even moments which, for instance, lead to analytic continuations of the underlying integral.

**Résumé.** Nous étudions la distance espérée d'une marche aléatoire à deux dimensions et à pas unité dans des directions aléatoires. Nous obtenons une évaluation des séries et des récurrences qui permettent de formuler explicitement cette distance pour un petit nombre de pas. Nous donnons des formules pour tous les moments d'une marche aléatoire à 2 et à 3 pas et nous formulons une conjecture pour l'expression d'une marche à 4 pas. Pour les moments pairs, nous utilisons des relations combinatoires qui, par exemple, permettent le prolongement analytique des intégrales.

**Resumen.** Se estudia la expectación de la distancia recorrida por una marcha aleatoria en dimensión 2 con pasos de longitud 1. Se presenta una expresión en forma de series y recursiones que permiten encontrar formulas explícitas para la distancia mencionada para un número pequeño de pasos. Fórmulas para todos los momentos en dimensiones 2 y 3 son dadas y se conjectura una expresión analítica para el caso de dimensión 4. Este artículo emplea aspectos de la combinatoria que aparecen en los momentos de order par, para producir una continuación analítica de la integral asociada con este proceso.

**Keywords:** random walks, hypergeometric functions, high-dimensional integration, analytic continuation

# 1 Introduction and Preliminaries

This is an extended abstract of (BNSW09) which contains the exposition given here complemented with much more detail. In particular, we often refer to (BNSW09) for full proofs of statements that we present.

Throughout, we consider the *n*-dimensional integral

$$W_n(s) := \int_{[0,1]^n} \left| \sum_{k=1}^n e^{2\pi x_k i} \right|^s dx \quad (1)$$

<footnote n="1">¹University of Newcastle, Australia. Email: jonathan.borwein@newcastle.edu.au</footnote>

<footnote n="2">²K.U.Leuven, Belgium. Email: dirk.nuyens@cs.kuleuven.be</footnote>

<footnote n="3">³Tulane University, New Orleans, USA. Email: astraub@tulane.edu</footnote>

<footnote n="4">⁴University of Newcastle, Australia. Email: james.wan@newcastle.edu.au</footnote>

<footnote>†part of this work done while a research associate at the Department of Mathematics and Statistics, University of New South Wales, Australia</footnote>
which occurs in the theory of uniform random walk integrals in the plane, where at each step a unit-step is taken in a random direction, see Figure 1. As such, the integral (1) expresses the sth moment of the distance to the origin after n steps. Particularly interesting is the special case of the expected distance $W_n(1)$ after n steps.

A lot is known about the one-dimensional random walk. E.g., its expected distance after n unit-steps is $(n-1)!!/(n-2)!!$ when n is even and $n!!/(n-1)!!$ when n is odd (and asymptotically this distance is $\sqrt{2n/\pi}$). For the two-dimensional walk no such explicit expressions were known, although the term random walk first appears in a (related) question by Karl Pearson in Nature in 1905 (Pea1905) for explicitly this two-dimensional walk under consideration. Pearson triggered answers by Lord Rayleigh (Ray1905) on the asymptotic behaviour of the probability for n very large and by Benett (referred to in (Pea1905b)) for the case n = 2, after which he concluded that there still was a large interest for the unresolved case of small n which is dramatically different from the case of large n. Note that the expected value for the root-mean-square distance is well known to be just $\sqrt{n}$ (in that case the implicit square root in (1) disappears which greatly simplifies the problem).

<figure><img src="image_1.png" /><figcaption>Fig. 1: Random walks in the plane.</figcaption></figure>

We picked up the special case $s = 1$ of (1) from the whiteboard in the common room at UNSW where it was written as a generalization of a discrete problem in a cryptographic context by Peter Donovan, discussed in (Don09). However, the problem in itself appears in numerous applications, e.g., in problems involving Brownian motion in physics. Numerical values of $W_n$ evaluated at integers can be seen in Tables 1 and 2. One immediately notices the apparent integer sequences for the even moments—which are the moments of the squared expected distance (thus the square root for $s = 2$ gives the root-mean-square distance $\sqrt{n}$). By experimentation and some sketchy arguments we quickly conjectured and believed that, for k a nonnegative integer,

$$W_3(k) = \mathrm{Re} \, {}_3F_2\left(\frac{1}{2}, -\frac{k}{2}, -\frac{k}{2} | 4\right). \qquad (2)$$

(In fact, (2) also holds for negative odd integers.) This was for long a mystery, but it will be proven in the final section of the paper.
<table><caption>Tab. 1: $W_n(s)$ at even integers.</caption><thead><tr><th>n</th><th>s = 2</th><th>s = 4</th><th>s = 6</th><th>s = 8</th><th>s = 10</th><th>(Slo09)</th></tr></thead><tbody><tr><td>2</td><td>2</td><td>6</td><td>20</td><td>70</td><td>252</td><td>A000984</td></tr><tr><td>3</td><td>3</td><td>15</td><td>93</td><td>639</td><td>4653</td><td>A002893</td></tr><tr><td>4</td><td>4</td><td>28</td><td>256</td><td>2716</td><td>31504</td><td>A002895</td></tr><tr><td>5</td><td>5</td><td>45</td><td>545</td><td>7885</td><td>127905</td><td></td></tr><tr><td>6</td><td>6</td><td>66</td><td>996</td><td>18306</td><td>384156</td><td></td></tr></tbody></table>

<table><caption>Tab. 2: $W_n(s)$ at odd integers.</caption><thead><tr><th>n</th><th>s = 1</th><th>s = 3</th><th>s = 5</th><th>s = 7</th><th>s = 9</th></tr></thead><tbody><tr><td>2</td><td>1.27324</td><td>3.39531</td><td>10.8650</td><td>37.2514</td><td>132.449</td></tr><tr><td>3</td><td>1.57460</td><td>6.45168</td><td>36.7052</td><td>241.544</td><td>1714.62</td></tr><tr><td>4</td><td>1.79909</td><td>10.1207</td><td>82.6515</td><td>822.273</td><td>9169.62</td></tr><tr><td>5</td><td>2.00816</td><td>14.2896</td><td>152.316</td><td>2037.14</td><td>31393.1</td></tr><tr><td>6</td><td>2.19386</td><td>18.9133</td><td>248.759</td><td>4186.19</td><td>82718.9</td></tr></tbody></table>

In Section 2 we develop an infinite series expression for $W_n(s)$ which holds for all real $s > 0$, see Theorem 2.1. From this it then follows in Corollary 2.2 that the even moments of $W_n(s)$ are given by integer sequences. The combinatorial features of $f_n(k) := W_n(2k)$, $k$ a nonnegative integer, are studied in Section 3. We show that there is a recurrence relation for the numbers $f_n(k)$ and confirm that indeed, an observation from Table 1, the last digit in the column for $s = 10$ is always $n$ modulo 10.

In Section 4 some analytic and numerical results for $n = 1, 2, 3$ are given and we lift the recursion for $f_n(k)$ to $W_n(s)$ by the use of Carlson's theorem. The recursions for $n = 2, 3, 4$ are given explicitly as an example. These recursions then give further information on the poles of the analytic continuations of $W_n$ (graphs of $W_n$ for $n = 3, 4, 5, 6$ and their analytic continuations are shown in Figure 2). From here we conjecture the recursion

$$W_{2n}(s) \stackrel{?}{=} \sum_{j \ge 0} \binom{s/2}{j}^2 W_{2n-1}(s-2j),$$

based on analytic continuations, and the explicit form, related to (2),

$$W_4(k) \stackrel{?}{=} \mathrm{Re} \sum_{j \ge 0} \binom{s/2}{j}^2 {}_3F_2 \left( \frac{1}{2}, -\frac{k}{2} + j, -\frac{k}{2} + j \middle| 4 \right).$$

for $k$ a positive integer. High precision numerical evaluations for $n = 3$ and $n = 4$ are given.

In the final section we explore the underlying probability model more closely, starting with another answer to Pearson, this time by Kluyver (Klu1906). Finally, considering conditional densities, we are able to give an alternative form for $W_3(s)$ which eventually leads to a proof of (2).
<figure><img src="image_2.png" /><figcaption>Fig. 2: Various $W_n$ and their analytic continuations.</figcaption></figure>

## 2 A Series Evaluation of $W_n(s)$

**Theorem 2.1** For Re $s \ge 0$,

$$W_n(s) = n^s \sum_{m \ge 0} (-1)^m \binom{s/2}{m} \sum_{k=0}^{m} (-1)^k \binom{m}{k} \left\{ n^{-2k} \sum_{a_1+\dots+a_n=k} \binom{k}{a_1, \dots, a_n}^2 \right\}. \quad (3)$$

**Proof:** We first exploit the binomial theorem to show that

$$W_n(s) = n^s \sum_{m \ge 0} (-1)^m \binom{s/2}{m} n^{-2m} \int_{[0,1]^n} \left( 4 \sum_{1 \le i < j \le n} \sin^2(\pi(x_j - x_i)) \right)^m dx. \quad (4)$$

Next we evaluate the trigonometric integral in (4). To this end, we show that it is the constant term of

$$(n^2 - (x_1 + \dots + x_n)(1/x_1 + \dots + 1/x_n))^m.$$

The details appear in (BNSW09). Alternatively, one may start with the observation that $W_n(s)$ is the constant term of

$$((x_1 + \dots + x_n)(1/x_1 + \dots + 1/x_n))^{s/2} \quad (5)$$

which follows directly from the integral definition. □

From Theorem 2.1 and the fact that the binomial transform is an involution we additionally learn that the even moments are integer sequences as detailed by the following corollary.

**Corollary 2.2** For nonnegative integers $k$,

$$W_n(2k) = \sum_{a_1+\dots+a_n=k} \binom{k}{a_1, \dots, a_n}^2. \quad (6)$$

An outline of the genesis of these evaluations is also given in (BNSW09).
## 3 Further Combinatorial Features

In light of Corollary 2.2, we consider the combinatorial sums $f_n(k) := W_n(2k)$ of multinomial coefficients squared. These numbers also appear in (RS09) in the following way: $f_n(k)$ counts the number of abelian squares of length $2k$ over an alphabet with $n$ letters (that is strings $xx'$ of length $2k$ from an alphabet with $n$ letters such that $x'$ is a permutation of $x$). It is not hard to see that, (Bar64),

$$f_{n_1+n_2}(k) = \sum_{j=0}^{k} \binom{k}{j}^2 f_{n_1}(j) f_{n_2}(k-j), \qquad (7)$$

for two non-overlapping alphabets with $n_1$ and $n_2$ letters. In particular, we may use (7) to obtain $f_1(k) = 1$, $f_2(k) = \binom{2k}{k}$, as well as

$$f_3(k) = \sum_{j=0}^{k} \binom{k}{j}^2 \binom{2j}{j} = {}_3F_2 \left( \begin{array}{c} \frac{1}{2}, -k, -k \\ 1, 1 \end{array} \middle| 4 \right) = \binom{2k}{k} {}_3F_2 \left( \begin{array}{c} -k, -k, -k \\ 1, -k + \frac{1}{2} \end{array} \middle| \frac{1}{4} \right), \qquad (8)$$

$$f_4(k) = \sum_{j=0}^{k} \binom{k}{j}^2 \binom{2j}{j} \binom{2(k-j)}{k-j} = \binom{2k}{k} {}_4F_3 \left( \begin{array}{c} \frac{1}{2}, -k, -k, -k \\ 1, 1, -k + \frac{1}{2} \end{array} \middle| 1 \right). \qquad (9)$$

Here and below ${}_pF_q$ denotes the hypergeometric function.

The following result is established in (Bar64) with the recursions for $n \le 6$ given explicitly.

**Theorem 3.1** For fixed $n \ge 2$, the sequence $f_n(k)$ satisfies a recurrence of order $\lambda := \lfloor n/2 \rfloor$ with polynomial coefficients of degree $n-1$:

$$c_{n,0}(k)f_n(k) + \dots + c_{n,\lambda}(k)f_n(k+\lambda) = 0.$$

**Remark 3.2** For fixed $k$, the map $n \mapsto f_n(k)$ is a polynomial of degree $k$. This follows from

$$f_n(k) = \sum_{j=0}^{k} \binom{n}{j} \sum_{\substack{a_1+\dots+a_j=k \\ a_i>0}} \left( \begin{array}{c} k \\ a_1, \dots, a_j \end{array} \right)^2, \qquad (10)$$

because the right-hand side is a linear combination (with positive coefficients only depending on $k$) of the polynomials $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{k}$ of respective degrees $0, 1, \dots, k$. From (10) the coefficient of $\binom{n}{k}$ is seen to be $(k!)^2$. We therefore obtain the first-order approximation $W_n(s) \approx_n n^{s/2}\Gamma(s/2+1)$ for $n$ approaching infinity, see also (Klu1906). In particular, $W_n(1) \approx_n \sqrt{\pi n}/2$. Similarly, the coefficient of $\binom{n}{k-1}$ is $\frac{k-1}{4}(k!)^2$ which gives rise to the second-order approximation

$$(k!)^2 \binom{n}{k} + \frac{k-1}{4} (k!)^2 \binom{n}{k-1} = k!n^k - \frac{k(k-1)}{4} k!n^{k-1} + O(n^{k-2}).$$

of $f_n(k)$. We therefore obtain

$$W_n(s) \approx_n n^{s/2-1} \left\{ \left( n - \frac{1}{2} \right) \Gamma\left( \frac{s}{2} + 1 \right) + \Gamma\left( \frac{s}{2} + 2 \right) - \frac{1}{4} \Gamma\left( \frac{s}{2} + 3 \right) \right\},$$
which is exact for $s = 0, 2, 4$. In particular, $W_n(1) \approx_n \sqrt{\pi n}/2 + \sqrt{\pi/n}/32$. More general approximations are given in (Cra09). ◇

**Remark 3.3** It follows straight from (6) that, for primes $p$, $f_n(p) \equiv n$ modulo $p$. Further, for $k \ge 1$, $f_n(k) \equiv n$ modulo 2. This may be derived inductively from the recurrence (7) since, assuming that $f_n(k) \equiv n$ modulo 2 for some $n$ and all $k \ge 1$,

$$f_{n+1}(k) = \sum_{j=0}^{k} \binom{k}{j}^2 f_n(j) \equiv 1 + \sum_{j=1}^{k} \binom{k}{j} n = 1 + n(2^k - 1) \equiv n + 1 \pmod{2}.$$

Hence for odd primes $p$,

$$f_n(p) \equiv n \pmod{2p}. \qquad (11)$$

The congruence (11) also holds for $p = 2$ since $f_n(2) = (2n - 1)n$, compare (10). ◇

**Remark 3.4** The integers $f_3(k)$ (respectively $f_4(k)$), the first of which are given in Table 1, also arise in physics, see for instance (BBBG08), and are referred to as hexagonal (respectively diamond) lattice integers. The following formulae (BBBG08, (186)–(188)) relate these sequences in non-obvious ways:

$$\begin{aligned} \left( \sum_{k \ge 0} f_3(k) (-x)^k \right)^2 &= \sum_{k \ge 0} f_2(k)^3 \frac{x^{3k}}{((1+x)^3(1+9x))^{k+\frac{1}{2}}} \\ &= \sum_{k \ge 0} f_2(k) f_3(k) \frac{(-x(1+x)(1+9x))^k}{((1-3x)(1+3x))^{2k+1}} \\ &= \sum_{k \ge 0} f_4(k) \frac{x^k}{((1+x)(1+9x))^{k+1}}. \end{aligned}$$

It would be instructive to similarly engage $f_5(k)$. ◇

# 4 Analytic and Numerical Results

We start with investigating the analyticity of $W_n(s)$ for a given $n$. In (BNSW09), we show that $W_n(s)$, as defined in (1), is analytic at least for $Re s > 0$. It is then shown (based on the results of Section 4.2) that (1) is indeed finite and analytic for $Re s > -2$ for each $n \ge 3$ (compare Figure 2).

## 4.1 Small number of steps

The case $n = 1$ is trivial: it follows straight from the integral definition (1) that $W_1(s) = 1$.

In the case $n = 2$, direct integration of (18) with $n = 2$ yields

$$W_2(s) = 2^{s+1} \int_0^{1/2} \cos(\pi t)^s dt = \binom{s}{s/2}, \qquad (12)$$
which may also be obtained using (3).

For $n = 3$, based on (8) we define

$$V_3(s) := {}_3F_2\left(\begin{array}{c} \frac{1}{2}, -\frac{s}{2}, -\frac{s}{2} \\ 1, 1 \end{array}\middle|4\right), \qquad (13)$$

so that by Corollary 2.2 and (8), $W_3(2k) = V_3(2k)$ for nonnegative integers $k$. This led us to explore $V_3(s)$ more generally numerically and so to conjecture the following which we prove in the penultimate section:

**Theorem 4.1** For nonnegative even integers and all odd integers $k$:

$$W_3(k) = \operatorname{Re} V_3(k). \qquad (14)$$

From here, we derive the following equivalent expressions for $W_3(1)$:

$$\begin{align*} W_3(1) &= \frac{4\sqrt{3}}{3} \left( {}_3F_2\left(-\frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}; \frac{1}{4} - \frac{1}{\pi}; \frac{\sqrt{3}}{24}\right) + \frac{\sqrt{3}}{24} {}_3F_2\left(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}; \frac{1}{4}\right) \right) \\ &= 2\sqrt{3} \frac{K^2(k_3)}{\pi^2} + \sqrt{3} \frac{1}{K^2(k_3)} \\ &= \frac{3}{16} \frac{2^{1/3}}{\pi^4} \Gamma^6\left(\frac{1}{3}\right) + \frac{27}{4} \frac{2^{2/3}}{\pi^4} \Gamma^6\left(\frac{2}{3}\right). \end{align*}$$

These rely on using Legendre's identity and several Clausen-like product formulae, plus Legendre's evaluation of $K(k_3)$ where $k_3 := \frac{\sqrt{3}-1}{2\sqrt{2}}$ is the third singular value as in (BB87). Similar expressions can be given for $W_3$ evaluated at any odd integer.

## 4.2 Carlson's Theorem

We may lift the recursive structure of $f_n$, defined in Section 3, to $W_n$ to a fair degree on appealing to Carlson's theorem (Tit39, 5.81):

**Theorem 4.2 (Carlson)** Let $f$ be analytic in the right half-plane $\operatorname{Re} z \ge 0$ and of exponential type (meaning that $|f(z)| \le Me^{c|z|}$ for some $M$ and $c$), with the additional requirement that

$$|f(z)| \le Me^{d|z|}$$

for some $d < \pi$ on the imaginary axis $\operatorname{Re} z = 0$. If $f(k) = 0$ for $k = 0, 1, 2, \dots$ then $f(z) = 0$ identically.

By verifying that Carlson's theorem applies, we get:

**Theorem 4.3** Given that $f_n(k)$ satisfies a recurrence

$$c_{n,0}(k)f_n(k) + \dots + c_{n,\lambda}(k)f_n(k+\lambda) = 0$$

with polynomial coefficients $c_{n,j}(k)$ (see Theorem 3.1) then $W_n(s)$ satisfies the corresponding functional equation

$$c_{n,0}(s/2)W_n(s) + \dots + c_{n,\lambda}(s/2)W_n(s + 2\lambda) = 0,$$

for $\operatorname{Re} s \ge 0$.
**Example 4.4** For $n = 2, 3, 4$ we find

$$(s + 2)W_2(s + 2) - 4(s + 1)W_2(s) = 0,$$

$$(s + 4)^2 W_3(s + 4) - 2(5s^2 + 30s + 46)W_3(s + 2) + 9(s + 2)^2 W_3(s) = 0,$$

$$(s + 4)^3 W_4(s + 4) - 4(s + 3)(5s^2 + 30s + 48)W_4(s + 2) + 64(s + 2)^3 W_4(s) = 0.$$

Note that for all complex $s$, the function $V_3(s)$ defined in (13) also satisfies the recursion given above for $W_3(s)$—as is routine to prove symbolically. $\diamond$

We note that in each case the recursion lets us determine significant information about the nature and position of any poles of $W_n$. Details appear in (BNSW09). In particular, for $n \ge 3$, the recursion guaranteed by Theorem 4.3 provides an analytic continuation of $W_n$ to all of the complex plane with poles at certain negative integers. Here, we confine ourselves to show the continuations of $W_3, W_4, W_5$, and $W_6$ on the negative real axis in Figure 2. These illustrate the fact that, e.g., $W_3$ and $W_5$ have simple poles at $-2, -4, -6, \dots$ whereas $W_4$ has double poles at these integers. It is further shown in (BNSW09) that, for instance, $\text{Res}_{-2}(W_3) = \frac{2}{\sqrt{3\pi}}$.

Our next somewhat audacious conjecture is (it is now much less audacious as David Broadhurst (Bro09) using a new expression for $W_n$, namely (20), has been able to verify the statement for $n = 2, 3, 4, 5$ and odd $s < 50$ to a precision of 50 digits):

**Conjecture 4.5** For positive integers $n$ and complex $s$,

$$W_{2n}(s) \stackrel{?}{=} \sum_{j \ge 0} \binom{s/2}{j}^2 W_{2n-1}(s-2j). \qquad (15)$$

It is understood that the right-hand side of (15) refers to the analytic continuation of $W_n$. By (7) Conjecture 4.5 clearly holds for $s$ an even positive integer. Further, it follows from (12) that the conjecture holds for $n = 1$.

Recall that the real part of $V_3(k)$ as defined in (13) gives $W_3(k)$ for nonnegative integers $k$. Define

$$V_4(s) := \sum_{j \ge 0} \binom{s/2}{j}^2 V_3(s - 2j) = \sum_{j \ge 0} \binom{s/2}{j}^2 {}_3F_2 \left( \begin{matrix} \frac{1}{2}, -\frac{s}{2} + j, -\frac{s}{2} + j \\ 1, 1 \end{matrix} \middle| 4 \right) \qquad (16)$$

This combines with the much better substantiated special case $n = 2$ of Conjecture 4.5 to provide:

**Conjecture 4.6** For all integers $k$,

$$W_4(k) \stackrel{?}{=} \text{Re} V_4(k). \qquad (17)$$

## 4.3 Numerical Evaluations

Note that the following one-dimensional reduction of the integral may be achieved by taking periodicity into account.

$$W_n(s) = \int_{[0,1]^{n-1}} \left| 1 + \sum_{k=1}^{n-1} e^{2\pi x_k i} \right|^s d(x_1, \dots, x_{n-1}). \qquad (18)$$
n = 3 Using this reduction, David Bailey (running tanh-sinh integration on a 256-core LBNL system for roughly 15 minutes) has confirmed that the first 175 digits of $W_3(1)$ are given by

$$W_3(1) \approx \begin{aligned} & 1.5745972375518936574946921830765196902216661807585191701936930983 \\ & 018311805944543821310853133622419530649842236115540882056173012611 \\ & 081031331499438143442975115786527521008424458. \end{aligned}$$

This agreed with the evaluation $W_3(1) = \text{Re } V_3(1)$ originally conjectured in (14). He has also confirmed 175 digits for $W_3(s) = \text{Re } V_3(s)$ for $s = 2, \dots, 7$.

n = 4 Using Conjecture 4.6 we provide the approximation

$$W_4(1) \approx \begin{aligned} & 1.7990924798428510335326028458461089100662820032916204566266417735 \\ & 988542669321205752411619305734748280560170144445179836872885. \end{aligned}$$

It is worthwhile observing that this level of approximation is made possible by the fact that, roughly, one correct digit is added by each term of the sum.

# 5 More Probability

As noted such problems have a long lineage. For example, in response to the question posed by Pearson in *Nature*, Kluyver (Klu1906) makes a lovely analysis of the cumulative distribution function of the distance traveled by a “rambler” in the plane for various step lengths. In particular, for our uniform walk Kluyver provides the Bessel representation

$$P_n(t) = t \int_0^\infty J_1(xt) J_0^n(x) \, dx. \qquad (19)$$

Thus, $W_n(s) = \int_0^n t^s p_n(t) dt$, where $p_n = P'_n$. From here, David Broadhurst (Bro09) obtains

$$W_n(s) = 2^{s+1-k} \frac{\Gamma(1+\frac{s}{2})}{\Gamma(k-\frac{s}{2})} \int_0^\infty x^{2k-s-1} \left(-\frac{1}{x}\frac{d}{dx}\right)^k J_0^n(x) \, dx \qquad (20)$$

for real $s$ with $2k > s > \max(-2, -\frac{n}{2})$. (20) enables Broadhurst (Bro09) to verify Conjecture 4.5 for $n = 2, 3, 4, 5$ and odd $s < 50$ to a precision of 50 digits.

**Remark 5.1** For $n = 3, 4$, symbolic integration in *Mathematica* of (20) leads to interesting analytic continuations (Cra09) such as

$$W_3(s) = \frac{1}{2^{2s+1}} \tan\left(\frac{\pi s}{2}\right) \left(\frac{s}{\frac{s-1}{2}}\right)^3 {}_3F_2\left(\frac{1}{2}, \frac{1}{2}, \frac{1}{2} \middle| \frac{1}{4}\right) + \left(\frac{s}{\frac{s}{2}}\right) {}_3F_2\left(\frac{-s}{2}, \frac{-s}{2}, \frac{-s}{2} \middle| \frac{1}{4}\right), \quad (21)$$

and

$$W_4(s) = \frac{1}{2^{2s}} \tan\left(\frac{\pi s}{2}\right) \left(\frac{s}{\frac{s-1}{2}}\right)^3 {}_4F_3\left(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{s}{2}+1 \middle| 1\right) + \left(\frac{s}{\frac{s}{2}}\right) {}_4F_3\left(\frac{1}{2}, \frac{-s}{2}, \frac{-s}{2}, \frac{-s}{2} \middle| 1\right). \quad (22)$$

We note that for $s$ a positive even integer the first term in (21) (resp. (22)) is zero and the second is a term also appearing in (8) (resp. (9)). ◇
Herein, we will take a related probabilistic approach so as to be able to express our quantities of interest in terms of special functions which allows us to explicitly resolve $W_3(2k + 1)$ for all odd values.

It is elementary to express the distance $y$ of an $(n + 1)$-step walk conditioned on a given distance $x$ of an $n$-step walk. Since, by a simple application of the cosine rule we find

$$y^2 = x^2 + 1 + 2x \cos(\theta), \qquad (23)$$

where $\theta$ is the outside angle of the triangle with sides $x$, $1$, $y$. It follows, for details see (BNSW09), that the conditional density for the distance $y$ of an $(n + 1)$-step walk as an extension of an $n$-step walk with distance $x$ is

$$h_x(y) = \frac{2y}{\pi\sqrt{4x^2 - (y^2 - x^2 - 1)^2}} \qquad (24)$$

which, of course, is independent of $n$.

We therefore have the following trivial evaluation

$$W_{n+1}(s) = \mathbb{E}(y^s) = \mathbb{E}(\mathbb{E}(y^s | x)) = \int_0^n \left( \int_{|x-1|}^{x+1} y^s h_x(y) dy \right) p_n(x) dx, \qquad (25)$$

under the assumption that the probability density $p_n$ for the $n$-step walk is known. Clearly, for the 1-step walk we have $p_1(x) = \delta_1(x)$, a Dirac delta at $x = 1$. It then follows immediately that the probability density for a 2-step walk is given by $p_2(x) = \frac{2}{\pi\sqrt{4-x^2}}$ for $0 \le x \le 1$ and $0$ otherwise.

## 5.1 Applications to $W_3$

The explicit form of $p_2(x)$ leads to some alternative probabilistically inspired expressions for $W_3(s)$. The inner integral in (25) is in fact expressible in terms of the hypergeometric function with details appearing in (BNSW09). For instance, in the case $s = 1$ we find

$$\int_{|x-1|}^{x+1} y h_x(y) dy = \frac{2(x+1)}{\pi} E\left(\frac{2\sqrt{x}}{x+1}\right), \qquad (26)$$

(for $x > 0$ and $x \ne 1$) where $E(k) = \frac{\pi}{2} F_1(\frac{1}{2}, -\frac{1}{2}; 1; k^2)$ denotes the complete elliptic integral of the second kind with parameter $k$. This leads to the following expression for the 3-step walk:

$$W_3(1) = \int_0^2 \frac{4(x+1)}{\pi^2 \sqrt{4-x^2}} E\left(\frac{2\sqrt{x}}{x+1}\right) dx. \qquad (27)$$

We are now in a position to prove Theorem 4.1.

**Proof of Theorem 4.1:** It remains to prove the result for odd integers. Since, as noted, for all complex $s$, the function $V_3(s)$ defined in (13) also satisfies the recursion given for $W_3(s)$ in Example 4.4, it suffices to show that the values given for $s = 1$ and $s = -1$ are correct. First, (BB87, Exercise 1c), p. 16) allows us to write

$$(x+1) E\left(2 \frac{\sqrt{x}}{x+1}\right) = \mathrm{Re}\left(2 E(x) - (1-x^2) K(x)\right)$$
for $0 < x < \infty$ where we have used Jacobi's imaginary transformations (BB87, Exercises 7a) & 8b), p. 73) to introduce the real part for $x > 1$. Thus, from (27),

$$ 
\begin{aligned}
W_3(1) &= \frac{4}{\pi^2} \operatorname{Re} \int_0^{\pi/2} \left( 2E(2\sin(t)) - (1 - 4\sin^2(t))K(2\sin(t)) \right) dt \\
&= \frac{4}{\pi^2} \operatorname{Re} \int_0^{\pi/2} \int_0^{\pi/2} 2\sqrt{1 - 4\sin^2(t)\sin^2(r)} dt dr \\
&\quad - \frac{4}{\pi^2} \operatorname{Re} \int_0^{\pi/2} \int_0^{\pi/2} \frac{1 - 4\sin^2(t)}{\sqrt{1 - 4\sin^2(t)\sin^2(r)}} dt dr.
\end{aligned}
$$

Joining up the two last integrals and parameterizing, we consider

$$ Q(a) := \frac{4}{\pi^2} \int_0^{\pi/2} \int_0^{\pi/2} \frac{1 + a^2 \sin^2(t) - 2a^2 \sin^2(t) \sin^2(r)}{\sqrt{1 - a^2 \sin^2(t) \sin^2(r)}} dt dr. \quad (28) $$

We now use the binomial theorem to integrate (28) term-by-term for $|a| < 1$ and substitute

$$ \frac{2}{\pi} \int_{0}^{\pi/2} \sin^{2m}(t) dt = (-1)^m \binom{-1/2}{m} $$

throughout. Moreover, $(-1)^m \binom{-\alpha}{m} = (\alpha)_m/m!$ where the later denoted the Pochhammer symbol. Evaluation of the consequent infinite sum produces:

$$ 
\begin{aligned}
Q(a) &= \sum_{k \ge 0} (-1)^k \binom{-1/2}{k} \left( a^{2k} \binom{-1/2}{k}^2 - a^{2k+2} \binom{-1/2}{k} \binom{-1/2}{k+1} - 2a^{2k+2} \binom{-1/2}{k+1}^2 \right) \\
&= \sum_{k \ge 0} (-1)^k a^{2k} \binom{-1/2}{k}^3 \frac{1}{(1-2k)^2} \\
&= {}_3F_2 \left( \begin{matrix} -\frac{1}{2}, -\frac{1}{2}, \frac{1}{2} \\ 1, 1 \end{matrix} \middle| a^2 \right).
\end{aligned}
$$

Analytic continuation to $a = 2$ yields the claimed result as per formula (13) for $s = 1$. The case $s = -1$ is similar, see (BNSW09). □

# 6 Conclusion

The behaviour of these two-dimensional walks provides a fascinating blend of probabilistic, analytic, algebraic and combinatorial challenges. Work on understanding Conjectures 4.5 and 4.6 is in progress.

**Acknowledgements** We are grateful to David Bailey for his substantial computational help, to Richard Crandall for helpful suggestions, to Bruno Salvy for reminding us of the existence of (Bar64), Michael Mossinghoff for showing us (Klu1906), and to Peter Donovan for stimulating this research and for much subsequent useful discussion.
References

[BBBG08] D. H. Bailey, J. M. Borwein, D. J. Broadhurst, and M. L. Glasser. "Elliptic integral evaluations of Bessel moments and applications." *J. Phys. A: Math. Theor.*, **41** (2008), 5203-5231.

[Bar64] P. Barrucand. "Sur la somme des puissances des coefficients multinomiaux et les puissances successives d'une fonction de Bessel." *Comptes rendus hebdomadaires des séances de l'Académie des sciences*, **258** (1964), 5318-5320.

[BB87] J. M. Borwein and P. B. Borwein. *Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity*. Wiley, 1987.

[BNSW09] J. M. Borwein, D. Nuyens, A. Straub, and J. Wan. "Random walk integrals." Preprint, October 2009.

[Bro09] D. J. Broadhurst. "Bessel moments, random walks and Calabi-Yau equations." Preprint, November 2009.

[Cra09] R. E. Crandall, "Analytic representations for random walk moments," Preprint, September 2009.

[Don09] P. Donovan. "The flaw in the JN-25 series of ciphers, II." *Cryptologia*, (2010), in press.

[Klu1906] I. C. Kluyver. "A local probability problem." *Nederl. Acad. Wetensch. Proc.*, **8** (1906), 341-350.

[Pea1905] K. Pearson. "The random walk." *Nature*, **72** (1905), 294.

[Pea1905b] K. Pearson. "The problem of the random walk." *Nature*, **72** (1905), 342.

[Ray1905] Lord Rayleigh. "The problem of the random walk." *Nature*, **72** (1905), 318.

[RS09] L. B. Richmond and J. Shallit. "Counting abelian squares." *The Electronic Journal of Combinatorics*, **16**, 2009.

[Slo09] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, 2009. Published electronically at http://www.research.att.com/sequences.

[Tit39] E. Titchmarsh. *The Theory of Functions*. Oxford University Press, 2nd edition, 1939.