Skip to main content
2 of 2
formatting
YCor
  • 63.9k
  • 5
  • 187
  • 286

Median of cardinality of set union

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.