3
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ Are $i,j,k\le n$ ? $\endgroup$ Commented Apr 17, 2013 at 20:06
  • $\begingroup$ @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. $\endgroup$
    – user66151
    Commented Apr 17, 2013 at 20:07
  • $\begingroup$ 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)$. $\endgroup$ Commented Apr 17, 2013 at 20:53
  • $\begingroup$ @BorisNovikov That's what I started with but I didn't manage to solve it that way. $\endgroup$
    – user66151
    Commented Apr 18, 2013 at 7:37
  • $\begingroup$ Make one more change: $q(i,k)=s(i,k)\frac{(i-1)!}{n^k}$. $\endgroup$ Commented Apr 18, 2013 at 9:08

1 Answer 1

0
+50
$\begingroup$

I write an exact solution of the equation and hope that it helps to you to obtain some estimate.

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.

$\endgroup$

You must log in to answer this question.