Consider the quantity:

for each index t of the string, let l(t) be the length of
  the run to which the character pointed to by the index belongs

c(t) = (leftceil log(l(t)+1) rightceil + 1)  /  l(t)

What is E[c(t)] in terms of C_{rle}(w)?
(the expectation is taken over the uniform choice of an index t).
How would one estimate E[c(t)]?

<br>
see another <a href="pset2prob3next"> hint...</a>