# limit of double binomial sum

Prove that

$$\lim_{\max(M,N) \to \infty} \frac{\sum_{i=0}^{M-1} \sum_{j=0}^{N-1} p^{i} (1-p)^{j} {i+j \choose i}}{\min (\frac{M}{p}, \frac{N}{1-p})} = 1$$

where $0<p<1$ and $M, N$ are positive integers.

I did it for the case that one of $M, N$ is fixed by using the differentiation of power series representation of $\frac{1}{1-p}$, but I have no idea about the remaining case - both of $M, N$ go to infinity.

My work - Proof for the special case where $N$ is finite:

The original problem becomes $$\lim_{M \to \infty} \sum_{i=0}^{M-1} \sum_{j=0}^{N-1} p^{i} (1-p)^{j} {i+j \choose i} = \frac{N}{1-p}.$$

To see this, for each $j$,

$$(1-p)^{j} \sum_{i=0}^{\infty} p^{i} {i+j \choose i} = (1-p)^{j} \frac{1}{j!} \frac{d^{j}}{dp^{j}} \big( \frac{1}{1-p} \big) = \frac{(1-p)^{j}}{(1-p)^{j+1}} = \frac{1}{1-p},$$

whence

$$\lim_{M \to \infty} \sum_{i=0}^{M-1} \sum_{j=0}^{N-1} p^{i} (1-p)^{j} {i+j \choose i} = N \cdot \frac{1}{1-p} = \frac{N}{1-p}.$$

• Still an interesting question worth to think about it! +1 – Markus Scheuer Nov 7 '14 at 8:35

Since this looks like a combinatorial problem (with all those sums and binomials), it makes sense to try to find a combinatorial interpretation of the values. In particular, define: $$f(M,N)=\sum_{i=0}^{M-1}\sum_{j=0}^{N-1}p^i(1-p)^j{i+j\choose i}$$ Before we get into what this means, we notice a useful quality of this function: $$f(M,N)=1+pf(M-1,N)+(1-p)f(M,N-1)$$ which can be proven since it expands to: $$f(M,N)=1+\left(\sum_{i=0}^{M-2}\sum_{j=0}^{N-1}p^{i+1}(1-p)^{j}{i+j\choose i}\right)+\left(\sum_{i=0}^{M-1}\sum_{j=0}^{N-2}p^{i}(1-p)^{j+1}{i+j\choose i}\right)$$ which, after we jigger with the sum limits becomes $$f(M,N)=1+\left(\sum_{i=1}^{M-1}\sum_{j=0}^{N-1}p^{i}(1-p)^{j}{i+j-1\choose i-1}\right)+\left(\sum_{i=0}^{M-1}\sum_{j=1}^{N-1}p^{i}(1-p)^{j}{i+j-1\choose i}\right)$$ and combining the sums where $M,N\geq 1$, splitting off the sums where $i=0$ or $j=0$ separately, and using the identity that ${i+j-1\choose i-1}+{i+j-1\choose i}={i+j\choose i}$ gives $$f(M,N)=1+\left(\sum_{i=1}^{M-1}p^{i}(1-p)^{0}{i+0-1\choose i-1}\right)+\left(\sum_{j=1}^{N-1}p^{0}(1-p)^{j}{0+j-1\choose 0}\right)+\left(\sum_{i=1}^{M-1}\sum_{j=1}^{N-1}p^{i}(1-p)^{j}{i+j\choose i}\right)$$ but since ${i+0-1\choose i-1}=1={i+0\choose i}$ and ${0+j-1\choose 0}=1={0+j\choose 0}$ and $1=p^0(1-p)^0{0\choose 0}$, the above all collapses to $$f(M,N)=\sum_{i=0}^{M-1}\sum_{j=0}^{N-1}p^i(1-p)^j{i+j\choose i}$$ as we expected. This all goes to ensure that we have the identity $$f(M,N)=1+pf(M-1,N)+(1-p)f(M,N-1).$$

Why is this important? Well, I interpret $f$ as follows:

If a person starts at the position $(M,N)$ and chooses to walk left (decreasing the $x$-coordinate by $1$) with probability $p$ or down (decreasing the $y$-coordinate) with probabiliy $(1-p)$, then $f(M,N)$ is the expected number of steps before one of the coordinates is $0$.

This is obvious from the recursive definition - the sum can be read that the person will take $1$ step (hence the $1+\ldots$ term) and then will, with probability $p$ be in the state $(M-1,N)$ and with probability $(1-p)$ be in the state $(M,N-1)$.

An intuitive way to see all of the above is that $p^i(1-p)^j{i+j\choose j}$ is the probability that the person would walk through $(0,0)$ if they started at $(i,j)$ that - or equivalently, it is the expected number of times that they would walk through $(M-i,N-j)$ if they started at $(M,N)$. If we sum up all of these expected values, we get the expected number of steps the person would would spend walking before reaching the $x$ or $y$ axes.

To further elucidate the problem, define two random variables $T_x$ and $T_y$, representing the number of steps taken before the $x$ and $y$ coordinates respectively are $0$, given that the person starts at $(M,N)$. Then, we can write three suggestive relations with these (where $\mathbb{E}$ is the expectation operator): $$\mathbb{E}(T_x)=\frac{M}p$$ $$\mathbb{E}(T_y)=\frac{N}{1-p}$$ $$\mathbb{E}(\min(T_x,T_y))=f(M,N)$$ where the last one is because the condition of the person having one zero coordinate occurs whenever either $T_x$ or $T_y$ does. We're essentially being asked to prove that, in this case $$\mathbb{E}(\min(T_x,T_y))\text{ is asymptotic to }\min(\mathbb{E}(T_x),\mathbb{E}(T_y)).$$ What is obvious from this is that, since the minimum of two variables must have expected value less than either variable, we get $$f(M,N)\leq \min\left(\frac{M}p,\frac{N}{1-p}\right).$$ If we can show that, for any $\varepsilon$ and all large enough $M$ and $N$, that $$(1-\varepsilon)\min\left(\frac{M}p,\frac{N}{1-p}\right)\leq f(M,N)$$ then we have shown that the limit converges to $1$, as expected.

To do this, consider the probability, for fixed $\lambda_1$ of $$P\left(T_x \leq (1-\lambda_1)\frac{M}p\right)$$ that is that the $x$ coordinate reaches $0$ by a constant factor faster than expected. We can easily show that this is the same as saying probability as the probability that, after $(1-\lambda_1)\frac{M}p$ steps, the $x$ coordinate of the person is $0$ or less - now, the $x$-coordinate is distributed according to a translation of binomial distribution with mean $\lambda_1 M$ and the probability that this is less than $0$ will clearly shrink to $0$ as $M$ increases to infinity (as a consequence of the central limit theorem). Thus, for any $\lambda_2>0$, we can choose $M$ large enough so that $P\left(T_x \leq (1-\lambda_1)\frac{M}p\right)<\lambda_2$. By a similar argument, we can choose $N$ large enough so that $P\left(T_y \leq (1-\lambda_1)\frac{N}(1-p)\right)<\lambda_2$.

What do we do with this knowledge? Well, this means that $$p=P\left(\min(T_x,T_y)\leq (1-\lambda_1)\min\left(\frac{M}p,\frac{N}{1-p}\right)\right)<2\lambda_2$$ since at least one of the before conditions must hold for this to hold. However, note that since $\min(T_x,T_y)>0$ we know that the function $$r(x)=\begin{cases}0&&\text{if }x\leq (1-\lambda_1)\min\left(\frac{M}p,\frac{N}{1-p}\right)\\(1-\lambda_1)\min\left(\frac{M}p,\frac{N}{1-p}\right)&&\text{if }x>(1-\lambda_1)\min\left(\frac{M}p,\frac{N}{1-p}\right)\end{cases}$$ will round every value of $\min(T_x,T_y)$ downwards implying: $$f(M,N)=\mathbb{E}(\min(T_x,T_y))\geq\mathbb{E}(r(\min(T_x,T_y)))$$ but since $r$ would be $0$ with probability $p$ and would be $(1-\lambda_1)\min\left(\frac{M}p,\frac{N}{1-p}\right)$ with probability $(1-p)$, this yields that \begin{align*}\mathbb{E}(r(\min(T_x,T_y)))&=(1-p)(1-\lambda_1)\min\left(\frac{M}p,\frac{N}{1-p}\right)\\&>(1-2\lambda_2)(1-\lambda_1)\min\left(\frac{M}p,\frac{N}{1-p}\right)\end{align*} Choose $\lambda_1$ and $\lambda_2$ such that $(1-2\lambda_2)(1-\lambda_1)>(1-\varepsilon)$ and we have already demonstrated that, for sufficiently large $M$ and $N$, the value $f(M,N)$ is greater than the above. This means that your limit does, indeed, converge to $1$.

• A hint and a question: Since $\binom{i+j}{i}$ represents the number of pathes of length $i+j$ from $(0,0)$ to $(i,j)$ containing only $(1,0)$ and $(0,1)$-steps, multiplying this value by $p^i(1-p)^j$ is not a probability, but an expectation value instead. My question: I don't see the validity of your suggestive relations. Could you clarify or calculate $\mathbb{E}(T_x)=\frac{M}{p}$? Thanks in advance. – Markus Scheuer Nov 5 '14 at 23:02
• @Markus Define $g(M)$ to be $\mathbb{E}(T_x)$ in an $M$-wide grid. Clearly $g(0)=0$. Then, for $g(M+1)$, note that, after the first step, with probability $p$ the $x$-coordinate is $M$ and is otherwise still $M+1$, hence we get $g(M+1)=1+pg(M)+(1-p)g(M+1)$ which solves to $g(M+1)=\frac{1}p+g(M)$. I figured this was intuitive enough, since we expect $1/p$ trials before an event with probability $p$ occurs. (The hint, I presume, suggests that, taking the summand as the expected number of times $(i,j)$ is visited, the sum is quite obviously the number of steps stayed within $[1,M]\times[1,N]$) – Milo Brandt Nov 6 '14 at 1:52
• Good answer, thanks! Your reasoning is now clear to me. :-) +1 – Markus Scheuer Nov 6 '14 at 8:31
• One thing I should point out: I think the $x$-coordinate is NOT a binomial distribution (with mean $\lambda_{1}M$), but anyway it has mean of $\lambda_{1}M$ and CLT is applicable. Anyhow, great argument. – fiverules Nov 6 '14 at 11:34
• To add something, your argument only deals with the case where both $M, N \to \infty$. The condition $\max (M,N) \to \infty$ contains the situation that one of them oscillates and remaining one goes to infinity.. – fiverules Nov 6 '14 at 18:12