0
$\begingroup$

Let $U$ be an arbitrary finite universe (you can just think of it as $[N]=\{1,2,\ldots,N\}$), and $\mathbf{S} = (S_i)_{i \in [n]}$ ($S_i \subseteq U$) be the sets that we are drawing from. Define a counting function $f_{\mathbf{S}}$ as follows: $$f_{\mathbf{S}}(k) := \text{median} \Big\{\Big|\bigcup_{i \in I} S_i\Big|: I \in \binom{[n]}{k}\Big\}.$$ Informally, $f_{\mathbf{S}}(k)$ is the median number of elements if we draw $k$ sets in $\mathbf{S}$. My question is, is the ''second derivative'' of $f_{\mathbf{S}}(k)$ negative, formally is the function below decreasing: $$h_{\mathbf{S}}(x) := f_{\mathbf{S}}(x+1) - f_{\mathbf{S}}(x).$$ Bonus question, how would we prove this if it is mean instead of median?

Intuitively it should hold because the excepted number of elements added decreases when the field is ''crowded'', but I couldn't pinpoint an exact proof.

$\endgroup$

1 Answer 1

1
$\begingroup$

It turns out there is a (somewhat absurd) counterexample.

Consider $U=\{1,2,3,4,5,6\}$, $S_1 = \{1\}, S_2 = \{2\}, S_3 = \{3,4,5,6\}$. Then $f_{\mathbf{S}}(1) = \text{median}\{1,1,4\}=1$, yet $f_{\mathbf{S}}(2) = \text{median}\{2,5,5\}=5$.

$\endgroup$

You must log in to answer this question.

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