3
$\begingroup$

Context:

I recently came across a question like “what’s the probability that a random number (integer) generator will generate four successive numbers as consecutive increasing numbers?”. Many people have solved this assuming each sample point consists of only 4 random numbers and counting number of cases four of them are consecutive & increasing and finally concluding the probability as $\frac{(N-4+1)}{N^4}$ assuming the generators produces integers in the range $[1,N]$. However this problem has induced many interesting thoughts in my mind such as what if we try to find the probability for the same event (i.e. 4 consecutive numbers) but in $n (n\ge4)$ picks! Of course in this case 4 consecutive increasing number would be rephrased as at least one occurrence of 4 or more consecutive increasing numbers in successive picks. Yet another interesting observation I made here is that with $n$ changing the probability also changes. I spent ample time to solve this question but couldn't figure out how to count size of the event space. In this regard I’m rephrasing my question below with equivalent Urn & Ball model and any help solving this question would be much appreciated.

Question:

An urn has $N$ balls marked with a integer number from $1$ to $N$. Thus there would be exactly one ball in the urn with a given number from $[1,N]$. If we randomly pick $n$ balls with replacement then we know that there would be $N^n$ possible ways of picking $n$ balls. The question is how many of such ways we’ll have at least one occurrence of $4(=c)$ or more successive picks having consecutive increasing numbers? We can assume $n\ge4$.

Example: For N=9 (range of numbering 1-9) , n=7 (number of pick), c=3(number of picks with consecutive numbers)

Sequences that are included:

i) $1,2,3,1,2,3,1$ (2 occurrences of 3 consecutive numbers)
ii) $1,2,3,3,4,5,6$ (1 occurrence of 3 consecutive numbers and 1 occurrence of 4 consecutive numbers)
iii) $8,9,9,9,4,5,6$ (1 occurrence of 2 consecutive numbers and 1 occurrence of 3 consecutive numbers)

Sequences that are NOT included:

i) $1,2,4,5,7,8$ (3 occurrences of 2 consecutive numbers)

Please let me know if more information is required!

  • 0
    @Hurkyl, Marc van Leeuwen: I thank you for your response and would like to know your views on this. Do you think this is a trivial question (that you or someone else can solve easily) or it's a challenging question (may be you would like to give a try as well given some spare time). P.S. (I'm neither a student nor this is any assignment from any course. I'm a software professional who takes interest in math.)2012-12-18

0 Answers 0