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:

*

*Let $A_0$ be $A$,

*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).

*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:

*

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


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


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

For a single element, the probability to survive up to $A_l$ is $(1-p)^l$.
Thus  


*

*$Pr\{|A_l|=0\}=(1-(1-p)^l)^k$

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

*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).

