Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.


  • a metric $d$
  • an aggregate function $f$
  • some sets (or multisets or random variables) $X$,$Y$

What do we call:

  1. $d(f(X),f(Y)) \leq f( [d(X_0,Y_0) \cdots d(X_n,Y_n)] )\ \forall\ k\in[0,1), X,Y$
  2. $d(f(X),f(Y))\leq \max_i d(X_i,Y_i)\ \forall X,Y$

Similar definitions:

  • $f$ is a contraction mapping: $d(f(x),f(y))\leq k\ d(x,y)\quad{}\forall x, y$

  • $f$ is subadditive: $f(x+y)\leq f(x)+f(y)\quad{}\forall x, y$

the similarity being two operations "commute" (but with inequality not equality).


You can solve a Markov decision process for some "state reducer" and some "action reducer", two reducing operations each satisfying [2] (otherwise, the iterative algorithm has no proof of convergence). different pairs of "MDP reducers" (what i call "satisfying property 2") give us different solutions.


Expectation and maximum/minimum are "mdp reducers" $|E[X] - E[Y]| \leq \max_i |X_i - Y_i|$
$|\max_i X_i - \max_i Y_i| \leq \max_i |X_i - Y_i|$

solving an mdp given mean for the state reducer and max for the action reducer answers "what's the best i can do in expectation?"

if i have a name for "mdp reducer", i can get a list of them, and play around with them, and find new interpretations i.e. answer different questions i.e. solve different problems.

does [1] have a name? does [2] have a name? if not, what are some functions that satisfy [2]?

(cross posted on mathoverflow)

share|improve this question
Your [2] is just the condition of being a metric map, using the $\infty$-product metric on the domain, isn't it? –  Henning Makholm Oct 3 '12 at 22:25
Simul-posted to MathOverflow, mathoverflow.net/questions/108381/… without notice to either site. Bad, bad. –  Gerry Myerson Oct 3 '12 at 23:53
@GerryMyerson i didn't know that was bad etiquette. what should i do? –  sam boosalis Oct 4 '12 at 1:51
I think I've already done what had to be done, namely, notifying each site that the question has been asked on the other. Anyone wanting to answer now knows to check the other site first to see what's already been done. I can't think of anything else to do. –  Gerry Myerson Oct 4 '12 at 4:00
add comment

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.