8
$\begingroup$

I have a recurrence

$$f(i,j) = 1+ \frac{N-i}{N} f(i,j-1) + \frac{i}{N} f(i-1, j)$$

$$f(i,0) = 0$$ $$f(0,j) = j$$

I would like to compute $f(N,M)$ in terms of N and M. The system is defined for $0\leq i\leq N$ and $0\leq j\leq M$ where $N$ and $M$ are non-negative integers.

I am familiar with techniques for solving single variable recurrences but cannot see how to extend them to this situation. Is there some generating function solution one can write down? Is it known how to solve this sort of recurrence?

By a hand wavy argument I believe the solution looks asymptotically roughly like $c\sqrt{NM}$ for some constant $c$, when $N > M$.

[Fixed typo in question.]

$\endgroup$
4
  • $\begingroup$ Are you sure the statement is correct? As far as I can see, an arbitrary choice of values of $f(0,j)$ for $0< j\le M$ can be completed to a solution of the recurrence, in particular $f(0,M)$ can be absolutely anything. $\endgroup$ Apr 3, 2013 at 15:32
  • $\begingroup$ @EmilJeřábek Fixed typo. $f(0,M) = M$ as you only ever take the $f(i,j-1)$ case. $\endgroup$
    – user32786
    Apr 3, 2013 at 15:41
  • $\begingroup$ Did you try generatingfunctionology? $\endgroup$ Apr 3, 2013 at 15:45
  • $\begingroup$ @MartinRubey Yes that is what I have been reading before getting stuck and asking here. $\endgroup$
    – user32786
    Apr 3, 2013 at 15:49

2 Answers 2

11
$\begingroup$

You have $f(0,j) = 1 + f(0,j-1)$ so $f(0,j) = j$. I get

$$f(1,j) = j + 1 - \left(\frac{N-1}{N}\right)^j $$

$$ f(2,j) = j + 2 - 2 \frac{(N-1)^{j+1}}{N^{j+1}} - 2 \frac{(N-2)^j}{N^{j+1}}$$

$$ f(3,j) = j + 3 - 3 \frac{(N-1)^{j+2}}{N^{j+2}} - 6 \frac{(N-2)^{j+1}}{N^{j+2}} - 9 \frac{(N-3)^j}{N^{j+2}}$$

$$ f(4,j) = j + 4 - 4 \frac{(N-1)^{j+3}}{N^{j+3}} - 12 \frac{(N-2)^{j+2}}{N^{j+3}} - 36 \frac{(N-3)^{j+1}}{N^{j+3}} - 64 \frac{(N-4)^{j}}{N^{j+3}}$$

It looks like $$f(i,j) = i + j - \sum_{k=1}^i k^{k-1} {i \choose k} \frac{(N-k)^{i+j-k}}{N^{i+j-1}}$$

$\endgroup$
1
  • $\begingroup$ Thank you for this exact answer and no generating functions needed. $\endgroup$
    – user32786
    Apr 4, 2013 at 18:01
5
$\begingroup$

This problem has a probabilistic interpretation. Namely, if one considers the Markov chain on the integer points in the rectangle $[0,N]\times [0,M]$ with the transition probabilities $$ p\bigl((i,j),(i,j-1)\bigr) = \frac{N-i}{N} \;, \qquad p\bigl((i,j),(i-1,j)\bigr) = \frac{i}{N} \;, $$ then $f(i,j)$ is the expected number of steps until the chain attains the horizontal line $\{j=0\}$ where it is absorbed. Now, the $i$ component of this chain is the Markov chain on $[0,N]$ with the transition probabilities $$ p(i,i) = \frac{N-i}{N} = p_i \;, \qquad p(i,i-1) = \frac{i}{N} = 1-p_i\;, $$ which can be interpreted as the deterministic chain $i\to i-1$ with additional "holding" at each state. The distribution of this holding time at a point $i$ is geometric with the parameter $1-p_i$, i.e., the holding time is 0 with probability $1-p_i$, is 1 with probability $p_i(1-p_i)$, etc. Thus, the expectation of the holding time at point $i$ is $p_i/(1-p_i)$, and the expected vertical displacement of the original chain provided its horizontal component attains a point $t\in [0,n]$ is $$ M_t=\frac{p_N}{1-p_N} + \dots + \frac{p_t}{1-p_t} = \frac{1}{N-1} + \dots + \frac{t}{N-t} \sim \int_0^t \frac{x}{N-x}dx = N\log\frac{N}{N-t}-t \;. $$ In particular, if $t$ is close to $N$, then $M_t\gg N>M$, which means that our chain most likely becomes absorbed before it attains the vertical segment $\{i=0\}$. [More rigorously here one should also estimate the variance of the vertical displacement to make sure it does not differ much from $M_t$.]

Now the equation $$ M = N\log\frac{N}{N-t}-t $$ will give us the likely number of horizontal steps $t$ necessary to have vertical displacement $M$, i.e., to be absorbed. The total expected time before absorption will be therefore $$ f(N,M)=M + t = N\log\frac{N}{N-t} \;. $$

The above equation can be rewritten as $$ \frac{M}{N} = -\log (1-t/N) - t/N \;. $$ Under the assumption that $M \ll N$ (i.e., $t \ll N$) one can expand the log in the RHS, which gives $$ \frac{M}{N} \approx \frac{t^2}{2N^2} \;, $$ whence $t\approx\sqrt{2MN}$ and $f(N,M)\approx\sqrt{2MN}$.

$\endgroup$
2
  • $\begingroup$ Thank you for a really nice alternative way at looking at the problem. It's good to see it matches my hand wavy argument too. For this approach could you possibly give more details for what you need to prove in terms of the variance to make the argument rigorous? Also a small thing, If $M = 1$ I think it's the Birthday Problem so $f(N,1) \approx \sqrt{\frac{\pi N}{2}}$. It looks the constant varies between $\sqrt{\frac{\pi}{2}}$ and $\sqrt{2}$. $\endgroup$
    – user32786
    Apr 4, 2013 at 18:00
  • $\begingroup$ Concerning the variance it's just a simple calculation (since the variance of exponential distributions is explicitly known) - then one has to apply the standard Chebyshev inequality (in the same way as in the proof of the weak law of large numbers). $\endgroup$
    – R W
    Apr 4, 2013 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.