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

Let r_n(p) be the sought expectation. We shall show that

(1)	r_n(p) = p + (n - 1)p(1 - p)

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,

r_n(p)	= p(1 - p)·[r_n-1(p) + 1] + [1 - p(1 - p)]·r_n-1(p)
	= r_n-1(p) + p(1 - p)
	= p + (n - 1)p(1 - p).

References

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

40616007