2
$\begingroup$

Let $p_1,p_2,...,p_n$ are given probabilities. ($\sum_{i=1}^n p_i =1, p_i \geq 0 $). Is there any distribution, which picks $k\leq n$ distinct elements from $1,2,...,n$ such that $P(i \in S) = k p_i$ and $(i\neq j)$ $P(i \in S, j \in S) = c p_i p_j$, where S is our distribution realization and $c$ is some constant?

$\endgroup$
1
$\begingroup$

Usually not. Denote $f_i=\mathbb{1}_{i\in S}$, then $\mathbb{E} f_i=\mathbb{E} f_i^2=kp_i$, $\sum f_i\equiv k$, $\mathbb{E} f_if_j=cp_ip_j$ if $i\ne j$. Thus $$k^2p_i=k\mathbb{E} f_i=\mathbb{E} \sum_j f_if_j=cp_i(1-p_i)+kp_i.$$ If $p_i>0$, this gives $c(1-p_i)=k^2-k$, and if $p_i\ne p_j$ and $k>1$ this gives a contradiction.

$\endgroup$
  • $\begingroup$ To complement this excellent answer, note that the desired conclusion will obviously hold by symmetry when the $p_i$'s are equal to one another and $S$ is uniformly distributed on the set of all subsets of size $k$. $\endgroup$ – Iosif Pinelis Mar 27 '18 at 0:18

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.