The Art Gallery Guardian

Isotonic function preserving grid in [0,1]


Definition1

A function \varphi:X\to Y is isotonic if \|x-y\| < \|w-z\| \implies \|\varphi(x)-\varphi(y)\| < \|\varphi(w)-\varphi(z)\| for all x,y,z,w\in X.

A sequence of points x_0,x_1,\ldots,x_n is called \delta-grid if \delta<\frac{1}{5n}, x_0=0, x_n=1 and for all 1 \leq i\leq n-1, we have x_i-x_{i-1} \in (\frac{1}{n}-\frac{\delta}{2^{i-1}},\frac{1}{n}-\frac{\delta}{2^i}). Note this imply x_n-x_{n-1}>\frac{1}{n}.

Theorem2

Let X be a \delta-grid of n points where \delta<2^{-n}. \varphi: X\to [0,1] is a isotonic function such that \varphi(0)=0 and \varphi(1)=1, then |x_i - \varphi(x_i)|<1/n

Proof

It's easy to see that \varphi is a increasing function. Let the points in X ordered as x_0,x_1,\ldots,x_n. Let l_i = |\varphi(x_i)-\varphi(x_{i-1})|. Note that

  1. \displaystyle \sum_{i=1}^n l_i = 1

  2. \displaystyle |x_i-x_{i-1}|<\frac{1}{n}-\frac{\delta}{2^i}<|x_{i+1}-x_i| thus by isotonic function \displaystyle |\varphi(x_i)-\varphi(x_{i-1})|<|\varphi(x_{i+1})-\varphi(x_i)|. This is just l_i<l_{i+1}.

  3. \sum_{i=1}^{m} l_i > \sum_{i=n-(m-2)}^{n} l_i for all m, because \frac{m}{n}\geq |x_m-x_0| > \frac{m}{n}-\delta > \frac{m-1}{n}+2\delta>|x_n - x_{n-(m-2)}|, thus \displaystyle |\varphi(x_m)-\varphi(x_{0})|<|\varphi(x_{n})-\varphi(x_{n-(m-2)})|.

Combine the relations above, we have \displaystyle \frac{m}{n} \geq \sum_{i=1}^m l_i > \sum_{i=n-(m-2)}^{n} l_i \geq \frac{m-1}{n}

But \sum_{i=1}^m l_i = \varphi(x_m), so m/n\geq x_m>m/n-\delta, m/n\geq \varphi(x_m)>(m-1)/n. Since \delta is small, we have |x_i-\varphi(x_i)|<1/n.

Posted by Chao Xu on 2014-11-04.
Tags: analysis.