Enough Random Numbers For Me

[fairyrak]

I want to generate a chain of x random numbers from 0 to 10:
(actually x=687 but I prefer to call it x)

what's the formula to calculate the probability that somewhere in that chain of x numbers there each and any these numbers formed by two digits will appear at least once?:

00, 01, 02 , 03 , 04, 05, 06, 07 , 08, 09, 10, 11, 12, 13 and so on. . . to 99

[factor-fiction]

Well done bert-h. Sorry if I interfered. I couldn't tell from fairyrak's replies that you had dealt with it fully.

[fairyrak]

I have problems to state mathematical question in an understandable way, I wish I would find someone rephrase my problem so that I could paste it in another question with a slight variant (that now the pairs can only start in the odd or even positions of the chain of length x instead of in whatever place they wanted) (I now want that they don't overlap between them)

[fairyrak]

let me guess:
93%/2 = 46.5% maybe? for x=687

[fairyrak]

and thanks for the reply, I just was waiting on a consensus

[jim360]

If the pairs don't overlap the problem becomes easy, or easier, because now each pair is independent of the previous one and at any point the probability of getting a new pair can be worked out. There's a certain amount of subtlety in counting, but at the very least I can confidently assert that the probability of getting all 100 pairs after generating 200 random numbers (or 100 pairs of random numbers) is equal to 100! /(100^100) (which is pathetically tiny), and that you would only expect to have got all 100 pairs of numbers at least once after having generated 519 such pairs, or 1038 single-digit random numbers (the formula for this one is given by 1+100/99 + 100/98 + 100/97 + ... + 100/2 + 100/1).

What I haven't done, yet, is come up with a general formula for the probability, but the principle is that you can now count "successful" strings more easily, since at the very least they require all 100 two-digit combinations to occur at least once, in any arrangement (100!) and then the remainder can be any arrangement of numbers you so choose, occurring at any point in the string. This counting should be subject to the condition that the probability is zero for a string of less than 100 pairs of digits, and never greater than 1, but always increasing, and so far I've not done the counting properly yet, but never mind. I'll try to think about it a bit more today.

[bert_h]

When the pairs are non-overlapping, this turns into a version of the well-known "coupon collector's problem", for which you can find plenty of Google hits, and even a calculator.

[jim360]

Indeed. My hope was to find the result for myself, although I can see that apparently the counting is non-trivial -- broadly speaking the probability of getting all 100 distinct pairs after 101 goes is equal to the probability of getting them all after 100 + the probability of getting 99 in the first 100, so that there's a sum involved. Perhaps surprisingly, to me at least, there also appears to be a relative sign between some contributions.