Overall problem: Sample i.u.d. from $\{1,\dots,n\}$. What is (a good lower bound for) the probability of getting the values $1$ and $2$ before either you get a number you have seen before or you have sampled $\lceil \sqrt{n} \rceil$ numbers?

I have formulated the problem using 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 an event occurring in a Markov chain before time $k$. I have computed the values for all $n<300$ and it does hold for those.

I 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 I can assume that $k \leq i$.

I would like to solve this particular problem but also more generally to learn techniques for giving good lower bounds for the probability of an event occurring in a Markov chain before a fixed time. In that light, is there a direct way of proving this without having to solve the recurrence fully?

This is the same question as the unanswered http://math.stackexchange.com/questions/364809/lower-bound-for-multivariate-recurrence .