3
$\begingroup$

If we have a set $S= \{s_1,s_2,..,s_n\}$ and each element in the set $S$ has an assigned probability $P_n$. Then a selection process is applied to the set $S$ such that, each element $S_n \in$ $S$ is selected in a returned set $RS$ based on its probability ($P_n$). (For example, if all probabilities are $1$, then $RS$ =$S$)

Is there any mathematical formula that represent the number of elements in $RS$ ?

$\endgroup$
3
$\begingroup$

One way to work through this problem is to adopt the formal machinery of probability spaces and random variables. It's less formidable than it sounds and often leads to elegant, simple calculations. The key idea is to introduce indicator functions, which are random variables that encode the selection process in a useful, elegant way.


In this case, ask yourself "to what random variable would each probability apply?" The probabilities describe selecting an $s_i$ or not. To encode that as a random variable--which is just a way of associating a number with each outcome--it is usually most convenient to associate a $1$ with the selection of $s_i$ and a $0$ with its non-selection. This is generally known in mathematics as an "indicator function" but since we are thinking of it as a random variable, it often is called an "indicator variable."

In this way we have created a sequence of random variables $X_i$. Each is a Bernoulli variable with probability $\pi_i$. (I changed the "$P_i$" of the question to a small Greek letter in order to adhere to a convention of clearly distinguishing outcomes (small letters) from random variables (capital letters) from parameters (Greek letters).)

Counts are sums: adding a $1$ for each element selected and a $0$ for each element not selected gives the count. Therefore, the number of elements selected is the sum of the $X_i$. Mathematically we might write

$$X = X_1 + X_2 + \cdots + X_n = \sum_{i=1}^n X_i$$

for that random variable. This is the formula sought.


We could--and usually do--go further. Several more things are of interest:

  1. What is the expectation of $X$?

  2. How dispersed is the distribution of $X$?

  3. What exactly is the probability distribution of $X$?

These have accessible answers, now that a formula is available:

  1. The expectation, which we may interpret as predicting the average number observed over many independent replications of this sampling process, is

    $$\mathbb{E}(X) = \mathbb{E}(X_1 + \cdots + X_n) = \mathbb{E}(X_1) + \cdots + \mathbb{E}(X_n) = \pi_1 + \pi_2 + \cdots + \pi_n.$$

    The second equality is due to the linearity of expectation and it does not require that the elements be selected independently. (That is a useful insight!) The last equality is basic and follows directly from the definitions: the average value of a random variable that equals $1$ with probability $\pi_i$ and $0$ otherwise is

    $$\mathbb{E}(X_i) = \pi_i(1) + (1-\pi_i)(0) = \pi_i.$$

    (This expectation is so nicely related to the probability precisely because we chose wisely when constructing the random variables $X_i$. We could have chosen any two distinct numbers to represent the two outcomes, and thereby obtained valid formulas, but they would not have been so revealing.)

  2. The variance is a good measure of the variability of a random variable. Provided the $n$ selections are independent, the variances add just like the expectations do. Using the (easily computed) result that $X_i$ has a variance of $\pi_i(1-\pi_i)$ we obtain

    $$\text{Var}(X) = \sum_{i=1}^n \text{Var}(X_i) = \sum_{i=1}^n \pi_i(1-\pi_i).$$

    (When selections are not independent, there will be covariances of the cross-terms in this sum, given by $\text{Cov}(X_i,X_j)$ for each $i\ne j$. For certain kinds of selection procedures these covariances can be calculated, such as for the Horvitz-Thompson estimator.)

    The square root of the variance is the standard deviation (SD). Most of the time, a realization of $X$ (that is, the result of one selection process) will be within two SDs of its expectation. When $n$ is large-ish and most of the $\pi_i$ are not too close to $0$ or $1$, the 68-95-99.7 Rule will hold: about 68% of the time $X$ will be within one SD of its expectation, 95% of the time it will be within two SDs of its expectation, and almost all of the time (99.7%) it will be within three SDs. This simple rule and the simple calculations that lead up to it (which, with a little practice, are easy to do quickly in one's head) provide a basis for anticipating not only what value the selection count is likely to be, but also for determining how much it is likely to deviate from that expectation.

  3. Obtaining the probability distribution takes more advanced methods; moment generating functions, characteristic functions, or cumulant generating functions are preferred. For the details, formulas, and working code, please see Probability distribution for different probabilities.

$\endgroup$
1
$\begingroup$

The sum of the probabilities gives you the average number of elements in the returned set.

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