Question

What is the probability that if I generate a sequence of 10 numbers by picking numbers one by one between 1 to 100 (randomly), the resultant sequence is strictly increasing?

Answer 1

Answer:

Step-by-step explanation:

Let us assume that the number generator generates numbers in the range [1..N]. Each number is equally likely to be generated (as the generator is perfect) and each generation is independent of the other. For example, picking the third (or any other) number from the generator has no effect on the subsequent picking (fourth, fifth...tenth number).

Now, let us think about the problem as having ten slots. How many ways this slots can be filled up? The first slot can have any values from [1..N] and hence N values. Similarly, the second slot can have any values in the range [1..N] (as repetition is allowed). Therefore, the total number of ways ten numbers can be generated by the generator is N*N*... (ten times multiplication) = N^10.

Now how many ways, 10 consecutive numbers can be generated from the range [1..N]. Let's see,

1 2 3 4 5 6 7 8 9 10 = that's 1 way

2 3 5 6 6 7 8 9 10 11 = that's another way

3 4 5 7 7 8 9 10 11 12 =  that's again another way

I hope you can see the pattern and the last consecutive element possible is

N-9 N-8 N-7 N-6 N-5 N-4 N-3 N-2 N-1 N --- that's the final consecutive element possible.

Therefore, the total number of consecutive elements possible is N-9.

So, the probability of a perfect generator generating ten consecutive number is

 =  total number of consecutive numbers /

number of ways ten numbers can be generated

= (N-9) /

N^10