MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $n$ and $k$ be two positive integers. Let $S = \{ \mathbf{p} \in \mathbb{R}^k : \mathbf{p} \geq 0, \sum_{i=1}^k p_i = 1 \}$ (i.e., a simplex). Consider a function $\mathbf{f}:\mathbb{Z}^k \rightarrow \mathbb{R}^k$. And from $\mathbf{f}$ we may define function $\mathbf{g}: S\subset \mathbb{R}^k \rightarrow \mathbb{R}^k$ as follows $$\mathbf{g}(\mathbf{p}) = \mathbb{E}[\mathbf{f}(\mathbf{X})], \quad \mathbf{X}\sim \text{Multinomial}(n,\mathbf{p}).$$ Here $\mathbf{X}$ is a random vector that follows the multinomial distribution determined by the number of trials $n$ and probabilities $p_1,p_2,\dots,p_k$.

Conjecture: If $\mathbf{f}$ is monotone, that is, $$ (\mathbf{x}-\tilde{\mathbf{x}})^T (\mathbf{f}(\mathbf{x})-\mathbf{f}(\tilde{\mathbf{x}})) \geq 0\quad \forall \mathbf{x}, \tilde{\mathbf{x}} \in \mathbb{Z}^k,$$ then $\mathbf{g}$ is also monotone, i.e., $$ (\mathbf{p}-\tilde{\mathbf{p}})^T (\mathbf{g}(\mathbf{p})-\mathbf{g}(\tilde{\mathbf{p}})) \geq 0\quad \forall \mathbf{p}, \tilde{\mathbf{p}} \in S.$$

Remark: The above result should hold in the following two special cases (I omit the proofs) -

  1. The function $\mathbf{f}$ is affine, namely, $\mathbf{f}(\mathbf{x})=G\mathbf{x}+\mathbf{b}$ for some matrix $G$ and vector $\mathbf{b}$.

  2. The function $\mathbf{f}$ is "separable", meaning that $$\mathbf{f}(\mathbf{x}) = (f_1(x_1), \dots, f_k(x_k))^T$$ for some non-decreasing scalar functions $f_1(\cdot), \dots, f_k(\cdot)$.

But does it hold in the general case?

share|cite|improve this question
@daizhuo - can you give an example of a monotone function, possibly of interest, that is not affine or separable? – ronaf Jan 22 '11 at 4:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.