Conditions under which a given scheme converges

2011-11-28T22:34:30Z

I'm sorry in advance for how long this question is. Suppose I have a continuous function $f:\mathbb{R}^n \rightarrow \Delta_{n-1}$, where we think of the simplex $\Delta_{n-1}$ as the set

$\Delta_{n-1} = {x\in \mathbb{R}^n : \sum_i x_i = 1, x_i \geq 0}$.

Suppose that this function $f$ has the following "nice" properties:

$f$ is translation-invariant, in the sense that $f(x_1,\dots,x_n) = f(x_1+t,\dots,x_n+t)$ for all $t$.
For any point $x=(x_1,\dots,x_n)$, if we increase the $i$th entry of $x$, the corresponding $i$th entry of $f(x)$ approaches $1$. In other words, we have $\lim_{t \rightarrow \infty} f(x_1,\dots, x_i + t, \dots, x_n)_i = 1$.
$f$ has a "monotonicity property", in the following sense: If $x = (x_1,\dots,x_n)$ and $\tilde{x} = (x_1,\dots,x_i+t,\dots,x_n)$ where $t > 0$, then $f(x)_i < f(\tilde{x})_i$ (with no other conditions on the other elements).

Now, let's define a vector field $V:\mathbb{R}^n \rightarrow \mathbb{R}^n$ in the following way: at point $(x_1, \dots, x_n)$, we select the index(es) $i$ such that $f(x_1,\dots,x_n)_i$ is maximal. Then, we let $V(x_1,\dots,x_n)$ be a vector with $-1$ in the components corresponding to $i$, and $0$ everywhere else. So, for example, if $f(x_1,x_2,x_3) = (0.1, 0.7, 0.2)$, we'd have $V(x_1,x_2,x_3) = (0,-1,0)$.

My question now is: suppose we start at some point $x$ and "follow" this vector field $V$ (I hope that the notion of "following" a vector field is well-defined -- I don't even know if that is the case here). Are there any "nice" conditions under which I'm guaranteed to eventually end up at a point where $f(x) = (1/n ,\dots, 1/n)$? Using an argument that Neil Strickland gave in an earlier thread,

http://mathoverflow.net/questions/67318/map-from-simplex-to-itself-that-preserves-sub-simplices

it seems that my map $f$ must be surjective, thus the barycenter of the simplex is at least in the image of $f$. Thanks!

Answer by Will Sawin for Conditions under which a given scheme converges

2011-11-28T23:26:54Z

First you want to make sure your vector field itself is well-defined. What do you intend to do when $f_i=f_j$?

No matter what you choose, your vector field will not be continuous except for very special $f$, so following it will be hard to define, but not impossible.

Note the following nice fact: Everywhere but those places, your vector field has the property that when you follow it, $\max (f(x))$ decreases. If it still has that property elsewhere, then following it long enough should allow you to reach the minimum value of $f(x)$.

Now, what should you choose? Let's say the first two coordinates of $f(x)$ are equal, for simplicity. Then your vector field should probably be somewhere in between $(-1,0,0)$ and $(0,-1,0)$. Otherwise, following it would take you into a region where the vector field there immediately took you out of it. But we can strengthen that condition. Suppose infinitesimally decreasing $x_1$ makes $f_1$ fall faster than $f_2$, and vice versa. Then your vector field must cause $f_1$ and $f_2$ to still be equal. Otherwise, you would immediately hit a region where the change was different.

Conditions under which a given scheme converges - MathOverflow

Conditions under which a given scheme converges

Answer by Will Sawin for Conditions under which a given scheme converges