Book Index Range

expectation of the number of ranges

Solution

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

Copyright © 1996-2018 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|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
[an error occurred while processing this directive]