**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? In particular, how can we prove it is at least $1/2n$?


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 either of two stopping conditions. 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 <https://math.stackexchange.com/questions/364809/lower-bound-for-multivariate-recurrence> .



Probability of event occurring before either of two stopping conditions
This particular problem can be solved by dividing it into two parts.


First, the probability that the first $\sqrt{n}$ numbers chosen are all distinct. Second, the probability that a random subset of $\{1,..,n\}$ of size $\sqrt{n}$ contains $1$ and $2$. The first probability is $\prod\_{k=1}^{\sqrt{n}} (1-\frac{k}{n}) \approx e^{-\frac12} \approx 0.6$. The second is $\frac{\sqrt{n}}{n}\frac{\sqrt{n-1}}{n-1}=\frac1n (1+o(1))$. Together, that's already more then $\frac1{2n}$.


