# Generating a random monotonically increasing polynomial?

Given a polynomial $y : \mathbb{R} \mapsto \mathbb{R}$ of degree $p$: $$y(x) = \sum_{k=0}^p c_k\, x^k,$$ can a random set of coefficients $\{c_0, \cdots ,c_p\}$ be generated such that $y$ is monotonically increasing for all $x \in [0,1]$?

Alternatively, can a probabilistic bound on the monotonicity of $y$ be shown? For example, if $n$ tests of the nonnegativity of the slope of $y$ are made at different locations $\{x_1,\cdots, x_n\}$, can an upper bound be placed on the probability that $y$ is not monotonically increasing?

Finally, if $\epsilon$ is this bound, then can $\epsilon$ be written as a function of $n$ and $p$?

-
Well, if you force your coefficients to be all greater than 0 (say, they each follow an exponential distribution), your polynom will be monotonically increasing on $[0,1]$, and even on $\mathbb{R}^+$. – S4M Jul 18 '12 at 20:53
I'm sure (almost) you don't mean the domain of $y$ to be $\mathbb{R}^p$. As a function $y(x)$ maps $\mathbb{R}$ to $\mathbb{R}$, and even if some dependence on coefficients $c_i$ is intended, there are $p+1$ of those. $p$ must be odd for $y(x)$ to be monotone on all of $\mathbb{R}$; it's essentially asking that the derivative $y'(x)$ be nonnegative. The reduction to interval $[0,1]$ is similar. As far as a random such choice goes, we'd need to specify the probability distribution desired. – hardmath Jul 18 '12 at 21:11
If you are looking for a numerical technique, then you could select the coefficients 'randomly' and then check if the resulting polynomial is increasing (just check if the polynomial $y'$ is non-negative on $[0,1]$ by looking at the end points and real roots). – copper.hat Jul 18 '12 at 21:30
I've corrected the domain of $y$. I do have future plans to expand the problem to higher dimensions, but that was a typo. – david.smith Jul 19 '12 at 17:24

Perhaps a partial answer will help to focus the issue of defining a probability distribution governing "random" choice of polynomials.

The region of feasible polynomials, increasing on $[0,1]$ of degree (at most) $p \gt 0$ is unbounded in the coefficient space. For one thing any constant can be added to such a polynomial and obtain another; similarly any positive constant can be multiplied to give another feasible polynomial.

If the feasible region is unbounded, we cannot glibly appeal to "uniform" distribution of probability over the region. This motivates adding a couple of constraints that make the region bounded. If strongly monotone increasing is the intended meaning, then consider adding the normalizing requirements $y(0) = 0$ and $y(1) = 1$, i.e. that $y$ maps $[0,1]$ onto $[0,1]$.

Now the case $p = 1$ becomes trivial, since $y = x$ is the only feasible polynomial.

Moreover the tests proposed by the OP, showing monotonicity by sampling the polynomial at intermediate points $\{x_1,...,x_n\}$, can be carried out in a deterministic way with $n = p-1$.

Corrected: Consider as an illustration the case $p = 2$, quadratic polynomials. Sampling these at $x_1 = \frac{1}{2}$ gives a parameterization of the solutions with $y(x_1) \in [\frac{1}{4},\frac{3}{4}]$. If we wish, the probability distribution can be taken to make $x_1$ be uniform on that interval, or to accord with some other distribution. The feasible quadratics are convex combinations of $y_0(x) = x^2$ and $y_1(x) = 2x - x^2$.

Conjecture: Looking at the lower degree examples, the general degree (at most) $p$ case appears to be this:

$$y(x) = x^p + \sum_{k=1}^{p-1} c_k \binom{p}{k} x^{p-k} (1-x)^k$$

where $c_k \in [0,1]$ for $k=1,\ldots,p-1$, so that the normalized feasible polynomials can be parameterized by $[0,1]^{p-1}$, using perhaps a uniform distribution over that hypercube. Among other evidence this set of functions is conserved by the monotone-preserving symmetry $y(x) \mapsto 1 - y(1-x)$.

-
I think I've worked out the parameterization of the monotonic cubic polynomials on $[0,1]$, which is a product of two intervals: $y(x) = x^3 +3sx(1-x)^2 + 3tx^2(1-x)$ for $s,t \in [0,1]$. – hardmath Jul 23 '12 at 15:02