2
$\begingroup$

MOTIVATION

I think that computing the asymptotics of $F(x)$ in this answer would give a solution for this question.

QUESTION

For $n \ge 0$, let $u_{2n} = \binom{2n}{n}^2 / 4^{2n}$ and $u_{2n+1} = 0$. Let $U(x) = \sum_{m=0}^{\infty} u_mx^m$ be the generating function for $u_m$. Let $f_m$ be another sequence such that its generating function $F(x) = \sum_{m=0}^{\infty} f_mx^m$ can be expressed as $F(x) = 1-1/U(x)$.

We have that asymptotically $u_{2n} \approx 1/(\pi n)$.

Can we compute an asymptotic approximation for $f_{2n}$?

$\endgroup$
5
  • 3
    $\begingroup$ $f_{2n} \sim \frac{\pi }{{n\log ^2 n}}$, see A054474. $\endgroup$ Commented Aug 18 at 2:21
  • $\begingroup$ @Gary thank you, although the asymptotics seems more complicated there than what you wrote here. Also, $f_{2n}$ counts walks in the whole plane, while OEIS A054474 considers only one quadrant. $\endgroup$ Commented Aug 18 at 6:30
  • 2
    $\begingroup$ $A054474/16^n$ seems to give your $f_{2n}$. $\endgroup$ Commented Aug 18 at 9:55
  • 1
    $\begingroup$ It is not difficult to prove that $f_{2n}$ behaves like $\frac{1}{n\log^2(n)}$, by using Karamata's Tauberian theorem. I'll try to write down details if needed. $\endgroup$ Commented Aug 18 at 10:28
  • $\begingroup$ The sequence is described as "Number of walks on square lattice that start and end at origin after 2n steps, not touching origin at intermediate stages. " Moreover, I gave as an answer a proof that the asymptotics Gary provided hold in the much more general setting of symmetric random walks with finite exponential moments $\endgroup$ Commented Aug 18 at 16:43

3 Answers 3

2
$\begingroup$

For any symmetric random walk with exponential moments on $\mathbb Z^2$, one has $$f_{2n}\sim C\frac{1}{n\log^2(n)}.$$ Indeed, one has the following local limit theorem : $p_{2n}(e,e)\sim C_0 n^{-1}$ (this is standard, see for instance Theorem~13.12 in Woess' book Random walk on infinite graphs and groups). This shows that the Green function (which you denote by $U$, but I will denote by $G$, which is more standard) satisfies the following : $$G(r)=\sum_{n\geq 0}p_n(e,e)r^n\sim -C_1\log (1-r).$$

Next, write $T=\min(n,X_n=e)$, that is $T$ is the first return time to the origin. Consider also the first return probability in time $n$ to $e$,i.e. $f_n=\mathbb P(T=n)$. Finally, consider the first return Green function $F(r)$ defined by $F(r)=\sum_{n\geq 0}f_nr^n$. Then, this function satisfies $$G(r)=\frac{1}{1-F(r)}.$$ This is the function you defined implicitly. For all this, see for instance Lemma 1.13 in the aforementioned book by Woess.

Note that by differentiating this expression, one gets $$F'(r)=\frac{G'(r)}{G(r)^2}.$$ Now, the function $G'$ has the following asymptotic behavior (still because of the above local limit theorem) : $$G'(r)\sim C_2\frac{1}{1-r}.$$ Therefore, $$F'(r)\sim C_3\frac{1}{(1-r)\log^2(1-r)}.$$ We can now use a Tauberian theorem to get $$(2n)f_{2n}\sim C_4 \frac{1}{\log^2(n)},$$ hence $$f_{2n}\sim C_5\frac{1}{n\log ^2(n)}.$$

$\endgroup$
3
  • $\begingroup$ Your answer doesn't seem correct to me since $f_{2n}\sim C_6\frac{1}{n \log(n)}$ appears to be a much better approximation as $n\to\infty$. $\endgroup$ Commented Aug 18 at 16:53
  • $\begingroup$ @StevenClark How so ? Anyway, OEIS A054474 shows that for the simple random walk, one has indeed $\frac{\pi}{n\log ^2(n)}$. $\endgroup$ Commented Aug 18 at 17:03
  • $\begingroup$ $f_{2n} n \log(n)$ seems to be more constant than $f_{2n} n \log^2(n)$ as $n$ increases which I illustrated in my updated answer. $\endgroup$ Commented Aug 18 at 17:40
1
$\begingroup$

We can write $$ - \frac{1}{K(x)} = -\frac{2}{\pi} + \sum_{n=1}^{\infty} \frac{2}{\pi} f_{2n} \, x^n, $$ where $K(x)$ is the complete elliptic integral of the first kind. From the behaviour of $K(x)$ as $x \to 1^-$, we can infer that $$ - \frac{1}{K(x)} = \sum_{k=1}^{\infty} \frac{2^{2k-1} \log^{k-1} 2}{\log^k(1-x)} \left( 1 + \mathcal{O}_k(1-x) \right), $$ as $x \to 1^-$. This implies \begin{align*} \frac{2}{\pi} f_{2n} &= \left[ x^n \right] \sum_{k=1}^{N} \frac{2^{2k-1} \log^{k-1} 2}{\log^k(1-x)} + \mathcal{O}\!\left( \frac{1}{n \log^{N+2} n} \right) + \mathcal{O}\!\left( \frac{1}{n^2 \log^2 n} \right) \\ &= \sum_{k=1}^{N} 2^{2k-1} \log^{k-1} 2 \, \frac{(-1)^n B_{n+k}^{(n+1)}(1)}{(n+k)!} + \mathcal{O}\!\left( \frac{1}{n \log^{N+2} n} \right) + \mathcal{O}\!\left( \frac{1}{n^2 \log^2 n} \right), \end{align*} for any fixed $N \ge 0$ as $n \to +\infty$. Here, $B_n^{(\alpha)}(x)$ denotes the generalised Bernoulli polynomials. By a result of Nörlund, we have \begin{align*} \frac{(-1)^n B_{n+k}^{(n+1)}(1)}{(n+k)!} &= \frac{(-1)^k}{(n+k) \log^k (n+k)} \sum_{m=1}^{M} \binom{m+k-1}{m} \left[ \frac{\mathrm{d}^m}{\mathrm{d}t^m} \frac{1}{\Gamma(t)} \right]_{t=0} \frac{(-1)^m}{\log^m(n+k)} \\ &\quad + \mathcal{O}\!\left( \frac{1}{n \log^{M+k+1} n} \right) \\ &= \frac{(-1)^k}{n \log^k n} \sum_{m=1}^{M} \binom{m+k-1}{m} \left[ \frac{\mathrm{d}^m}{\mathrm{d}t^m} \frac{1}{\Gamma(t)} \right]_{t=0} \frac{(-1)^m}{\log^m n} \\ &\quad + \mathcal{O}\!\left( \frac{1}{n \log^{M+k+1} n} \right) + \mathcal{O}\!\left( \frac{1}{n^2 \log^{k+1} n} \right), \end{align*} for any fixed $k \ge 1$, $M \ge 0$ as $n \to +\infty$. Accordingly, $$\boxed{ f_{2n} = \frac{\pi}{n \log^2 n} \left( \sum_{k=0}^{N-1} \frac{c_k}{\log^k n} + \mathcal{O}\!\left( \frac{1}{\log^N n} \right) \right) + \mathcal{O}\!\left( \frac{1}{n^2 \log^2 n} \right),} $$ for any fixed $N \ge 0$ as $n \to +\infty$, where $$ \boxed{c_k = (-1)^k\sum_{m=0}^{k} 2^{2m} \log^m 2 \, \binom{k+1}{m} \left[ \frac{\mathrm{d}^{k-m+1}}{\mathrm{d}t^{k-m+1}} \frac{1}{\Gamma(t)} \right]_{t=0}.} $$ The first three coefficients are \begin{align*} c_0 &= 1, \\ c_1 &= -2 \gamma - 8 \log 2, \\ c_2 &= 3 \gamma^2 + 24 \gamma \log 2 + 48 \log^2 2 - \frac{\pi^2}{2}, \end{align*} in agreement with those given at $\text{A}054474$.

$\endgroup$
0
$\begingroup$

This may not be a complete answer but perhaps provides some insight.


Noting that

$$U(x)=\sum_{n=0}^{\infty} u_{2 n}\, x^{2 n}=\sum_{n=0}^{\infty} \frac{\binom{2 n}{n}^2}{4^{2 n}}\, x^{2 n}=\frac{2 K\left(x^2\right)}{\pi}\,,\quad |x|<1\tag{1}$$

where $K(x)$ is the complete elliptic integral of the first kind leads to

$$F(x)=1-\frac{1}{U(x)}=1-\frac{\pi}{2\, K\left(x^2\right)}=\sum_{n=0}^{\infty} f_{2 n}\, x^{2 n}\,,\quad |x|<1\tag{2}.$$


The following table illustrates several values of $f_{2 n}$. I believe $16^n f_{2 n}$ is an integer but I was not able to find any related OEIS entries.

$$\begin{array}{ccc} n & f(2 n) & \log _2(\text{Denominator}[f(2 n)]) \\ 0 & 0 & 0 \\ 1 & \frac{1}{4} & 2 \\ 2 & \frac{5}{64} & 6 \\ 3 & \frac{11}{256} & 8 \\ 4 & \frac{469}{16384} & 14 \\ 5 & \frac{1379}{65536} & 16 \\ 6 & \frac{17223}{1048576} & 20 \\ 7 & \frac{56001}{4194304} & 22 \\ 8 & \frac{11998869}{1073741824} & 30 \\ 9 & \frac{41064827}{4294967296} & 32 \\ 10 & \frac{571915951}{68719476736} & 36 \\ 11 & \frac{2018982161}{274877906944} & 38 \\ 12 & \frac{115338112823}{17592186044416} & 44 \\ 13 & \frac{415720532641}{70368744177664} & 46 \\ 14 & \frac{6041874952949}{1125899906842624} & 50 \\ 15 & \frac{22103950817043}{4503599627370496} & 52 \\ 16 & \frac{20825721430968213}{4611686018427387904} & 62 \\ 17 & \frac{77047750289886219}{18446744073709551616} & 64 \\ 18 & \frac{1145470055108455527}{295147905179352825856} & 68 \\ 19 & \frac{4274935497276922857}{1180591620717411303424} & 70 \\ 20 & \frac{256206642255178772127}{75557863725914323419136} & 76 \\ \end{array}$$


Figure (1) below illustrates a discrete plot of $f_{2 n}$ in blue and $\frac{1}{2 \pi n}$ in orange. I don't believe $f_{2 n}\approx\frac{1}{2 \pi n}$ is as good of an approximation as $u_{2 n}\approx\frac{1}{\pi n}$, so it could probably stand some improvement.

discrete plot of f_{2 n} in blue and 1/(2 \pi n) in orange

Figure (1): Illustration of $f_{2 n}$ in blue and $\frac{1}{2 \pi n}$ in orange


This other answer gives the approximation $f_{2n}\approx C_5 \frac{1}{n \log^2(n)}$ which is consistent with the dominant term in the more complicated approximation

$$a(n)\approx \frac{\pi\, 16^n}{n} \left(\frac{1}{\log^2(n)}-\frac{2 \gamma +8 \log(2)}{\log^3(n)}+\frac{3 \gamma^2-\frac{\pi ^2}{2}+48 \log^2(2)+24 \gamma \log(2)}{\log^4(n)}\right)\tag{3}$$

given by OEIS Entry A054474 which implies $f_{2 n}=\frac{A054474(n)}{16^n}\approx \frac{a_n}{16^n}$ for $n>0$.


Figure (2) below illustrates $f_{2n}\approx C_6 \frac{1}{n \log(n)}$ appears to be a better approximation than $f_{2n}\approx C_5 \frac{1}{n \log^2(n)}$ or $f_{2 n}\approx \frac{a_n}{16^n}$ for small values of $n$ since $f_{2 n} \cdot \left(n \log^2(n)\right)$ illustrated in blue and $f_{2 n} \cdot \frac{16^n}{a_n}$ illustrated in orange both seem to exhibit growth as $n$ increases whereas $f_{2 n} \cdot (n \log(n))$ illustrated in green seems to be relatively constant.


Illustration of f_{2 n x (n \log^2(n)) in blue and f_{2 n} x (n \log(n)) in orange

Figure (2): Illustration of $f_{2 n} \cdot \left(n \log^2(n)\right)$ in blue, $f_{2 n} \cdot \frac{16^n}{a_n}$ in orange, and $f_{2 n} \cdot (n \log(n))$ in green


But perhaps Figure (2) above is misleading since if OEIS Entry A054474 is correct $f_{2n}\approx C_5 \frac{1}{n \log^2(n)}$ and $f_{2 n}\approx \frac{a_n}{16^n}$ must become better estimates than $f_{2n}\approx C_6 \frac{1}{n \log(n)}$ as $n\to\infty$.

$\endgroup$
6
  • $\begingroup$ As Gary already explaind in comments, the asymptotics are of order of magnitude $\frac{1}{n\log^2(n)}$, not $\frac{1}{n}$ as you seem to suggest $\endgroup$ Commented Aug 18 at 16:44
  • $\begingroup$ @M.Dus I said in my answer I thought the estimate $\frac{1}{2 \pi n}$ could be improved upon, but I believe $f_{2n}\sim C_6 \frac{1}{n \log(n)}$ is a better estimate than $f_{2n}\sim C_5 \frac{1}{n \log^2(n)}$ which I illustrated in my updated answer. $\endgroup$ Commented Aug 18 at 17:39
  • 2
    $\begingroup$ @StevenClark I think the apparent better approximation of $1/(n\log{n})$ is due to $n$ being small and a scaling effect. See this numeric test for $10000 \le n \le 20000$ where the blue trace is $f_{2n}n\log^2{n}$ while the green trace is $10f_{2n}n\log{n}$. $\endgroup$ Commented Aug 19 at 7:49
  • $\begingroup$ @FabiusWiesner You might be right, but the numeric test results seem to indicate neither approximation is particularly accurate in the expanded range $10000 \le n \le 20000$. $\endgroup$ Commented Aug 19 at 21:03
  • $\begingroup$ @StevenClark, that is true. I think that we need an $n$ much bigger than $20000$ in order for the $1/\log^3{n}$ and $1/\log^4{n}$ components of the OEIS formula to become negligible. $\endgroup$ Commented Aug 20 at 5:56

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.