2
$\begingroup$

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 .

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas Zare
    Commented Apr 23, 2013 at 1:40
  • $\begingroup$ @DouglasZare You are quite right. Question updated. $\endgroup$
    – Simd
    Commented Apr 23, 2013 at 19:13

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Simd
    Commented Apr 24, 2013 at 10:12
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Douglas Zare
    Commented Apr 24, 2013 at 10:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .