7
$\begingroup$

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}. $$

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

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Markus Scheuer Nov 5 '14 at 23:02
  • $\begingroup$ @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]$) $\endgroup$ – Milo Brandt Nov 6 '14 at 1:52
  • $\begingroup$ Good answer, thanks! Your reasoning is now clear to me. :-) +1 $\endgroup$ – Markus Scheuer Nov 6 '14 at 8:31
  • $\begingroup$ 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. $\endgroup$ – fiverules Nov 6 '14 at 11:34
  • $\begingroup$ 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.. $\endgroup$ – fiverules Nov 6 '14 at 18:12

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.