I am working on convex polygons & algorithms among points in general position and I'm wondering if it's valid approach to the problem using probabilty or randomness. Let me explain briefly.
Let's assume $V$ is a set $n$ points in a general-position (no three pionts on the same line). Then, choose a random ordered subset $X$ of these points $X = (x_1,x_2,x_3,… ,x_k)$ to form a polygon. For each edge of the polygon, namely consecutive pair of points $e_i = (x_i,x_{i+1})$, if all the points in $X-\{x_i,x_{i+1}\}$ are on the either side of the edge then $X$ is in convex position. Let's denote the probabilty of having this case for first edge as $p_1$ which is easy to evaluate for sufficently large n. $$p_1 \to \frac{1}{2^{k-3}}+$$ But since the valid side of the other edges is set, then for the remaining cases for $i >1$, $$P_i \to \frac{1}{2^{(k-2)}}$$ according to my observation.
Please also note that for any $j < i$, $p_i$ and $p_j$ are independent events from each other. When we try to compute the conditional probability I observe that $$p_1 \cap p_2 \cap ... \cap p_{i-1} | p_i = p_i$$. What I mean is that, assuming that all $p_1,..,p_i$ are holds then the the problem remains same, that is in the worst case halving the remaining points. In this iterative random process each edge divides the remaning points as valid ones and invalid ones.Then the probability of having $X$ in convex position is, let's say $p_X$
$$p_X = \prod\limits_{i = 1}^{k} p_{i} \to \frac{1}{2^{(k-3)+(k-2)(k-1)}} $$
The number of distinct $k$ ordered subset in $n$ points is exactly $\frac{P(n,k)}{k}$. So the expected number of valid $X$ convexes in $n$ points is $$E_{convex(n,k)} \to \frac{P(n,k)}{k.2^{(k-2)k-1}} $$
it is easy to see that
$$ n > 2^{k-2}+k/2 -1 \implies E_{convex(n,k)} > 1 $$
This is the point I got stuck. Is that result really implies the existence of convex polygon at given conditions above?
Hopefully I'm not mixing apples and oranges.
The method seems valid. But after careful consideration, nearly all $p_i$ pairs are interdependent, clearly limiting each other's result set. Unfortunately the result is not valid.