Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
With care, I believe you can describe any sequence of numbers with a fixed number of states. Things like "contains a 4-sequence", "Does not contain a 4-sequence, but ends in a 3-sequence whose last digit is in [a,b]", "Does not contain a 4-sequence, but ends in a 2-sequence (that is not a 3-sequence) whose last digit is in [c,d]", et cetera. I expect which intervals to use should be clear when you try to write down the transition matrix of how many ways there are to go from one state to another. (the reason for intervals is that no 4-sequence can begin with a digit in [N-2,N]) –  Hurkyl Dec 17 '12 at 9:59
    
What contribution do the two exclamation marks make to the title? –  joriki Dec 17 '12 at 10:03
1  
@joriki: They give artistic embellishment to an otherwise bald and unexciting title? (Channeling Pooh-Bah, I’m afraid.) –  Brian M. Scott Dec 17 '12 at 10:22
    
@Hurkyl: I'm afraid that I could not guess whether you're criticizing the post or providing a hint to solution. In fact I didn't get why did you mention "no 4-sequence can begin with a digit in [N-2,N]"! To me if N $\ge $ 4+2=6 then a 4-sequence can start with N-2. Am I missing something! –  BuckCherry Dec 17 '12 at 11:45
    
@BuckCherry: What you seem to be missing is that once you have chosen one of $\{N-2,N-1,N\}$, there is no possible way to continue for at least three steps, each time choosing the number that is one more than the previously chosen number. Therfore once such a number is drawn (and it is not itself one more than the previous number) one goes to a "nothing useful found yet" state. What Hurkyl suggests is that the process of checking whether a desired subsequence exists can be done by an automaton with only very few states. For me it is not convincing. –  Marc van Leeuwen Dec 17 '12 at 16:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.