Book Index Range

The index of a book lists every page on which certain words appear. To save space these are listed in ranges; for example, if a word occurs on pages 1, 2, 3, 5, 8, and 9, then its index contains ranges: 1-3, 5, 8-9.

A certain word appears on each page of an n-page book (n > 0) independently with probability p. Find the expected number of entries in its index entry.

Solution

Copyright © 1996-2009 Alexander Bogomolny

by induction on n.

When n = 1, (1) becomes r₁(p) = p, which is clearly true.

Suppose n > 1 and assume (1) holds for r_n-1(p), which is the expected number of ranges for an (n-1)-page book. The addition of one more page may or may not change the total number of ranges. When page n is added, the number of ranges increases by one if the term occurs on page n and does not occur on page (n - 1); this happens with probability p(1 - p). Otherwise, the number of ranges does not change. Therefore,

References

1. G. G. Chappell, A Quicky, Math Magazine, Vol. 72, No. 4, October 1999, Q893 (p. 326), A893 (p. 331).

Copyright © 1996-2009 Alexander Bogomolny