# Expected number of uniformly random points in unit square is in convex position. If n points are uniformly generated in a unit square, following famous Erdős–Szekeres theorem. The probability of them be in convex position is (((2n-2),(n-1))//n!)^2

Expected number of uniformly random points in unit square is in convex position.
If n points are uniformly generated in a unit square, following famous Erdős–Szekeres theorem. The probability of them be in convex position is ${\left(\left(\genfrac{}{}{0}{}{2n-2}{n-1}\right)/n!\right)}^{2}$
My interest is to find the expected number of points be in convex position, and I am enumerating i points in the convex position and add all the possible is.
Here is what I did, $P\left(i\right)={\left(\left(\genfrac{}{}{0}{}{2i-2}{i-1}\right)/i!\right)}^{2}$, the probability of having i points in convex position.
And the expected number of points be in convex position can be achieved via $\sum _{i=1}^{n}\left(\genfrac{}{}{0}{}{n}{i}\right)\ast P\left(i\right)$
And I was using WolframAlpha to get an idea of this number, for some reason the expected number is bigger than n, which is impossible
Can someone help me where did I do wrong?
You can still ask an expert for help

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Samantha Braun
Step 1
You've computed the expected number of subsets of points in convex position. For example, when $n\le 3$ all ${2}^{n}-1$ nonempty subsets are in convex position, so the sum equals ${2}^{n}-1$
Let X be the maximum cardinality of all sets in convex position. By union bound on all sets of size k we have:
$P\left(X\ge k\right)\le \left(\genfrac{}{}{0}{}{n}{k}\right){\left(\frac{1}{k!}\left(\genfrac{}{}{0}{}{2k-2}{k-1}\right)\right)}^{2}$
Step 2
So we get an upper bound on the expectation of X:
$\begin{array}{rl}E\left(X\right)& =\sum _{k=1}^{n}P\left(X\ge k\right)\\ & \le \sum _{k=1}^{n}min\left(1,\left(\genfrac{}{}{0}{}{n}{k}\right){\left(\frac{1}{k!}\left(\genfrac{}{}{0}{}{2k-2}{k-1}\right)\right)}^{2}\right)\end{array}$
Getting a lower bound is more complicated, I think this upper bound should be reasonably tight. Why? Most of the sum on the right hand side comes from the terms which equal 1, the terms less than 1 decay rapidly. The expected number of sets of size k in convex position equals $\left(\genfrac{}{}{0}{}{n}{k}\right){\left(\frac{1}{k!}\left(\genfrac{}{}{0}{}{2k-2}{k-1}\right)\right)}^{2}$, so when this quantity is much bigger than 1, it's a reasonable to guess that X will be bigger than k with high probability.