probability of making a convex function from random sampling So I just thought of this puzzle: let's say I have an $M \times N$ binary matrix, which I make by randomly (uniformly at random) choosing $K<= M \times N$ elements to set to $1$. Or alternatively just think of it as sampling random points in $R^2$ using a grid, and then let's say we connect the points (or $1$ entry of the matrix) to make a $1D$ graph. I.e. We randomly choose point $1$, then point $2$, connect point $1$ to $2$, choose point $3$, connect $2$ to $3$, etc. Repeating $K$ times. Then what is the probability I make a convex function? For this case, I would think we can make use of the idea of secant lines and how for a convex function they are above the graph.
Or if you want for simplicity, to avoid some problems with creating graphs of functions, we can say the sampling procedure is simplified to sample exactly $1$ point from $col1$, then $1$ pt from $col2$, etc. to $colN$. Connections made between consecutive samples only. Then this avoid problems with the graph being multiple valued, so it is a function from $R$ to $R$. Then what is the probability I create a convex function?
Combinatorially exact expression, or reasonable approximation, would be acceptable.
As a small 1st step, the denominator (total number possible samplings) in the 1st case will be $(MN)*(MN-1)*...*(MN-K+1$), VS. in the 2nd simplified case it is $M^N$.
 A: To clarify, I'll consider the following version of your problem: What's is the probability that $n$ points drawn uniformly at random from a parallelogram are in convex position ?
Such problems have collectively come to be known as Sylvester's problem,
 and [Vatr 1994] computed
$$p(n, \text{paralleogram}) = \left(\frac{1}{n!}{2n-2\choose n - 1}\right)^2.
$$
Note that as you'd expect, this probability is asymptotically $0$. There are also explicit results for triangles and discs. A good survey of the subject can be found here.
In general, one can show [Barany $\le 2001$] that, for any convex subset $C$ of the plane,
$$
\lim_{n \rightarrow \infty} n^2 p(n, C)^{1/n} = e^2\alpha(C)^3/4,
$$
where $\alpha(C)$ is the affine perimeter of $C$; $\alpha(C)$ vanishes on convex polyhedral sets and is positive on convex bodies with twice continuously differentiable boundary, e.g discs. As an immediate corollary, one gets
$$
p(n,\text{polygon}) = o(n^{-2n}).
$$
To conclude, one can also consider the more general question: What is the probability that the convex hall of $n$ points drawn uniformly randomly from $C$ has $k$ vertices ?
With an explicity formula, [Butcha $\le 2006$] solves this problem for $C = \text{triangle}$.
