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
    @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

3

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).
  • 0
    You could plug that in wolfram alpha with different values. I think you can get sliders.2013-06-25