undefined | Better HN

0 pointsBeetleB8y ago0 comments

>Hence interesting is solving discrete problems with "continuous" tools - like e.g. http://ac.cs.princeton.edu/home/

I'm often interested in the opposite: Solving continuous problems by going to the discrete domain.

I'm not a mathematician, but I did enjoy taking math courses and dabbling a little.

My personal highlight was when I was struggling for months to solve a continuous variable problem, but then one day I decided to "pixelate" it and converted it to a discrete problem. I solved the discrete problem, and got the answer to the continuous problem by taking the limit of the solution.

The problem was: If you choose n numbers at random (uniformly) in the interval (0,1), what is the expected value of the maximum?

I showed this problem to a number of people (including math professors) who struggled with it. Finally, one day, a colleague solved the problem in 5 minutes and 3 lines using continuous math. (It's not a clever solution either - surprising so many people missed it).

Still, I feel content with my discrete proof (which was about 2 pages). Since then I've often thought I should collect interesting continuous problems solved this way and put them on a web site, but never did. :-(

0 comments

3 comments · 1 top-level

jeremysalwen8y ago· 2 in thread

So is this the solution? The probability that all numbers are less than x is equal to x^n. So then you take the derivative of that to get the probability that the maximum us is exactly x. n x^n-1. Then calculate the expected value as integral from 0 to 1 of x n x^n-1 = n/n+1.

BeetleBOP8y ago

Too lazy to think deeply about it, but it sounds right. You start with the cumulative distribution function and get the pdf from it, which looks like what you're doing.

Really simple solution. Problem is simple enough that this could be a standard HW problem in a probability course. Yet so many people (including myself) did not see it. We kept doing multiple integrals (n integrals for n points) and tried using induction on it.

This was actually a subproblem of the real problem. The real problem was: Given n points chosen randomly on a circle, construct the n-sided polygon. What is the probability that the center of the circle is inside the polygon? Since I worked on it, the problem has shown up on the Internet in various places (usually for the special case of n=3 - triangles, but I think I've seen the general one posted here and there). I don't recall if anyone came up with the same solution I did for the general case - I think one site had it.

aoki8y ago

it is (a standard HW problem). for bonus points, there's a connection between order statistics of the uniform distribution (such as max) and the beta distribution, of which the solution above is an example.

j / k navigate · click thread line to collapse