Exact Convergence Rate in the Limit Theorems of Erdos-Renyi and Shepp

The original Erdos-Renyi theorem states that Uₙ/(α k) → 1 almost surely for a large class of distributions, where Uₙ = 0≤ i ≤ n - k (Sᵢ₊ₖ - Sᵢ), Sᵢ = X₁ + ⋯ + Xᵢ is a partial sum of i.i.d. random variables, k = κ(n) = c log n, c > 0, and α > 0 is a number depending only upon c and the distribution of X₁. We prove that the lim and the lim inf of (Uₙ - α k)/log k are almost surely equal to (2t⁾⁻¹ and -(2t⁾⁻¹, respectively, where t^ is another positive number depending only upon c and the distribution of X₁. The same limits are obtained for the random variable Tₙ = 1≤ i ≤ n(Si+κ(i) - Sᵢ) studied by Shepp.