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

Definition1

A function $φ : X \to Y$ is isotonic if $∥ x - y ∥ < ∥ w - z ∥ ⟹ ∥ φ (x) - φ (y) ∥ < ∥ φ (w) - φ (z) ∥$ for all $x, y, z, w \in X$ .

A sequence of points $x_{0}, x_{1}, \dots, x_{n}$ is called $δ$ -grid if $δ < \frac{1}{5 n}$ , $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{δ}{2 ^{i - 1}}, \frac{1}{n} - \frac{δ}{2 ^{i}})$ . Note this imply $x_{n} - x_{n - 1} > \frac{1}{n}$ .

Theorem2

Let $X$ be a $δ$ -grid of $n$ points where $δ < 2^{- n}$ . $φ : X \to [0, 1]$ is a isotonic function such that $φ (0) = 0$ and $φ (1) = 1$ , then $∣ x_{i} - φ (x_{i}) ∣ < 1/ n$

Proof

It’s easy to see that $φ$ is a increasing function. Let the points in $X$ ordered as $x_{0}, x_{1}, \dots, x_{n}$ . Let $l_{i} = ∣ φ (x_{i}) - φ (x_{i - 1}) ∣$ . Note that

$i = 1 \sum n l_{i} = 1$
$∣ x_{i} - x_{i - 1} ∣ < \frac{1}{n} - \frac{δ}{2 ^{i}} < ∣ x_{i + 1} - x_{i} ∣$ thus by isotonic function $∣ φ (x_{i}) - φ (x_{i - 1}) ∣ < ∣ φ (x_{i + 1}) - φ (x_{i}) ∣$ . This is just $l_{i} < l_{i + 1}$ .
$\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} - δ > \frac{m - 1}{n} + 2 δ > ∣ x_{n} - x_{n - (m - 2)} ∣$ , thus $∣ φ (x_{m}) - φ (x_{0}) ∣ < ∣ φ (x_{n}) - φ (x_{n - (m - 2)}) ∣$ .

Combine the relations above, we have $\frac{m}{n} \geq i = 1 \sum m l_{i} > i = n - (m - 2) \sum n l_{i} \geq \frac{m - 1}{n}$

But $\sum_{i = 1}^{m} l_{i} = φ (x_{m})$ , so $m / n \geq x_{m} > m / n - δ$ , $m / n \geq φ (x_{m}) > (m - 1) / n$ . Since $δ$ is small, we have $∣ x_{i} - φ (x_{i}) ∣ < 1/ n$ .

Posted by Chao Xu on 2014-11-04.

Tags: analysis.

Isotonic function preserving grid in [0,1]

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