MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 .

share|cite|improve this question
It looks like this came from a particular problem, you chose one technique, and then removed the original problem. But if you chose the wrong technique, the simplest solution is probably to rediscover the problem you deleted and then pursue a better technique. If you really want to solve the original, don't delete it and force that technique on others. I think the original problem was something like finding the probability that you encounter two particular birthdays before the first repetition. – Douglas Zare Apr 23 '13 at 1:40
@DouglasZare You are quite right. Question updated. – motl737 Apr 23 '13 at 19:13
up vote 2 down vote accepted

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}$.

share|cite|improve this answer
Thank you. Embarrassingly (for me) this is the first argument I came up with but decided (mistakenly) it wasn't precise. The process stops early if it finds a repeat or a $1$ and a $2$. So if we talk about $\sqrt{n}$ samples then we know it doesn't contain a $1$ and $2$ already (and also is not a uniform subset). I feel there is one sentence that will fix this confusion of mine so sorry this is so basic. – motl737 Apr 24 '13 at 10:12
You can continue drawing until you have $\sqrt{n}$. This will underestimate the probability because you might reach $1$ and $2$ successfully, then discard this because you encounter a repeat. The underestimate is still more than $1/2n$. – Douglas Zare Apr 24 '13 at 10:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.