Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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).
share|improve this answer
    
Thanks Hagen but the sum is not very useful for me. For what I am doing I need to understand the relationship between these parameters and the probabilities. –  Kaveh Oct 15 '12 at 6:34
    
You could plug that in wolfram alpha with different values. I think you can get sliders. –  PyRulez Jun 25 '13 at 14:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.