Partially correct series calculations?

Question

I know how to get the chances of drawing n numbered balls out of a hat in the correct order (n!).

How would I work out the chances of drawing n balls with at least q in the right order?

(for example drawing 20 numbered balls out of a hat at random and ending up with at least 10 in the right order)

Additional Details

There can be an infinite number of balls in the hat. What I mean by "in the right order" is not that number 4 immediately follows number 3, its that at least ten of the balls are in "sequence" (eg 2, 5, 67, 89 etc).

Come to think of it the "infinite balls" bit might be a little extreme. Take it as twenty balls in the hat if its easier!

Answer 1

Best Answer - Chosen by Asker

This sounds like the type of problem that has been solved for the proof of a non-parametric statistics test. Unfortunately I don't know which one off the top of my head.

As you say picking out n balls from a hat containing precisely n in sequence is 1/n!, since there are n! possible orderings and only one is right.

If the hat contains more balls, M say, then there are M!/(M-n)! ways of choosing n balls from the hat. As you have already recognized the tricky bit comes when you have to find an expression for the number of subsequences in order. There is a webpage about straight flushes in poker which shows the logic of how to calculate (visit source below).

The infinite balls in a cosmic sized hat is easy - apart from the small logistical problem of making the balls big enough to write impossibly large numbers on and how does one randomly take balls from such a very large hat. And needing a second universe into which to place the selected balls. All mere trifles to a mathematician.

Since there will always be infinitely more balls with larger numbers than any given ball you select the probability of the next ball being of larger value is 'almost one'. So the probability of q being in sequence is 'almost one'. This means that in the long run a finite number of sequences will be in the wrong order, but you can make the number in the right order as large as you like simply by running the sampling experiment for longer.

[I think the logic is right, but bow to the wisdom of anyone who comes up with a better argument and more understanding of this kind of problem].

I started trying to see a pattern to the finite case by working through some examples with small numbers, but the answers I got quickly ruled out any simple rule involving factorials. I think the answer involves a sum of factorial based terms, but I haven't figured out the details of it yet. So I guess its back to sweat-of-brow calculating the cases.

Source(s):

http://home.att.net/~numericana/answer/c…

Asker's Rating:

Asker's Comment:

Thanks, I'll work through the poker website and see if that helps.

Answer 2

Oooo - sounds tricky. Are there only 20 balls in the hat to start off with or more than 20?