# The probability that random removal of members from a set results in the empty set

Assume that $A=[k] = \{1,\ldots k\}$. Consider the following random process:

1. Let $A_0$ be $A$,
2. For each $i\in \mathbb{N}$, let $B_i\subseteq A_i$ be a random subset of $A$: $Pr\{j \in B_i\}=p$ (iid).
3. Let $A_{i+1} = A_i - B_i$.

In other words, we start with a set of size $k$ and at each step we remove the members independently with probability $p$ and continue this process for $l$ steps.

Questions:

1. What is the probability that after $l$ steps the size of the set reduces to zero? ($Pr\{|A_l|=0\}$)

2. What is the probability that after $l$ steps the size of the set is at least 2? ($Pr\{2 \leq |A_l| \}$)

3. What is the probability that one of $A_i$s for $0\leq i\leq l$ has size one? ($Pr\{\exists 0\leq i \leq l, \ |A_l|=1 \}$)

I am looking for answers in terms of $k$, $l$, and $p$.

### Clarification:

I need to understand the relation between these parameters and the probabilityies (e.g. what happens when $l=\lg k$? is the probability bounded away from 0? greater than $\frac{1}{2}$ and bounded from it? etc.) so I need nice closed forms.

If it is not possible to give a closed form for the exact value then a nice closed form for estimate with a small error.

The main case I am interested in is $p=\frac{1}{2}$, so if giving the answer for arbitrary $p$ is difficult then you can assume $p = \frac{1}{2}$.

-
It seems Hagen's post answers fully your question as you formulated it initially. The Clarification you just added modifies completely the scope of the question. I suggest to delete the so-called clarification, to accept the answer and to ask another question, describing more clearly and more precisely the problem you are interested in. – Did Oct 15 '12 at 6:47
Note that Hagen's formula already yields that $P(|A_l|=0)$ is nearly $1$ if $l\gg\lg k$ and nearly $0$ if $l\ll\lg k$. – Did Oct 15 '12 at 6:50
@did, this is what I intended to ask (close form answer), I wasn't expecting a sum as an answer, but that is fine, I don't mind asking a new question. I will post a new question. – Kaveh Oct 16 '12 at 4:16

For a single element, the probability to survive up to $A_l$ is $(1-p)^l$. Thus
1. $Pr\{|A_l|=0\}=(1-(1-p)^l)^k$
2. $Pr\{|A_l|\ge 2\}=1-Pr\{|A_l|=2\}-Pr\{|A_l|=1\}=1-(1-(1-p)^l)^k-k(1-p)^l(1-(1-p)^l)^{k-1}$
3. is a bit more difficult. $Pr\{|A_i|=1\} = k(1-p)^i(1-(1-p)^i)^{k-1}$ and $Pr\{|A_i|=1, |A_{i+1}|=0\} = k(1-p)^i(1-(1-p)^i)^{k-1}p$. Thus the answer is $$\sum_{i=0}^{l-1} k(1-p)^i(1-(1-p)^i)^{k-1}p+ k(1-p)^l(1-(1-p)^l)^{k-1}$$ (The firs sum counts probability that at step $i$ there is one element for the last time, the extra summand accounts for exactly one lement at the end of the experiment).