# what is this called? “difference of the function is less than the function of the difference”

Given:

• 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).

Why

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.

Examples

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)

-
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