1
$\begingroup$

Given a set $S= \{s_1,s_2,..,s_n\}$ and each element $s_i \in S$ has an assigned probability $p(s_i)$. Then, a selection process is applied to the set $S$ such that, each element $s_i \in$ $S$ is removed from the set $S$ based on its probability $p(s_i)$. We do this process for $k$ times, and for each time we want to find the number of deleted items from the set $S$. Here starts my question: The number of deleted items, $Q_t$, from the list at any time $0 < t \leq k$ can be obtained by:

$Q_t = \sum\limits_{s_i \in S}{p(s_i)}$

Is the above formula correct? Do we need to consider the probability that an item $p_i$ was not deleted at $t-1$ when we counting the number of deleted items at $t$, such that:

$Q_t = \sum\limits_{s_i \in S}{(1-p(s_i))\cdotp(s_i)}$

thanks!

$\endgroup$
  • 3
    $\begingroup$ Hint: the chance that $s_i$ remains in the set after $k$ trials is $(1-p(s_i))^k$. Use that to find the expected number of elements that remain. BTW, your formula for $Q_t$ requires some kind of special interpretation, because the $s_i$ are not necessarily numbers. $\endgroup$ – whuber Aug 3 '16 at 20:36
1
$\begingroup$

Instead of thinking about the set $S$, I would also give it a step index, so that $S_0=S$ and $S_1$ corresponds to a random variable that contains the objects that remain after one round of deletion.

This helps clarify between two different possible interpretations of $Q_t$: in one case, it is everything that has been deleted since the beginning ($S_0$-$S_t$), and in the other case, it is only those objects deleted in the last step ($S_{t-1}$-$S_{t}$).

whuber's hint, that the survival probability ($1-p(s_i)$) is more natural than the deletion probability, is the main piece necessary to find the correct formula. Combine it with the definition of $Q_t$ as a difference of sets above, and you're done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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