Both Uk and Vk are functions of the Markov process {Yk : k = 0,1,...}, so in particular, both {Un} and {Vn} depend on the initial value Y0. For clarity one should note that Uk has mean zero when Y0 ≡ 0 and Vk has mean zero when Y0 follows the stationary distribution ν. The random variables Uk and Vk differ by a constant that depends on k, and by (14) the constant is not larger than O(δk). Thus, by the representation (10), we have . Now, we expand the sum in (17) and write . To estimate the first sum An of (18), we apply (13) just as we did in the derivation of (14), and this time we find . Summation then gives us . To deal with the double sum Bn, we first need a lemma to help us estimate some of the summands of Bn. Lemma 7. For any initial distribution µ one has Eµ[ViVi+j] = O(δj) for all i,j ≥ 0. Proof. To exploit the Markov property for the chain {Yn : n = 0,1,...}, we first condition on Yi−1 and Yi and note that Eµ[ViVi+j] = Eµ[ViEµ[Vi+j |Yi−1,Yi]] = Eµ[ViEµ[Vi+j |Yi]] = Eµ[ViEYi[Vj]]. If we use (13) as before, then we see that for all x ∈ X we have Ex[Vn] = Eν[Vn] + O(δn), and the implied constant does not depend on x. When we insert this into (21) and recall that the definition of Vn gives us Eν[Vn] = 0, the proof of the lemma is complete. Lemma 7 helps us deal with cross terms with large j, but we also need a relation that deals with arbitrary j. Here, we again use (13) to get for all j ≥ 0 that E0[ViVi+j] = Eν[ViVi+j] + O(δi) = Eν[V1V1+j] + O(δi).
The main feature here is that one has ak+1/bk = ρ > 1 for all 1 ≤ k < M. If we have Xi ∈ Ii for i = 1,2,...M, then all of the observations X1, X2, ..., XM are selected, so we always have the inequality M ∏1(Xk ∈ Ik) ≤ 1(Nρ ≥ M). k=1 Finally, by the independence of the variables Xk, 1 ≤ k ≤ M and the strict monotonicity of F, we see that the expectation of the product is strictly positive. This gives us P(Nρ ≥ M) > 0 for all M ≥ 1. Since M is arbitrary, we see that Nρ is unbounded, and the proof of the theorem is complete. Complements to Classical Record Theory Here we consider the calculation of the expected number of selections where we assume that there was a selection made at “time zero” that had value x ∈ [0,1]. Formally, we modify the definition (2) by first setting τ1 = min{j : Xj ≥ ρx}. Next, for k ≥ 2 we define τk as before by setting τk = min{j : Xj ≥ ρXτk 1}, and − finally we set . In this notation, R´enyi’s classical formula for the expected number of records is , and the main goal of this section is to generalize this result in two ways. The immediate goal is to show that , and then in Theorem 12 we will get a closely related formula for E[Rnx(ρ)]. We begin by using first step analysis to get a useful recursion for the quantities gn,ρ(x) def= E[Rnx(ρ)] and gn(x) def= gn,1(x). Specifically, if we consider the first observation y = X1, then X1 is not accepted if y ≤ ρx, and this happens with probability ρx. On the other hand if y = X1 ∈ [ρx,1] we do accept X1, and accordingly we find the basic recurrence relation (44) For general ρ ∈ (0,1), this equation offers considerable resistance; in essence, it is a linearized non-autonomous pantograph equation in integrated form. Nevertheless,