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