Let $F_n$ be a real valued function, $$F_n(r) = \frac{r}{n}(\psi(n) - \psi(r)$$ where $\psi$ is a digamma function. Let the sequence of functions $\{g_n\}$ be defined by $g_n(x) := F_n(nx)$.

Show that $\{g_n\}$ converges uniformly on [0,1] and to the function $g(x) := -xlog(x)$.

I am trying to understand the paper, "A variant of the Secretary Problem: the Best or the Worst" by L. Bayon, J. Grau, A. M. Oller-Marcen, M. Ruiz, P.M. Suarez.

It says there that this can be seen with little effort but I am at a loss.

Any hints on how I would prove this would be much appreciated.

  • $\begingroup$ $\psi(n+1) = \psi(n) + \frac{1}{n}$ then use $\log(x) = \int_1^x \frac{1}{t}dt = \lim_{m \to \infty} \frac{x-1}{m}\sum_{n=1}^m \frac{1}{1+n \frac{x-1}{m}}$ $\endgroup$ – reuns May 6 at 5:38

We have

$$\tag{1}\begin{align}|F_n(nx) -(-x \log x)| &= |x(\psi(n) - \psi(nx)) + x\log x| \\&= |x(\psi(n) - \log n) - x(\psi(nx) - \log(nx)| \\ &\leqslant|x||\psi(n) - \log n| + |x (\psi(nx) - \log(nx))|\end{align}$$

There are many well-known representations of the digamma function. Using a recurrence relation we get following representation for integer arguments:

$$\psi(n) = \sum_{k=1}^{n-1} \frac{1}{k} - \gamma,$$

where $\gamma$ is the Euler-Mascheroni constant. With $0 \leqslant x \leqslant 1$, we then have $$\tag{2}|x||\psi(n) - \log n| \leqslant |\psi(n) - \log n| = \left| \sum_{k=1}^{n-1}\frac{1}{k} - \log n - \gamma\right| $$

From the definition of $\gamma$, the RHS of (2) converges to $0$ as $n \to \infty$ and , thus, for any $\epsilon > 0$ there exists $N_1 \in \mathbb{N}$, independent of $x$, such that for all $n \geqslant N_1$, we have for the first term on the RHS of (1),

$$|x||\psi(n) - \log n| < \epsilon/2$$

Using Gauss' integral representation we have

$$\psi(z) = \log z - \frac{1}{2z} - \int_0^\infty \left(\frac{1}{2} - \frac{1}{t} + \frac{1}{e^{t} + 1} \right)e^{-tz} \, dt,$$

and it can be shown (see here) that for all $z > 0$,

$$\frac{1}{2z} \leqslant \log z - \psi(z) \leqslant \frac{1}{z}$$

Thus, for the second term on the RHS of (1) we have

$$\frac{1}{2n} = \frac{x}{2nx} \leqslant |x (\psi(nx) - \log(nx))| = x(\log (nx) - \psi(nx))\leqslant \frac{x}{nx} = \frac{1}{n},$$

and so for any $\epsilon > 0$ there exists $N_2 \in \mathbb{N}$, independent of x, such that for all $n \geqslant N_2$ and all $x \in (0,1]$ we have

$$|x (\psi(nx) - \log(nx))| < \epsilon /2$$

Thus, for all $n \geqslant (N_1,N_2)$ and all $x \in (0,1]$, we have

$$|F_n(nx) - (-x\log x)| < \epsilon$$

This establishes uniform convergence on $(0,1]$. To completely finish here, we would need to establish that $F_n(0) = 0$ by extension as is the case for $x\log x$ where we have $x \log x \to 0$ as $x \to 0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.