# Sampling with non-uniform probabilities

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?

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.
• 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$. – Iosif Pinelis Mar 27 '18 at 0:18