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

miniliv4 2022-09-30 Answered
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 ( ( 2 n 2 n 1 ) / n ! ) 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 ( i ) = ( ( 2 i 2 i 1 ) / i ! ) 2 , the probability of having i points in convex position.
And the expected number of points be in convex position can be achieved via i = 1 n ( n i ) P ( i )
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

Expert Community at Your Service

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

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Samantha Braun
Answered 2022-10-01 Author has 9 answers
Step 1
You've computed the expected number of subsets of points in convex position. For example, when n 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 ( X k ) ( n k ) ( 1 k ! ( 2 k 2 k 1 ) ) 2
Step 2
So we get an upper bound on the expectation of X:
E ( X ) = k = 1 n P ( X k ) k = 1 n min ( 1 , ( n k ) ( 1 k ! ( 2 k 2 k 1 ) ) 2 )
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 ( n k ) ( 1 k ! ( 2 k 2 k 1 ) ) 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.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

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

You might be interested in

asked 2022-11-08
An upper bound on the expected value of the square of random variable dominated by a geometric random variable
Let X and Y be two random variables such that:
1. 0 X Y
2. Y is a geometric random variable with the success probability p (the expected value of Y is 1/p).
I would be grateful for any help of how one could upperbound E ( X 2 ) in terms of p.
asked 2022-09-25
Probability distribution of a random variable
We roll a dice until we get 6. Knowing that we have rolled 10 times, evaluate the probability that in the next 20 rolls there will be no 6. So in this question are we supposed to use binomial distribution or geometric distribution?
asked 2022-08-16
Geometric probability expressed as a geometric series
Suppose that we want to show that P ( X n ) = ( 1 p ) n
Where X is a geometric random variable with probability of success p.
P ( X > n ) can be written as a geometric series as follows:
Σ X = n + 1 ( 1 p ) n 1 = ( 1 p ) n
But how do I proof this? What is a and r in this particular geometric series?
asked 2022-11-07
Why is this not a geometric distribution?
A recruiting firm finds that 20% of the applications are fluent in both English and French. Applicants are selected randomly from a pool and interviewed sequentially. Find the probability that at least fi ve applicants are interviewed before fi nding the fi rst applicant who is fluent in both English and French
The answer for this question is ( 0.8 ) 5 .
asked 2022-08-10
Two points are chosen at random on a line segment of length 9 cm. The probability that the distance between these 2 points is less than 3 cm is?
asked 2022-07-17
What is the expected volume of the simplex formed by n + 1 points independently uniformly distributed on S n 1 ?
asked 2022-07-20
Calculate the probability of circuit breakage.
A breakage of the electrical circuit occurs if either an element K 1 or both elements K 2 and K 3 break. The elements K 1 , K 2 , K 3 break independently of each other with probabilities respectively 0.3, 0.2, 0.1. Calculate the probability of circuit breakage.

New questions