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. \[ \sum_{i=1}^n l_i = 1 \]

  2. \[|x_i-x_{i-1}|<\frac{1}{n}-\frac{\delta}{2^i}<|x_{i+1}-x_i|\] thus by isotonic function \[|\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 \[|\varphi(x_m)-\varphi(x_{0})|<|\varphi(x_{n})-\varphi(x_{n-(m-2)})|\].

Combine the relations above, we have \[ \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.