Math Question - Expected Number of Trials

[Mike_N_Ike]

Hellllo Got|Apex! I was trying to work through something today that for the life of me I can't remember how to do...and I remembered all of the math gurus that we had here - so I thought I'd give it a shot :)


The problem is set up as such:

You have X number of cases to test. During each trial, or iteration, you randomly test one of the X cases. The process cannot use logic to choose the next case, so it's chosen at random every time. In other words, it is possible to choose the same one any number of times in a row.

Obviously, the minimum number of trials needed to test all X cases would be X; and the maximum number of trials needed to test all X cases would be infinite. I am trying to determine the average, or expected number of trials that need to be executed before all X test cases have been hit.

If this is easier to do using an actual value, we can pretend that X is 5 - although it will more likely end up being somewhere between 30 and 50.

If anybody has insight on this, it would be greatly appreciated :D

Miss you guys!

[MrGreg]

Nothing gets the blood flowing like math on a Friday night.

I haven't worked out the answer to your question yet, but here is another probability that may be useful:

The odds that a single SPECIFIC test case will be run at least once are

1 - ((x-1)/x)^y

i.e. 1 - the odds it is never run.

[Napoleon54]

I think the answer will depend upon the confidence level you want. Do you want 90% certainty that all cases will be tested? 95%? 99%?

If you want 0% confidence simply pick a number of tests <x. But as the number of trials proceeds past x to infinity, the chances of every case being tested will approach 100%. In between x and infinity is everything in between 0% and 100%. Thus a confidence level is required to make the determination.

There may be math gurus here, but hopefully there's also a statistics guru or two (not me) that can actually figure this out. :D

BTW, maybe Verizon's customer service people can help you out, I hear they do magical things with numbers.

[MrGreg]

The odds of complete coverage for x test cases and y trials (assuming each case is equally likely for any given trial and each trial is an independent event) are

x multichoose (y-x) divided by x multichoose y

which can be expressed as:

(y-1)!
------
(y-x)!(x-1)!
-------------------
(x+y-1)!
------
y!(x-1)!

which reduces to:

y!(y-1)!
--------------
(y-x)!(y+x-1)!





You can use this to figure out how many trials you'll have to do to reach your acceptable level of coverage 90%, 95%, etc. (like Napoleon54 said).


x multichoose (y-x) is the number of possible "good" outcomes and x multichoose y is the total possible number of outcomes. I found it easiest to think of this as a "stars and bars" type of problem where you need to count the permutations where no two bars are next to each other.

And if you want to actually calculate these probabilities, you'll need something more powerful than excel, since excel craps out at around y=100.