3
$\begingroup$

Can we solve the following recurrence relation: $$a_{m,n} = 1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}$$ with $a_{0,n}=a_{m,0}=0$? If not, can we get an estimate of the growth of $a_{m,n}?$

I encountered this question when analyzing a 2D random walk on $R_+^2$ with boundaries at $x = m$ and $y = n$.

$\endgroup$
5
$\begingroup$

Inspired by Robert Israel's answer: Consider the generating function of the double-indexed array $(a_{m,n})$: \begin{multline*} P(s,t):=\sum_{m,n\ge0}a_{m,n}s^m t^n=\sum_{m,n\ge1}a_{m,n}s^m t^n \\ =\sum_{m,n\ge1}\Big(1 + \frac{a_{m,n-1}+a_{m-1,n}}{2}\Big)s^m t^n =\frac{st}{(1-s)(1-t)}+\frac{s+t}2\,P(s,t), \end{multline*} whence \begin{align*} P(s,t)&=\frac{st}{(1-s)(1-t)}\frac1{1-\frac{s+t}2} \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac{s+t}2\Big)^k \\ &=\sum_{m,n\ge1}s^mt^n\sum_{k\ge0}\Big(\frac12\Big)^k \sum_{j=0}^k\binom kj s^j t^{k-j}\\ &=\sum_{p,q\ge1}s^pt^q\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \end{align*} for $s,t$ in $(-1,1)$, so that \begin{equation*} a_{p,q}=\sum_{j=0}^{p-1}\sum_{k=j}^{q-1+j}\Big(\frac12\Big)^k \binom kj \tag{0} \end{equation*} for natural $p,q$.


Added: As an illustration of the use of formula (0), let us obtain the asymptotics of $a_{p,q}$ as $p,q\to\infty$. To do that, it is convenient to use the central limit theorem (CLT) of probability theory, applied here to the binomial distribution. Indeed, note that \begin{equation*} \Big(\frac12\Big)^k \binom kj=P(X_k=j), \end{equation*} where $X_k$ has the binomial distribution with parameters $k$ and $1/2$, so that, by the CLT, \begin{equation*} P(X_k\le x)\underset{k\to\infty}\longrightarrow\Phi(g_x(k)) \end{equation*} uniformly in all real $x$, where $\Phi$ is the standard normal cumulative distribution function and \begin{equation*} g_x(k):=\frac{x-k/2}{\sqrt{k/4}}=\frac{2x-k}{\sqrt k}=\frac{2x}{\sqrt k}-\sqrt k, \end{equation*} which is decreasing in $k$ for each $x\ge0$. Without loss of generality, \begin{equation*} p\ge q. \end{equation*} Interchanging the order of summation in (0), we have \begin{align*} a_{p,q}&:=\sum _{k=0}^{p+q-2} \sum _{j=\max (0,1+k-q)}^{\min (p-1,k)} P(X_k=j) \\ &=\sum _{k=0}^{p+q-2}P(\max (0,1+k-q)\le X_k\le\min (p-1,k)) \\ &=S_1+S_2+S_3=p+T_1-T_2, \tag{1} \end{align*} where \begin{align*} S_1&:=\sum _{k=0}^{q-1}P(0\le X_k\le k)=q, \\ S_2&:=\sum _{k=q}^{p-1}P(1+k-q\le X_k\le k) =p-q-\sum _{k=q}^{p-1}P(X_k\le k-q), \\ S_3&:=\sum _{k=p}^{p+q-2}P(1+k-q\le X_k\le p-1) \\ &=\sum _{k=p}^{p+q-2}[P(X_k\le p-1)-P(X_k\le k-q)], \\ T_1&:=\sum _{k=p}^{p+q-2}P(X_k\le p-1) =\sum _{k=p}^{p+q-2}\Phi(g_{p-1}(k))+o(q), \\ T_2&:=\sum _{k=q}^{p+q-2}P(X_k\le k-q)=\sum _{k=q}^{p+q-2}\Phi(g_{k-q}(k))+o(p) \\ &=p-1-U+o(p)=p-U+o(p), \quad U:=\sum _{k=q}^{p+q-2}\Phi(g_{q}(k)); \tag{2} \end{align*} here we used the identities $g_{k-q}(k)=-g_{q}(k)$ and $\Phi(-u)=1-\Phi(u)$.

Let now $A_p$ vary with $p$ so that $A_p\to\infty$, $A_p=o(\sqrt p)$, and \begin{equation*} k_p:=2p-A_p\sqrt{2p}\in\mathbb Z. \end{equation*} Then for integers $k$ in $[p,k_p]$ we have \begin{equation*} g_{p-1}(k)=g_p(k)+o(1),\quad g_p(k)= \frac{2p-k}{\sqrt k}\ge\frac{2p-k_p}{\sqrt k_p}\ge A_p\to\infty, \end{equation*} so that $\Phi(g_{p-1}(k))\to1$ uniformly in integers $k$ in $[p,k_p]$ and hence \begin{multline*} T_{11}:=\sum _{k=p}^{\min(p+q-2,k_p)}P(X_k\le p-1) =\sum _{k=p}^{\min(p+q-2,k_p)}\Phi(g_{p-1}(k))+o(q) \\ =\min(p+q-2,k_p)-(p-1)+o(q)+o(q)=q+o(p), \end{multline*} because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. Also, \begin{equation*} 0\le T_1-T_{11}=\sum _{k=1+\min(p+q-2,k_p)}^{p+q-2}P(X_k\le p-1) \le(p+q-2)-\min(p+q-2,k_p)=o(p), \end{equation*} again because $p\ge q$ and $A_p\sqrt{2p}=o(p)$. So, \begin{equation*} T_1=q+o(p). \tag{3} \end{equation*}

The term $U$ is estimated similarly to $T_1$. Write \begin{equation*} U=U_1+U_2+U_3, \end{equation*} where \begin{align*} U_1&:=\sum _{k=q}^{k_q}\Phi(g_{q}(k)), \\ U_2&:=\sum_{k=1+k_q}^{\min(l_q,p+q-2)}\Phi(g_{q}(k)), \\ U_3&:=\sum_{k=1+\min(l_q,p+q-2)}^{p+q-2}\Phi(g_{q}(k)), \end{align*} where \begin{equation*} l_q:=2q+A_q\sqrt{p+q}. \end{equation*} The term $U_1$ is estimated similarly to, and a bit more simply than, $T_{11}$, and we get \begin{equation*} U_1=q+o(q). \end{equation*} The term $U_2$ is estimated similarly to $T_1-T_{11}$, and we get \begin{equation*} U_2=o(q). \end{equation*} For integers $k$ in $[l_q,p+q]$ we have \begin{equation*} g_q(k)=\frac{2q-k}{\sqrt k}\le\frac{2q-l_q}{\sqrt k}=\frac{-A_q\sqrt{p+q}}{\sqrt k} \le-A_q\to-\infty, \end{equation*} so that $\Phi(g_q(k))\to0$ uniformly in integers $k$ in $[l_q,p+q]$ and hence \begin{equation*} U_3=o((p+q-2)-\min(l_q,p+q-2))=o(p). \end{equation*} So, \begin{equation*} U=q+o(p). \tag{4} \end{equation*} Collecting the pieces (1)--(4) together, we get \begin{equation*} a_{p,q}=p+T_1-T_2=p+T_1-p+U+o(p)=p+q-p+q+o(p)=2q+o(p), \end{equation*} under the assumption $p\ge q$. Without this assumption, \begin{equation*} a_{p,q}=2\min(p,q)+o(\max(p,q)) \end{equation*} as $p,q\to\infty$.

$\endgroup$
  • $\begingroup$ I'm more interested in the asymptotic behavior of $a_{m,n}$ if a closed form solution cannot be obtained. Is there a way to do that? $\endgroup$ – neverevernever Feb 11 at 17:40
  • $\begingroup$ I have added the asymptotics for large values of the indices. $\endgroup$ – Iosif Pinelis Feb 12 at 21:31
3
$\begingroup$

If $P_k(t) = \sum_{m=0}^k a_{m,k-n} t^m$ is the generating function of an ascending antidiagonal, we have

$$P_k(t) = \frac{t^k-t}{t-1} + \frac{1+t}{2} P_{k-1}(t), \ P_0(t) = 0 $$ and this can be solved:

$$ P_k(t) = \frac{2 t + 2t^{k+1} - 4 t ((t+1)/2)^k}{(t-1)^2}$$

$\endgroup$
2
$\begingroup$

Here are two observations. Both struck me as surprising at first and then not so surprising at all.

  • $a(m,n)$ is the expected number of flips of a fair coin until one gets either $m$ heads or $n$ tails.

  • Consider the recurrence relation $$b_{m,n}=b(m-1,n)+b(m,n-1)+2^{m+n-2}$$ with $b_{0,n}=b_{m,0}=0.$ Then $$a_{m,n}=\frac{b_{m,n}}{2^{m+n-2}}.$$


I suppose the first observation translates to the behavior of right/up walks in a rectangle. The second observation easily results from the recurrence for the $a_{m,n}.$

Here is a table of the first few values $b_{m,n}:$

$$\left[ \begin {array}{ccccccccc} 1&3&7&15&31&63&127&255&511 \\ 3&10&25&56&119&246&501&1012&2035 \\ 7&25&66&154&337&711&1468&2992&6051 \\ 15&56&154&372&837&1804&3784&7800&15899 \\ 31&119&337&837&1930&4246&9054&18902&38897 \\ 63&246&711&1804&4246&9516&20618&43616&90705 \\ 127&501&1468&3784&9054&20618&45332&97140&204229 \\ 255&1012&2992&7800&18902&43616&97140&210664& 447661\\ 511&2035&6051&15899&38897&90705&204229& 447661&960858\end {array} \right]$$

One observes (and then easily proves) that

  • The table reduced $\bmod 2$ is a Sierpinski triangle.
  • $b_{1,n}=1\cdot2^n-1.$
  • $b_{2,n}=2\cdot 2^{n+1}-(n+4).$
  • $b_{3,n}= 3\cdot 2^{n+2}-\frac{n^2+9n+24}2.$.
  • $b_{4,n}= 4\cdot 2^{n+3}-\frac{n^3+15n^2+86n+192}6.$
  • $b_{5,n}=5\cdot 2^{n+4}-\frac{n^4+22n^3+203n^2+950n+1920}{24}.$
$\endgroup$
1
$\begingroup$

By induction, it is immediate that $a_{m,n}\le 2\min(m,n)$. In addition, when $m$ is fixed and $n>m$ we have $a_{m,n}=2m-P_m(n)/2^n$, where $P_m(x)$ is a polynomial of degree $m$, so $2m$ is an exponentially good bound. For $m=n$, it seems that $a_{n,n}=2n(1-1/\sqrt{\pi n}+o(1/\sqrt{n}))$, but I have not taken the time to prove it.

Added: numerically $$a_{n,n}=2n(1-1/\sqrt{\pi n}+1/(8\sqrt{\pi n^3})-1/(128\sqrt{\pi n^5})+...)$$

Looks like a well-known expansion, probably in Knuth vol 1.

$\endgroup$
  • $\begingroup$ For m=n, do you have any intuition for the asymptotics? $\endgroup$ – neverevernever Feb 11 at 14:04
  • $\begingroup$ yes, see my addition $\endgroup$ – Henri Cohen Feb 11 at 14:28

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.