Conditions under which a given scheme converges - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T04:16:15Z http://mathoverflow.net/feeds/question/82122 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82122/conditions-under-which-a-given-scheme-converges Conditions under which a given scheme converges Jennifer Gao 2011-11-28T22:34:30Z 2011-12-13T00:22:12Z <p>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</p> <p>$\Delta_{n-1} = {x\in \mathbb{R}^n : \sum_i x_i = 1, x_i \geq 0}$.</p> <p>Suppose that this function $f$ has the following "nice" properties:</p> <ol> <li>$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$.</li> <li>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$.</li> <li>$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 &lt; f(\tilde{x})_i$ (with no other conditions on the other elements).</li> </ol> <p>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)$.</p> <p>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,</p> <p><a href="http://mathoverflow.net/questions/67318/map-from-simplex-to-itself-that-preserves-sub-simplices" rel="nofollow">http://mathoverflow.net/questions/67318/map-from-simplex-to-itself-that-preserves-sub-simplices</a></p> <p>it seems that my map $f$ must be surjective, thus the barycenter of the simplex is at least in the image of $f$. Thanks!</p> http://mathoverflow.net/questions/82122/conditions-under-which-a-given-scheme-converges/82127#82127 Answer by Will Sawin for Conditions under which a given scheme converges Will Sawin 2011-11-28T23:26:54Z 2011-11-28T23:26:54Z <p>First you want to make sure your vector field itself is well-defined. What do you intend to do when $f_i=f_j$?</p> <p>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.</p> <p>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)$.</p> <p>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.</p>