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

|Contact| |Front page| |Contents| |Up| |Store|

Copyright © 1996-2017 Alexander Bogomolny

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

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

by induction on n.

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

Suppose n > 1 and assume (1) holds for rn-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,

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

References

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

|Contact| |Front page| |Contents| |Up| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62045019

Search by google: