Suppose $X$ is an $N$-dimensional random variable $X := [X_1 \; X_2 \; \cdots \; X_N]$ such that all entries can either be 0 or 1 while satisfying the following:

(i) $\mathbb{P}(X_i = 1) = p_i \; \; , \; \; \forall i$

(ii) $p_1 + p_2 + \cdots + p_N \le c$

where $c$ is some positive integer such that $c < N$.

Can we ensure the following deterministic constraint from the probabilistic constraint in (ii)?

(iii) $\mathbb{1}_{\{X_1 = 1\}} + \mathbb{1}_{\{X_2 = 1\}} + \cdots + \mathbb{1}_{\{X_N = 1\}} \le c \; \;$ with probability 1

Obviously if (iii) is true, (ii) is satisfied (we can take expectation from (iii) and (ii) will follow). I need to see whether there are cases that (ii) would imply (iii) too?

I can give an example for the case where $N=2$ and $c=1$. So, suppose we have random variable $Y$ such that:

$Y=1 \;$ if $\;X_1 = 1 \; ,\; X_2 = 0$

$Y=2\;$ if $\;X_1 = 0 \; ,\; X_2 = 1$

$Y=3\;$ if $\;X_1 = 0 \; ,\; X_2 = 0$

and so we have

$\mathbb{P}(Y = 1) = p_1$ and $\mathbb{P}(Y = 2) = p_2$ and $\mathbb{P}(Y = 3) = 1 - p_1 - p_2$ such that $p_1 + p_2 \le 1$. Thus, the constraint $\mathbb{1}_{\{X_1 = 1\}} + \mathbb{1}_{\{X_2 = 1\}} \le c \; \;$ can be written as:

$\mathbb{1}_{\{Y = 1\}} + \mathbb{1}_{\{Y = 2\}} \le c \; \;$

which is satisfied because $Y$ is either 1 or 2 and we have that $p_1 + p_2 \le 1$.

Is there a way to extend this to $N$-dimensional case?


1 Answer 1


Your condition (ii) is too weak on its own to constrain the degrees of freedom you have in the problem. Hence it is not hard to construct examples where (iii) is true and where it is not. The idea behind these examples is simple: If you want to show that (iii) is false you need to make sure that many of the $X_i$ take the value one on the same non-null set from the underlying sigma algebra. If you want to find cases where (iii) is true make sure this does not happen, i.e. if a single $X_i$ is one, all the others are zero.

Simple counterexample to (ii) implies (iii):

Take all $X_i$ to be identical. More subtle counterexample: Let $\Omega=\{\omega_0, \ldots, \omega_{N+1}\}$. Choose any $\epsilon>0$ with $\epsilon < \min\{p_1,\ldots,p_N, \frac{1 - \sum p_j}{N+1}\}$. Define $P$ by $P(\omega_0)=\epsilon$, $P(\omega_j)=p_j-\epsilon$ for $1\le j\le N$ and $P(\omega_{N+1})=1 - (N+1)\epsilon - \sum p_j$. Now set $X_i(\omega_o)=X_i(\omega_i)=1$ for $1\le i\le N$ and $X_i(\omega_j)=0$ in all other cases.

Simple example where (iii) holds

Let $\Omega=\{\omega_1, \ldots, \omega_{N+1}\}$. Set $X_i(\omega_j) = 1$ if $i=j$ and zero otherwise. Define $P(\{\omega_i\})$ so that it is a measure and (i) holds.

  • $\begingroup$ You are right that (ii) does not imply (iii) in general; but are there cases where this holds true? $\endgroup$ Jun 16, 2016 at 23:30
  • $\begingroup$ sure, see my edits $\endgroup$
    – g g
    Jun 17, 2016 at 5:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .