Warren, It's Question 10 on the Part IA Probability sheet 2, therefore well known: http://www.statslab.cam.ac.uk/~frank/PROB/sheet2.pdf Sincerely, Adam P. Goucher http://cp4space.wordpress.com

----- Original Message ----- From: Warren D Smith Sent: 04/16/13 05:13 PM To: math-fun@mailman.xmission.com Subject: [math-fun] how many records?

Here's a cute and useful fact.

Let S be a set of N numbers. Permute them into random order. Scan thru the elements in that order. Each time you encounter a new record max, ring a bell. So for example, if S={7*,8*,5,3,4,9*} you would ring the bell 3 times at the *s.

EASY CLAIM: expected number of times the bell rings, equals HarmonicNumber(N) = 1+1/2+1/3+...+1/N.

HARDER QUESTIONS, which I have not looked at: What about the variance? What about tail bounds? Can you write a formula for the whole probability distribution for the number of bell-rings: Prob(R) = xxx?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun