# Lower bound for multivariate recurrence

I have a recurrence that looks like

$$p(i,j,k) = \frac{j}{n}p(i-1,j-1,k-1) + \frac{i-j}{n}p(i-1,j,k-1)$$

$$p(i,0,k) = 1$$ $$p(i,j,0) = 0$$ $$p(0,j,k) = 0$$

The base cases are to be considered in order from top to bottom. So the first matching one applies.

We define the function only when $0\leq i,k \leq n$ and $0\leq j \leq 2$.

I would like to prove that $$p\left(n,2,\left\lceil \sqrt{n} \right\rceil\right) \geq \frac{1}{2n}$$

for $n\geq 2$.

The recurrence measures the probability of events occurring in a Markov chain. I have computed the values for all $n<300$ and it does hold for those.

Is there a direct way of proving this without having to solve the recurrence fully? It looks like you should be able to prove it by induction but I can't exactly see how.

Update. As suggested in the comments, we can solve $p(i,1,k)$ explicitly just by unrolling as the recurrence is simply $$p(i,1,k) = \frac{1}{n} + \frac{i-1}{n} p(i-1,1,k-1)$$

and we can also assume $k \leq i$ so we know exactly how many steps to unroll for. However, I am not sure how much this helps.

• Are $i,j,k\le n$ ? Commented Apr 17, 2013 at 20:06
• @BorisNovikov Yes. In fact I am only interested in $p\left(n,2,\left\lceil \sqrt{n} \right\rceil\right)$ so this also follows from that.
– user66151
Commented Apr 17, 2013 at 20:07
• Then maybe it would simplier consider two equations with the functions $q(i,k)=p(i,1,k)$ and $r(i,k)=p(i,2,k)$. It seems one can find an explicit expression at least for $q(i,k)$. Commented Apr 17, 2013 at 20:53
• @BorisNovikov That's what I started with but I didn't manage to solve it that way.
– user66151
Commented Apr 18, 2013 at 7:37
• Make one more change: $q(i,k)=s(i,k)\frac{(i-1)!}{n^k}$. Commented Apr 18, 2013 at 9:08

I suppose that $i>k$.
1) Let $j=1$. Setting $p(i,1,k)=\frac{(i-1)!}{n^k}r(i,k)$ we have $$r(i,k)=\frac{n^{k-1}}{(i-1)!}+r(i-1,k-1).$$ From here $$r(i,k)=\frac{1}{n^{i-k}}\sum_{\alpha=i-k}^{i-1}\frac{n^\alpha}{\alpha!}\approx \frac{1}{n^{i-k}}(e^{i-1}-e^{i-k}).$$
2) Let $j=2$. Setting $p(i,2,k)=\frac{(i-2)!}{n^k}t(i,k)$ we have $$t(i,k)=2r(i,k)+t(i-1,k-1).$$ From here $$t(i,k)=2(r(i,k)+r(i-1,k-1)+\ldots +r(i-k+2,2))\approx \ldots$$ (here you have a geometric progression). Of course, $\approx$'' should be used cautiously.