AnonymousBunny wrote:

Let $g(m,n)=1/f(m,n)$ . Consider a random walk starting from $(m+1,n)$ where at each step we go left or down 1 unit with equal probability. Then, $g(m,n)$ is the probability that we touch the line $y=0$ before we touch the line $x=0$ .

So we want to estimate the following quantity: start a random walk from $(n+1,n)$ . What is the probability we hit $y=0$ before $x=0$ ? Let $E$ denote this event.

Let $P_i=(x_i,y_i)$ be the $i$ th point in the step and let $v$ be the largest $i$ such that $|y_i-x_i|=1$ . Condition on $v=k$ ; we want to estimate $P(x_k>y_k|v=k)$ . I claim this is $\geq 1/2+1/(2n-1)$

Consider a set of lattice paths where from each $(x,y)$ we go to either $(x+1,y+1)$ or $(x+1,y-1)$ .
Let $A$ be the number of such length $k$ paths from $(0,1)$ to (k,1) which touch the line $y=0$ , $B$ be the number of paths from $(0,1)$ to $(k,1)$ which don't touch the line $y=0$ and let $C$ be the number of paths from $(0,1)$ to $(k,-1)$ . By standard bijection arguments, the conditional probability we want to compute is $(A+B)/(A+B+C)$ . Moreover, by reflection argument, $B=C$ , and by using Catalan numbers, $A=(A+B/((k-1)/2)$ . Since $k \leq 2n$ , we get that $A/(B+C) \geq 1/2+ 1/(2n-1)$ .

Now simply note that $E$ is true iff $x_v>y_v$ where $v$ is defined as above. Since for each conditioning of $v$ the conditional probability is $\geq 1/2+ 1/(2n-1)$ we get that $g(n,n) \geq 1/2+ 1/(2n-1)$ .

In fact this inequality must be strict because the conditional probability is strictly larger for small values of $v$ (which have a nonzero probability).

I think the reflection argument shows $A=C$ , not $B=C$ .
Furthermore, for computing $A/B$ , my calculation gave $(A+B)/C = (k+2)/k$ . Hence $A:B:C = k : 2 : k$ , and the probability is $\frac{k+2}{2k+2} \geq \frac{1}{2} + \frac{1}{2n+1}$ , which is weaker than $\frac{1}{2} + \frac{1}{2n-1}$ you claimed but still suffices because that value is $\frac{100}{199} = 1.99^{-1}$ . If you have spare time please calculate again and edit post or reply to check out who is right