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 impossibleCan someone help me where did I do wrong?

Question

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 impossibleCan someone help me where did I do wrong?

Samantha Braun · Accepted Answer

Step 1You&#039;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    −  1Let 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 2So 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&#039;s a reasonable to guess that X will be bigger than k with high probability.

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

Answered question

Answer & Explanation

New Questions in High school geometry