## What is the expected value for this

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

If there are $8$ random points in the plane whose horizontal coordinate and vertical coordinate are uniformly distributed on the open interval $\left(0,1\right)$, what is the expected largest size of a subset in which the points form the vertices of a convex polygon? Thanks!

-
By the way, "size" only means cardinality here. – user0o Jan 17 at 20:14
Related: en.wikipedia.org/wiki/Happy_ending_problem – Sam Hopkins Jan 17 at 20:22
@Berlusconi: it does not need to 16. An answer for any number less than or equal to $8$ would be highly appreciated. It may not be trivial to solve for a large number, but one can probably have some probability estimates on the angles, which largely determine the convexity. – user0o Jan 17 at 20:44
@Sam: do you know about the probability that the extremal configurations in generalized happy ending problem occur for $8$ points or less? – user0o Jan 17 at 20:49

2
Probability distribution not clear: Are the points independent? For a given point, are the horizontal and vertical coordinates independent? – Gerald Edgar Jan 19 at 13:35
show 3 more comments

## 1 Answer

For specific and not very small $n$ this would be quit a messy computation.

There are esults about the asymptotics for large $n$ in a paper of Ambrus and Barany http://arxiv.org/abs/0906.5452 . They consider a slightly different problem, but their methods work and the result is $c n^{1/3}$ for some computable $c$.

Note also that they compute the typical value, which is only a lower bound for the expectation. Various concentration inequalities which apply since the points are iid can be used to get the expectation as well. (Or you could try to get a large deviation estimate directly.)

-

Dear Omer, thank you for your answer, but do you know if the exponent  would change for other convex regions? since they only considered a triangle. – user0o Jan 25 at 3:46
The exponent would not change. For example, take random points in a circular disk. Fit a triangle in the disk. A constant fraction of the n points falls inside the triangle (w.h.p.), and thus you get at least $c′n^{1/3}$ points in convex position; similarly, an ellipse (affine image of a disk) fits into any triangle, showing the other direction of the inequality. Any two convex shapes are related like this (after affine transformation). – Günter Rote Apr 28 at 23:15
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 9, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8923681378364563, "perplexity_flag": "head"}