1. Runs

In an n-string,that is, a string consisting of n digits, a run is defined to be an occurrence of an integer in a string such that if the next digit contains the same integer it is the same run, and if it contains another integer we have another run. And k denotes the number of integers we can use to form a string. For instance, if we form a string of 10 digits by using the numbers 1,2,3,4,5, we have n=10 & k=5. And the number of runs in the string 2344155521 is 7 (2,3,4,1,5,2,1). The question is: what is the expected number of runs in an n-string with k possible integers?

I tried to apply the problem to the sequence of tossing an unbiased coin noting whether it is head or tail. Then we have k=2 (h or t). Since it is a nonbiased coin, p=q=1/2 (where p and q denote the probability of having head or tail) , and then expected number of runs is

1 + 2(n-1)*p*q = 1 + 2(n-1)*(1/2)*(1/2) = 1 + (n-1)/2. But when k is larger than 2, i don't know what to do? Can you help me?

2. Originally Posted by enrique
In an n-string,that is, a string consisting of n digits, a run is defined to be an occurrence of an integer in a string such that if the next digit contains the same integer it is the same run, and if it contains another integer we have another run. And k denotes the number of integers we can use to form a string. For instance, if we form a string of 10 digits by using the numbers 1,2,3,4,5, we have n=10 & k=5. And the number of runs in the string 2344155521 is 7 (2,3,4,1,5,2,1). The question is: what is the expected number of runs in an n-digit string with k possible integers?

I tried to apply the problem to the sequence of tossing an unbiased coin noting whether it is head or tail. Then we have k=2 (h or t). Since it is a nonbiased coin, p=q=1/2 (where p and q denote the probability of having head or tail) , and then expected number of runs is

1 + 2(n-1)*p*q = 1 + 2(n-1)*(1/2)*(1/2) = 1 + (n-1)/2. But when k is larger than 2, i don't know what to do? Can you help me?

If yes, I think the answer is {x:x∈R,1≤x≤n}.

3. No, the answer is an integer that should depend on both n and k.

4. Originally Posted by enrique
No, the answer is an integer that should depend on both n and k.
What is the title of the chapter?

5. Sorry, but i didn't understand what you meant.

6. Originally Posted by enrique
Sorry, but i didn't understand what you meant.
Such as function, polynomial, differentiation, statistic, trigonometry, geometry coordinate...