Skip to main content
6 of 6
added 345 characters in body; edited tags
Simd
  • 3.4k
  • 26
  • 54

How to show a function converges to 1

Consider the following recurrence relation in two variables: $$f(a, b) = \frac{a}{a+b} f(a-1,b)+ \frac{b}{a+b}f(a+1,b-1) $$ for positive integers $a$ and $b$, with the boundary conditions $f(0,b)=0$ for integers $b>0$ and $f(a,0)=1$ for integers $a\ge0$.

I believe that $f(1,n)$ converges to $1$ as $n$ tends to infinity. However I can't see how to prove it.

Numerically the convergence is slow.

@FedorPetrov's reformulation of the recurrence as a probability question is as follows (lightly edited). Consider an urn with $a$ White and $b$ Black balls. Take a random ball, eat it if it is White and recolor it White (returning to the urn) if it is Black. Then $f(a,b)$ is the probability that when the balls become of the same color, this color is White.

Simd
  • 3.4k
  • 26
  • 54