Probabilistic deletion of elements from a set

Question

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!

Answer 1

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.