Consider a non-decreasing discrete function $f$ defined over $\{0,1,\ldots,n\}$.
Let $g$ be the least concave majorant of $f$. Assume that for some $i\in \{1,\ldots,n-1\}$, $g(i)\neq f(i)$. How to prove that $g$ is linear over $\{i-1, i ,i+1 \}$, i.e., $g(i)-g(i-1) = g(i+1)-g(i)$?
I tried the following: Suppose that $g(i)-g(i-1) \neq g(i+1)-g(i)$, then we must have that $g(i)$ is above the line that interpolates $g(i-1)$ and $g(i+1)$ by concavity of $g$. Then, I think that one might be able to find a contradiction with the fact that $g$ is the least concave majorant but cannot formalize it.
Best Answer
If $g(i) \ne f(i)$ for some $i \in \{ 1, \ldots, n-1 \}$ then $g(i) > f(i)$ since $g$ is a majorant of $f$. Now assume that $g$ is not linear on $[i-1, i+1]$, i.e. it is strictly concave on that interval: $$ g(i) > \frac 12 (g(i-1)+g(i+1)) \, . $$
The idea is that we can decrease the value of $g(i)$ slightly so that $g$ is still a concave majorant of $f$. More precisely: Define the function $h: \{ 0, \ldots , n \} \to \Bbb R$ by $$ h(j) = \begin{cases} g(j) & \text{if } j \ne i \, ,\\ \max\left(\frac 12 (g(i-1)+g(i+1)), f(i) \right) & \text{if } j = i \, . \end{cases} $$ $h$ is concave, is a majorant of $f$, and satisfies $h(i) < g(i)$. This is a contradiction to the minimality of $g$.
Proof that $h$ is concave: For $j=i$ we have $$ h(i) \ge \frac 12 (g(i-1)+g(i+1)) = \frac 12 (h(i-1)+h(i+1)) $$ and for $j \ne i$ we have $$ h(j) = g(j) \ge \frac 12 (g(j-1)+g(j+1)) \ge \frac 12 (h(j-1)+h(j+1)) \, . $$
Remark: The condition that $f$ is non-decreasing is not needed for this conclusion.