# Inequality with monotone functions on power set

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}$.

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$.
• Do you think it is true that there exists $\bar{k}$ such that the inequality holds for all $k \geq \bar{k}$? – user693 Jan 16 '14 at 10:09
• 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$. – user693 Jan 16 '14 at 10:16
• 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$? – user693 Jan 16 '14 at 20:47
• In [math.stackexchange.com/questions/640989/… I start from your formulation and add an assumption on $f$. – user693 Jan 16 '14 at 21:24