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.

New contributor
kingoyster is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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$.

New contributor
kingoyster is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

You must log in to answer this question.

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