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?