5
$\begingroup$

We say a finite point process $X$ on $[N]=\{1,…,N\}$ can be understood as a random subset. It is defined either via its inclusion probabilities, that is $\mathbb{P}(S \subseteq X)$ for $S \subseteq [N]$ or its likelihood $\mathbb{P}(X=S)$ for $ S \subseteq [N]$.

I would like to ask about the interpretation of the inclusion probabilities. My mental picture of the situation is that $X$ pulls out a random subset from $\{1, 2, ..., n\}$. So the likelihood picture makes a lot of sense here (the probability that the subset which I pull out happens to be $S$). However, how do the inclusion probabilities relate to this picture? What is the equation $\mathbb{P}(S \subseteq X)$ for $S \subseteq [N]$ actually saying, and why does it help? Why do we define the correlation functions using the inclusion probabilities? How can this be generally interpreted and viewed?

How can each part of the definition of a point process be related to our intuition, in particular the inclusion probabilities and their correlation functions?

$\endgroup$

1 Answer 1

5
$\begingroup$

There'a a lot going on here, but it is primarily a matter of mathematical notation and language. I will discuss a bunch of related in issues in the context of a simple running example. I won't attempt to write fully general formulas for everything, remaining content to show the calculations in enough detail to enable you to write such formulas if you care to.


One issue of substance is the PIE: Principle of Inclusion-Exclusion. It says that when a finite set $S$ is expressed as a union of proper subsets, $S = S_1\cup S_2\cup \cdots \cup S_k,$ you can count the elements of $S$ by summing the counts of its subsets and then adjusting that count by subtracting the number of elements in their mutual intersections (which subtracts too much), then adding back in the number of elements in their three-fold intersections, and so on.

Ultimately the PIE will show how the inclusion probabilities alone determine the probability distribution of the random sets.

Let's get to the matter of notation. We may view this "point process" equivalently as (a) taking random samples of (potentially) random sizes; (b) a stochastic process; (c) a multivariate distribution; or (d) a subset-valued random variable. To explain this I will describe one specific, simple such process in various ways. Let's begin with the example.

Use the notation $[0]=\emptyset$ and $[N]=\{0,1,\ldots, N-1\}$ (Indexing starts at $0$ rather than $1.$) For instance, $[N]=[3]$ has $2^3$ subsets, a collection known as its power set $\mathcal{P}([N]).$ Let's use the first eight letters of the Greek alphabet to identify them, as shown in this tabulation.

$$\begin{array}{clcccl|rr} \text{Name} & S & \mathcal{I}_0 & \mathcal{I}_1 & \mathcal{I}_2 & \text{Proper Subsets} & k & F \\ \hline \alpha & \{0,1,2\} & 1 & 1 & 1 & \beta,\gamma,\delta,\epsilon,\zeta,\eta,\theta & 1 & 1\\ \beta & \{0,1\} & 1 & 1 & 0& \epsilon,\zeta,\theta & 1 & \frac{5}{12}\\ \gamma & \{0,2\} & 1 & 0 & 1& \epsilon,\eta,\theta & 2 & \frac{5}{12}\\ \delta & \{1,2\} & 0 & 1 & 1& \zeta,\eta,\theta & 3 & \frac{7}{12}\\ \epsilon& \{0\} & 1 & 0 & 0& \theta & 1 & \frac{2}{12}\\ \zeta& \{1\} & 0 & 1 & 0& \theta & 2 & \frac{3}{12}\\ \eta& \{2\} & 0 & 0 & 1& \theta & 1 & \frac{2}{12}\\ \theta& \{\} & 0 & 0 & 0& & 1 & \frac{1}{12}\\ \end{array}$$

This table describes many interesting things:

  • Its rows $\alpha,\ldots, \theta$ correspond to the sample space $\Omega=\mathcal{P}([N]).$ It is the collection of all possible values of the random sets -- all $2^N$ of them.

  • The columns headed $\mathcal{I}_j$ are the indicators of the elements. By definition, for any $j\in [N],$ $$\mathcal{I}_j(S) = \left\{\begin{array}{ll} 1 & j \in S \\ 0 & j \notin S.\end{array}\right.$$

  • The vector $\mathbf I = (\mathcal{I}_0,\mathcal{I}_1,\mathcal{I}_2)$ is a binary representation of each set. This permits us to identify $\Omega$ with the set of $N$-digit binary sequences.

  • The collection of proper subsets of each set $S$ determines a partial order on the sets. We may write, for instance, $\zeta \le \beta$ because $\zeta=\{1\}$ is a subset of $\beta=\{0,1\}.$ However, neither of the relations $\eta\le\beta$ nor $\beta\le\eta$ holds: that's why this is only a partial order.

  • To this description I have added two columns $k$ and $F.$ The $k$ determine a probability distribution: divide any $k$ by their sum ($12$) to obtain the probability. For example, the chance that a random set obtained by this process is $\delta=\{1,2\}$ is $\Pr(\delta) = 3/12=1/4.$

  • If you were to print this table on paper (several times) and cut out eight strips for the eight rows on each sheet, $k$ tells you how many copies of each strip to place into a box. This box will therefore wind up with $1+1+2+\cdots +1 = 12$ strips, or "tickets."

  • A random set (with distribution determined by $k$) is a random draw of a ticket from this box.

  • Consequently, $\mathbf I$ is a vector-valued random variable and each of the indicators $\mathcal{I}_j$ is an (ordinary, real-valued) random variable.

Alternative Descriptions

The last column $F$ gives the "inclusion probabilities" mentioned in the question. There are several equivalent ways of looking at them.

  1. For any outcome $S$ listed in the table, $F(S)$ is the sum of probabilities of $S$ and all its proper subsets. That is, $$F(S) = \sum_{T\subseteq S} \Pr(T)= \Pr(S) + \sum_{T\subset S, T\ne S} \Pr(T).$$ For instance, $$F(\delta) = \Pr(\delta) + \Pr(\zeta) + \Pr(\eta) + \Pr(\theta) = \frac{3 + 2 + 1 + 1}{12} = \frac{7}{12}$$ as you can read directly from the "Proper Subsets" column and $k$ column.

  2. The vector-valued random variable $(\mathcal{I}_0, \mathcal{I}_1, \mathcal{I}_2)$ has (by a standard definition) a cumulative distribution function $G$ defined by $$\begin{array}{rl} G:&\mathbb{R}^3\to[0,1] \\ G(x_0,x_1,x_2) &= \Pr(\mathcal{I}_0 \le x_0 \text{ and } \mathcal{I}_1\le x_1 \text{ and } \mathcal{I}_2\le x_2).\end{array}$$ (Because the ranges of the indicator variables are within the unit interval $[0,1],$ this exhibits $G$ as a copula.)

$F$ and $G$ are equal. A neat choice of notation will make this apparent. The vector-valued random variable $\mathbf{I} = (\mathcal{I}_0,\mathcal{I}_1,\mathcal{I}_2)$ sets up a one-to-one correspondence between each possible random set and the value of $\mathbf I$ via

$$S\subseteq [N] \longleftrightarrow \mathbf{I}(S) \in \mathbb{R}^N.$$

The standard partial order on $\mathbb{R}^N$ is componentwise comparison: we write $\mathbf{x}\le \mathbf{y}$ if and only if $x_i\le y_i$ for every component $i.$ Under the foregoing correspondence, comparison of subsets is the same as comparison of their indicators. That is, for $S,T\subseteq[N],$ $$S\subseteq T\ \text{ if and only if }\ \mathbf{I}(S) \le \mathbf{I}(T).$$

We have seen

The inclusion probabilities of the subsets $X\subseteq [N]$ specify the distribution function $F$ of the indicator $\mathbf I.$

The PIE merely restates how multivariate distribution functions work. See https://stats.stackexchange.com/a/386409/919 for a full algebraic explanation. The point, of course, is that the inclusion probabilities completely determine the probability distribution on $\Omega.$

Correlations

The natural sense of "correlation" in the question concerns the correlations (and covariances) of the indicators. First let's look at the means: these are the expected fraction of time a particular value $i$ will appear in a random set, equal to the chance that $i$ appears:

$$E[\mathcal{I}_i] = \Pr(\mathcal{I}_i=1)\times 1 + \Pr(\mathcal{I}_i=0)\times 0 = \Pr(\mathcal{I}_i=1).$$

By definition, the covariances are

$$\operatorname{Cov}(\mathcal{I}_i, \mathcal{I}_j) = E[\mathcal{I}_i\mathcal{I}_j] - E[\mathcal{I}_i]E[\mathcal{I}_j].$$

On the right we see (a) the chance that both $i$ and $j$ appear in a random set $S,$ adjusted for the chance both would appear if they were independent.

For instance, in the running example $$E[\mathcal{I}_0] = \Pr(0\in S) = \Pr(\alpha) + \Pr(\beta) + \Pr(\gamma) + \Pr(\epsilon) = 5/12,$$ with similar calculations giving $E[\mathcal{I}_1] = 7/12 = E[\mathcal{I}_2].$

Likewise,

$$E[\mathcal{I}_0\mathcal{I}_1] = \Pr(\alpha) + \Pr(\beta) =2/12,$$

whence

$$\operatorname{Cov}(\mathcal{I}_0,\mathcal{I}_1) = \frac{2}{12} - \frac{5}{12}\times \frac{7}{12} = -\frac{11}{144}.$$

Finally, because $\mathcal{I}_i^2 = \mathcal{I}_i$ (since $0^2=0$ and $1^2=1$), the variances don't require any more computation. Indeed, these indicators are (obviously) Bernoulli random variables. So, for instance, the variance of $\mathcal{I}_0$ is $(5/12)\times(1-5/12) = 35/144$ and the variance of $\mathcal{I}_1$ is the same. Thus, according to the usual formula,

$$\operatorname{Cor}(\mathcal{I}_0, \mathcal{I}_1) = \frac{-11/144}{35/144} = -\frac{11}{35}.$$

Sampling and Point Inclusion Probabilities

A random subset $S$ of $[N]$ can be considered a random sample of $[N].$ Crucial in the statistical theory of estimating properties based on a sample are the (point) inclusion probabilities

$$\pi_i = \Pr(i\in S)$$

and joint inclusion probabilities

$$\pi_{ij} = \Pr(\{i,j\}\subset S).$$

They are the chances that element $i$ will appear in the sample and, for $i\ne j,$ the chances that both $i$ and $j$ appear together in the sample.

In our running example, we may directly compute the point inclusion probabilities. For instance, consider $\pi_1.$ Because subsets $\alpha,\beta,\delta,\zeta$ are those that include $1,$ we may sum their chances $k/12$ to obtain

$$\pi_1 = \frac{1 + 1 + 3 + 2}{12} = \frac{7}{12}.$$

Notice that $\pi_{ii}=\pi_i.$ Generally,

$$\pi_{i,j} = \sum_{S:\{i,j\}\subseteq S} \Pr(S).$$

Here are the point inclusion and joint inclusion probabilities in the example as computed this way.

$$\begin{array}{cc} i,j & \pi_{ij} \\ \hline 0,0 & \frac{5}{12}\\ 1,1 & \frac{7}{12}\\ 2,2 & \frac{7}{12}\\ 0,1 & \frac{2}{12}\\ 0,2 & \frac{3}{12}\\ 1,2 & \frac{4}{12} \end{array}$$

As we saw in the preceding section on correlations, the joint inclusion probabilities yield formulas for expectations, variances and covariances of any random variables created from the indicator $\mathbf I.$ These formulas are the basis of variance and standard error estimates for complicated surveys involving unequal inclusion probabilities and nonzero correlations (created, for instance, by stratification and other forms of hierarchical sampling schemes).


Code

Often, seeing programming instructions to carry out computations can be revealing. The following R code performs all the calculations described here for the running example. It then simulates $10^7$ such random sets and uses those results to estimate properties of the process. Among other things, it estimates the mean and covariance as

$$E[\mathbf I] = \frac{1}{12}(5,7,7);\quad \operatorname{Cov}(\mathbf I) = \frac{1}{144}\pmatrix{35 & -11& 1\\ -11 & 35 & -1 \\ 1 & -1 & 35},$$

agreeing with all the example results.

https://en.wikipedia.org/wiki/Incidence_algebra explains the meanings and computations of the Zeta and Mobius arrays used to convert between the $k$ and $F$ columns in the first table.

#
# A sample space.
#
Omega <- c("alpha", "beta", "gamma", "delta", "epsilon", "zeta", "eta", "theta")
#
# The sets.
#
Sets <- list(alpha=c(0,1,2), beta=c(0,1), gamma=c(0,2), delta=c(1,2),
             epsilon=0, zeta=1, eta=2, theta=c())
#
# Indicator functions.
#
I <- as.matrix(expand.grid(0:1, 0:1, 0:1))[c(8, 4, 6, 7, 2, 3, 5, 1), ]
rownames(I) <- Omega
colnames(I) <- paste0("I", 0:2)
#
# A probability distribution.
#
k <- c(1,1,2,3,1,2,1,1); names(k) <- Omega
p <- k / sum(k)
#
# Set inclusion probabilities.
#
Zeta <- matrix(0, length(Omega), length(Omega), dimnames=list(Omega, Omega))
for (i in seq_along(Omega)) {
  for (j in i:length(Omega)) {
    Zeta[i, j] <- min(I[i,] >= I[j,])
  }
}
FF <- Zeta %*% p; colnames(FF) <- "F"
#
# Show how to compute the probability distribution from the inclusion probabilities.
#
Mobius <- solve(Zeta)
Pr <- Mobius %*% FF; colnames(Pr) <- "Pr" 
#
# Display the first table.
#
df <- data.frame(Omega, I, k, F=round(12*FF,2), Pr=round(12*Pr, 2))
names(df) <- c("Omega", "I0", "I1", "I2", "k", "12*F", "12*Pr")
(df)
#
# Simulate the process.
#
set.seed(17)
S <- sample(Omega, 1e7, replace=TRUE, prob=p)
#
# Show the first few sets generated.
#
(Sets[head(S)])
#
# Estimate means, the covariance matrix, and the correlation matrix.
#
mu <- colMeans(I[S, ])
Sigma <- cov(I[S, ])
Rho <- cor(I[S, ])

round(mu*12, 2)     # Compare to the worked example
round(Sigma*144, 1) # Ditto
round(Rho, 3)       # Ditto
#
# Point inclusion probabilities.
#
Pi <- crossprod(I[S,]) / length(S)
round(Pi*12, 2)
```
$\endgroup$
1
  • 1
    $\begingroup$ Thank you so much for the informative answer and code makes complete sense! $\endgroup$ Feb 8, 2022 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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