From: Cris Moore <moore@santafe.edu>

Subject: Re: [math-fun] how many records?

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.

--True, but the expectation = harmonic(n) formula works without need of independence. I think Moore's point is this independence comes in handy when working on higher moments than the 1st.

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) .

--this is the stirling number (first kind, unsigned) generating function, essentially.

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).

--k-tuples of what? The i_1,..., i_k need to be selected from {1,2,3...,n} without replacement, I think is what he meant.

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.

--right. Now you are cooking with gas.

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,

--he meant "remove the ones with two i's equal"

and add back in (twice) the ones where they're all the same. Cris

--A generalization of Cris Moore's 3 formulas 1: E[t] = H(n,1) 2: E[t(t-1)] = H(n,1)^2 - H(n,2)3: E[t(t-1)(t-2)] = H(n,1)^3 - 3 H(n,1) H(n,2) + 2 H(n,3) 3: E[t(t-1)(t-2)] = H(n,1)^3 - 3 H(n,1) H(n,2) + 2 H(n,3) is j+1: E[t*(t-1)*(t-2)*...*(t-j)] = H(n,1)^(j+1) + s(j+1,j)*H(n,1)^(j-1)*H(n,2) + s(j+1,j-1)*H(n,3) where s(N,R) are the signed stirling numbers of first kind, note s(N,N)=1, s(N,0)=0, and we proclaim s(N,AnythingNegative)=0. That works for j=0,1,2 but is not the right generalization for larger j. Indeed the next one is 4: E[t(t-1)(t-2)(t-3)] = H(n,1)^4 - 6 H(n,1)^2 H(n,2) + 3 H(n,2)^2 + 8 H(n,1) H(n,3) - 6 H(n,4). I think the right generalization should involve multinomial coefficients with upstairs index j+1 and a sum over all partitions of j+1 (which go in the downstairs indices)... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)