[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?
The number of permutations of 1..n with k left to right maxima is given by the Stirling Numbers of the first kind. See, for example: http://blog.tanyakhovanova.com/?p=451 . Since we have an explicit generating function for them (see Wikipedia, for example), we can easily calculate any moment of their distribution. Victor On Tue, Apr 16, 2013 at 12:13 PM, Warren D Smith <warren.wds@gmail.com> wrote:
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
OK, there seems to be an amazing exact formula for the variance-- as amazing as the exact formula for the expectation value: expect = harmonic(n,1) variance = harmonic(n,1) - harmonic(n,2) where harmonic(n,k) = 1 + 1/2^k + 1/3^k + ... + 1/n^k. This probably is a new result (?). E.g. it is not listed in the NIST compilation of facts about Stirling numbers, http://dlmf.nist.gov/26.8 -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
OK, there seems to be an amazing exact formula for the variance-- as amazing as the exact formula for the expectation value: expect = harmonic(n,1) variance = harmonic(n,1) - harmonic(n,2) where harmonic(n,k) = 1 + 1/2^k + 1/3^k + ... + 1/n^k. This probably is a new result (?). E.g. it is not listed in the NIST compilation of facts about Stirling numbers, http://dlmf.nist.gov/26.8
Warren Smith wrote:
OK, there seems to be an amazing exact formula for the variance-- as amazing as the exact formula for the expectation value:
expect = harmonic(n,1)
variance = harmonic(n,1) - harmonic(n,2)
where harmonic(n,k) = 1 + 1/2^k + 1/3^k + ... + 1/n^k. This probably is a new result (?).
It is found, e.g., in http://www.isse.ucar.edu/extremevalues/nedglick.pdf (page 14, near the top). -- g
The great thing about this problem is that if X_i is the event that the i'th entry sets a record, these events are independent! To see this, note that X_i occurs if the i'th entry is bigger than the previous i-1 entries, and this has probability 1/i no matter what order the previous i-1 entries occurred in. To compute the moments, consider the generating function G(z) = \sum_{t=0}^n z^t Pr[there are t records]. Then G(z) = z (1+(z-1)/2) (1+(z-1)/3) (1+(z-1)/4) ... (1+(z-1)/n) . Then for any k, the "k'th falling moment" E[t(t-1)(t-2)...(t-k+1)] is the k'th derivative of G(z) at z=1. This is the sum over all distinct, ordered k-tuples (i_1, ... i_k) of the product 1/(i_1 ... i_k). I'll use Warren's notation H(n,k) = sum_{i=1}^n 1/i^k. For k=1, we get E[t] = H(n,1). For k=2, we have E[t(t-1)] = H(n,1)^2 - H(n,2) since H(n,1)^2 is the sum over all ordered pairs (i_1,i_2), including i_1=i_2, but we only want the distinct ones. To get the variance, we write E[t^2]-E[t]^2 = E[t(t-1)] + E[t] - E[t]^2 = H(n,1) - H(n,2) . Let's do one more. The third falling moment is E[t(t-1)(t-2)] = H(n,1)^3 - 3 H(n,1) H(n,2) + 2 H(n,3) where we start with all 3-tuples, remove the ones where one i equals the other two, and add back in (twice) the ones where they're all the same. I think there are Bell numbers lurking here... the distribution of the number of fixed points of a permutation also has Bell numbers in its moments. Cris On Apr 16, 2013, at 4:28 PM, Warren D Smith wrote:
OK, there seems to be an amazing exact formula for the variance-- as amazing as the exact formula for the expectation value:
expect = harmonic(n,1)
variance = harmonic(n,1) - harmonic(n,2)
where harmonic(n,k) = 1 + 1/2^k + 1/3^k + ... + 1/n^k. This probably is a new result (?). E.g. it is not listed in the NIST compilation of facts about Stirling numbers, http://dlmf.nist.gov/26.8
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Cris Moore -
Gareth McCaughan -
Victor Miller -
Warren D Smith