Consider a discrete probability space $\left( S, F, P\right)$, where $S = \{ 1, 2, \ldots, N \}$.

Consider the set $$S' := \mathcal{P}(S) \setminus \{ \varnothing\} = \{ \{ 1\}, \{ 2\}, \ldots, \{N\}, \{ 1, 2 \}, \{1, 3\}, \ldots, \{N-1, N\}, \{1, 2,3\}, \{1, 2, 4\}, \ldots\}$$ which is the power set of $S$ taking away the empty set.

Consider a function $f: S' \rightarrow \mathbb{R}$ with the following properties. (Not sure if the second is needed.)

  1. $f$ is monotone: $X \subset Y \ \Rightarrow \ f(Y) \geq f(X)$

  2. $f$ is determined by at most $2 \leq n \ll N$ elements:

for all $X \subset S'$, there exists $x_1, ..., x_{ \min\{n, |X|\} } \in X$ such that $f(X) = f(\{ x_1, ...., x_{ \min\{n, |X|\} } \})$

Say if the following inequality holds for all $k \geq n$. (If not, say under what additional conditions on $f$ it is non-negative.)

$$ \sum_{ i_1, ..., i_k = 1 }^N \sum_{i_{k+1} = 1 }^N \sum_{j=1}^N \\ \left( 1\left[ f( {i_1}, ..., i_k, j ) > f( {i_1}, ..., {i_k} ) \right] - 1\left[ f( {i_1}, ..., i_k, {i_{k+1}}, j ) > f( {i_1}, ..., i_k, {i_{k+1}} ) \right] \right) \\ P(i_1) \cdots P(i_{k+1}) P(j) \ \geq 0$$

where $1\left[ \cdot \right] \in \{0,1\}$ denotes the indicator function. The sums with the probabilities $P_{i_1}, ..., P_{j}$ may be replaced by probability integrals for ease of notation.

Comment. Since $f$ is monotone, the idea is that on average $f( {i_1}, ..., i_k, j ) > f( {i_1}, ..., {i_k} )$ is more likely than $f( {i_1}, ..., {i_k}, {i_{k+1}}, j ) > f( {i_1}, ..., i_k, {i_{k+1}} )$.

Variation. Say if there exists $\bar{k}$ such that the above inequality holds for all $k \geq \bar{k}$.


The inequality is equivalent to the following statement.

Let $(X_k)_{k\geqslant 1}$ be i.i.d. with support a finite set $S$. Let $A_k=\{X_n\mid1\leqslant n\leqslant k\}$, thus $A_k$ is a random subset of $S$, and $p_k=P[f(A_{k+1})\gt f(A_k)].$

Then the sequence $(p_k)_{k\geqslant 1}$ is nonincreasing.

Counterexamples abund. For instance, choose some $Z\subseteq S$ with size at least $3$ and define $f$ by $f(X)=1$ if $Z\subseteq X$ and $f(X)=0$ otherwise. Then $f$ fulfills every condition mentioned, but $p_k=0$ for every $k\leqslant|Z|-2$ while $p_k\gt0$ for every $k\geqslant|Z|-1$.

  • $\begingroup$ Do you think it is true that there exists $\bar{k}$ such that the inequality holds for all $k \geq \bar{k}$? $\endgroup$ – user693 Jan 16 '14 at 10:09
  • $\begingroup$ The reason why I am asking this is that for $k$ large, the sequence $\{X_k\}$ mentioned in your answer will take all the values $\{1, 2, ..., N\}$ with high probability, so that $p_k \rightarrow 0$. $\endgroup$ – user693 Jan 16 '14 at 10:16
  • $\begingroup$ What can we say for $k \geq n$ (where $n$ comes from the second property of $f$)? In your example, is $p_k$ non-increasing for all $k \geq 2$? $\endgroup$ – user693 Jan 16 '14 at 20:47
  • $\begingroup$ In [math.stackexchange.com/questions/640989/… I start from your formulation and add an assumption on $f$. $\endgroup$ – user693 Jan 16 '14 at 21:24

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.