2
$\begingroup$

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

  • 0
    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.2012-10-15
  • 0
    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$.2012-10-15
  • 0
    @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.2012-10-16

1 Answers 1