Blocks of consecutive letters in a random word

135 Views Asked by At

Let $X$ be an alphabet with $d$ letters, and we consider words over $X$. A block in a word is a subword of the form $xx...x$ for some letter $x\in X$. Every word $w$ is uniquely partitioned on blocks $w=v_1v_2\ldots v_k$, where consecutive blocks contain different letters.

Question 1: What is the expected value of the number of blocks in a random word of length $n$?

Question 2: What is the expected value of the maximal length of a block in a random word of length $n$?

Edit: I have found answer to Question 2 for |X|=2 in the book "Analytic Combinatorics", Prop. V.1: the mean maximal length $\sim \log_2 n$.