next up previous
Next: Calculation of the Mean Up: Random Permutation Matrices An Previous: Description of Xn,a when

   
A Technical Lemma

The following lemma, which is an elementary analysis result, will be needed for calculating the limit of E[Xn,a] in the next section.

Lemma 1   Suppose $\alpha > \beta\geq 0$. Let (Ln) and (Mn) be sequences of positive integers which satisfy

\begin{displaymath}\frac{L_n}{n} \rightarrow L >0\end{displaymath}

and

\begin{displaymath}\frac{M_n}{n} \rightarrow M >0.\end{displaymath}

Then the sum

\begin{displaymath}\sum_{k=L_n}^{M_n} \frac{1}{\alpha k + \beta} =
\frac{1}{\alpha} \ln (M_n) - \frac{1}{\alpha} \ln (L_n) + A_n,\end{displaymath}

where

\begin{displaymath}\vert A_n\vert \leq \frac{1}{\alpha L_n}.\end{displaymath}

In particular,

\begin{displaymath}\lim_{n\rightarrow \infty}
\sum_{k=L_n}^{M_n} \frac{1}{\alpha k + \beta} = \frac{1}{\alpha}
\ln\left(\frac{M}{L}\right).\end{displaymath}

 

Proof. First, observe that for any integers 0 < x < y, the sum

 \begin{displaymath}\sum_{k = x + 1}^y\frac{1}{k} = \ln (y/x) + \epsilon_1 (x, y),
\end{displaymath} (21)

where

 \begin{displaymath}\frac{1}{2y} -\frac{1}{2x} \le \epsilon_1 (x, y) \le 0.
\end{displaymath} (22)

(This can be seen by comparing the sum with the integral $\int_x^y \frac{1}{t} dt$.)

Next, since $\alpha > \beta\geq 0$, note that

\begin{displaymath}\sum_{k = x + 1}^{y+1}\frac{1}{\alpha k} < \sum_{k = x}^y\frac{1}{\alpha k+\beta} \le
\sum_{k = x}^y\frac{1}{\alpha k}.
\end{displaymath} (23)

Thus, using (21),

\begin{displaymath}\sum_{k = x}^y\frac{1}{\alpha k+\beta} ={1 \over \alpha}\ln(y/x)+\epsilon_2(x,y),
\end{displaymath} (24)

where

\begin{displaymath}\frac{1}{\alpha}\left(\frac{1}{y+1}+\epsilon_1(x,y)\right) < ...
...)\le
\frac{1}{\alpha}\left(\frac{1}{x}+\epsilon_1(x,y)\right).
\end{displaymath} (25)

Combining this with (22), the error can be bounded by

\begin{displaymath}\vert \epsilon_2 (x, y) \vert \le\frac{ 1}{\alpha x}.
\end{displaymath} (26)

Setting $A_n = \epsilon_2 (L_n, M_n)$,

\begin{displaymath}\sum_{k=L_n}^{M_n} \frac{1}{\alpha k + \beta} = \frac{1}{\alpha} \ln (M_n) -
\frac{1}{\alpha} \ln (L_n) + A_n.
\end{displaymath} (27)

Finally, note that since $L_n/n \rightarrow L>0$, the sequence $1/(\alpha L_n) \rightarrow
0$. Thus $A_n \rightarrow 0$, and

\begin{displaymath}\lim_{n\rightarrow \infty}
\sum_{k=L_n}^{M_n} \frac{1}{\alpha k + \beta} = \frac{1}{\alpha}
\ln\left(\frac{M}{L}\right).\end{displaymath}


next up previous
Next: Calculation of the Mean Up: Random Permutation Matrices An Previous: Description of Xn,a when

2000-09-25