The Art Gallery Guardian

Isotonic function preserving grid in [0,1][0,1]


Definition1

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

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

Theorem2

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

Proof

It's easy to see that φ\varphi is a increasing function. Let the points in XX ordered as x0,x1,,xnx_0,x_1,\ldots,x_n. Let li=φ(xi)φ(xi1)l_i = |\varphi(x_i)-\varphi(x_{i-1})|. Note that

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

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

  3. i=1mli>i=n(m2)nli\sum_{i=1}^{m} l_i > \sum_{i=n-(m-2)}^{n} l_i for all mm, because mnxmx0>mnδ>m1n+2δ>xnxn(m2)\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 φ(xm)φ(x0)<φ(xn)φ(xn(m2))\displaystyle |\varphi(x_m)-\varphi(x_{0})|<|\varphi(x_{n})-\varphi(x_{n-(m-2)})|.

Combine the relations above, we have mni=1mli>i=n(m2)nlim1n\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 i=1mli=φ(xm)\sum_{i=1}^m l_i = \varphi(x_m), so m/nxm>m/nδm/n\geq x_m>m/n-\delta, m/nφ(xm)>(m1)/nm/n\geq \varphi(x_m)>(m-1)/n. Since δ\delta is small, we have xiφ(xi)<1/n|x_i-\varphi(x_i)|<1/n.

Posted by Chao Xu on .
Tags: analysis.