memnus: Dave Davenport and Lovelace with quotes from Alice In Wonderland (We're All Mad Here (Narbonic))
2007-10-10 02:13 pm
Entry tags:

Results

(Handy reference link for the lazy)

Monte Carlo estimator says:

- Numbers in D are skewed toward smaller values.
- Approximate size of D is 1.7n.

And I had my characterization of the problem slightly wrong, which caused some confusion: the terminating condition should have been "when you cannot choose any more numbers" as [livejournal.com profile] zane314 guessed.

click
memnus: Dragon with pigtails and glasses, saying "No sense... in a way that blows your mind?" (That makes no sense! (O&M))
2007-10-09 07:16 pm
Entry tags:

For the probabilitists in the audience

I'd like your thoughts on a problem. (Here, all "randomly chosen" numbers are taken from the same continuous real distribution.) Suppose you have a set S of n randomly-chosen numbers, and a set D, initially empty. Begin by removing the largest number from S and placing it in D, and adding another random number to S. Now take the largest number from S that is smaller than the last number you chose, place it in D, and replace it with a random number. Repeat until you've taken the smallest number from S.

- What is the distribution of numbers in D?
- What is the expected value for the size of D?
- Bonus question (I know the answer to this one!): Why is Brian thinking about this problem?

I'm about to start in on a Monte Carlo estimator of the problem, but I'd like some theoretical input.

click