[math-fun] how many records?
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?
--ok, thanks to Victor Miller's hint, we have expected # bell rings = ha(N) = 1 + 1/2 + 1/3 + ... + 1/N. probability of exactly R rings = |s(N,R)| / N! where s(N,R) = Stirling Numbers of the first kind. variance of #bell rings = SUM(R=0..N)OF [R-ha(N)]^2 * |s(N,R)|/N! Of course, when N is large, ha(N) approaches ln(N)+gamma where gamma= 0.5772156649 is the Euler-Mascheroni constant. The variance appears numerically to approach ha(N)-1.645 which if so would mean that the probability distribution is sharply peaked around its expectation, e.g. when N--> infinity the probability-->100% that #bellrings lies within the interval [0.999, 1.001]*ha(N). That's remarkably predictable.
variance of #bell rings = SUM(R=0..N)OF [R-ha(N)]^2 * |s(N,R)|/N!
Of course, when N is large, ha(N) approaches ln(N)+gamma where gamma= 0.5772156649 is the Euler-Mascheroni constant.
The variance appears numerically to approach ha(N)-1.645 That's remarkably predictable.
--It looks as though the exact value for 1.645 is pi^2/6=1.6449340668482264364. Also known as RiemannZeta(2). If you extrapolate the last column of the table below to N=infinity assuming error proportional to 1/N, then you get 1.644934066834 which is too low by 0.000000000014. ....N...........expect.......................variance...................difference... 1 1.00000000000000 0.00000000000000 1.00000000000000 2 1.50000000000000 0.25000000000000 1.25000000000000 4 2.08333333333333 0.65972222222222 1.42361111111111 8 2.71785714285714 1.19043509070295 1.52742205215420 16 3.38072899322899 1.79638245978401 1.58434653344499 32 4.05849519543652 2.44432793260860 1.61416726282792 64 4.74389090370577 3.11446040229688 1.62943050140889 128 5.43314709258917 3.79599508763471 1.63715200495446 256 6.12434496281728 4.48330952650860 1.64103543630868 512 6.81651653454972 5.17353368659462 1.64298284795510 1024 7.50917567227813 5.86521769124796 1.64395798103017 2048 8.20207877181772 6.55763286702960 1.64444590478812 4096 8.89510389696632 7.25041394094320 1.64468995602312 8192 9.58819004609531 7.94337804210931 1.64481200398600 16384 10.28130671000845 8.63643367645385 1.64487303355460 32768 10.97443863201216 9.32953508227638 1.64490354973578 65536 11.66757818323579 10.02265937506018 1.64491880817561 131072 12.36072154911302 10.71579511163020 1.64492643748282 262144 13.05386682232797 11.40893657016967 1.64493025215830 -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
I believe that all the moments can be calculated, using the trick of choosing n real numbers independently from [0,1] and sorting them, rather than choosing from the n! permutations. - Cris On Apr 16, 2013, at 1:31 PM, Warren D Smith wrote:
variance of #bell rings = SUM(R=0..N)OF [R-ha(N)]^2 * |s(N,R)|/N!
Of course, when N is large, ha(N) approaches ln(N)+gamma where gamma= 0.5772156649 is the Euler-Mascheroni constant.
The variance appears numerically to approach ha(N)-1.645 That's remarkably predictable.
--It looks as though the exact value for 1.645 is pi^2/6=1.6449340668482264364. Also known as RiemannZeta(2). If you extrapolate the last column of the table below to N=infinity assuming error proportional to 1/N, then you get 1.644934066834 which is too low by 0.000000000014.
....N...........expect.......................variance...................difference... 1 1.00000000000000 0.00000000000000 1.00000000000000 2 1.50000000000000 0.25000000000000 1.25000000000000 4 2.08333333333333 0.65972222222222 1.42361111111111 8 2.71785714285714 1.19043509070295 1.52742205215420 16 3.38072899322899 1.79638245978401 1.58434653344499 32 4.05849519543652 2.44432793260860 1.61416726282792 64 4.74389090370577 3.11446040229688 1.62943050140889 128 5.43314709258917 3.79599508763471 1.63715200495446 256 6.12434496281728 4.48330952650860 1.64103543630868 512 6.81651653454972 5.17353368659462 1.64298284795510 1024 7.50917567227813 5.86521769124796 1.64395798103017 2048 8.20207877181772 6.55763286702960 1.64444590478812 4096 8.89510389696632 7.25041394094320 1.64468995602312 8192 9.58819004609531 7.94337804210931 1.64481200398600 16384 10.28130671000845 8.63643367645385 1.64487303355460 32768 10.97443863201216 9.32953508227638 1.64490354973578 65536 11.66757818323579 10.02265937506018 1.64491880817561 131072 12.36072154911302 10.71579511163020 1.64492643748282 262144 13.05386682232797 11.40893657016967 1.64493025215830
-- 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
Cristopher Moore Professor, Santa Fe Institute
participants (2)
-
Cris Moore -
Warren D Smith