Questions tagged [rate-of-convergence]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-2
votes
1answer
28 views

Order of convergence of iterative methods

Consider the fixed point iteration $$x_{n+1}=\phi(x_n), n\geq 0,\ \text{with}\ \phi(x)=3+(x-3)^3, \ x\in(2.5, 3.5)$$ and the initial approximation $x_0=3.25$. Then the order of convergence of the ...
0
votes
1answer
24 views

The rate of convergence of the remainder of the power series for the Polylog function

Let $0<p<1$ be a positive real number strictly smaller than one and $q>0$ be a positive real number. Consider the series $$ \mathsf{Li}_{-q}(p) = \sum_{\ell=1}^{+\infty}\ell^{q}p^{\ell} $$ ...
5
votes
1answer
95 views

Rate of convergence in probability - log transform

Let $C>0$ and $(X_n)$ be a sequence of positive random variables. Assume that $$ |X_n - C| = o_p(r_n^{-1}) \iff r_n|X_n-C|=o_p(1) $$ for some fixed sequence $(r_n)$ with $r_n \to \infty$. What can ...
6
votes
1answer
85 views

$E[Y_n^{-1}]$ converges at the same rate as $E[Y_n]^{-1}$ where $Y_n = \bigg(n\sum_{i=1}^n X_i^2 - \bigg(\sum_{i=1}^nX_i \bigg)^2\bigg)^k$

Let $X_1,X_2,\dots,X_n$ be i.i.d observations of a continuous random variable $X$. Let $Y_n$ be the sample variance: $$ Y_n = \bigg(n\sum_{i=1}^n X_i^2 - \bigg(\sum_{i=1}^nX_i \bigg)^2\bigg)^k. $$ ...
1
vote
0answers
68 views

Continuous mapping theorem and convergence in $L_p$

My question kind of generalizes the question in Analogue of continuous mapping theorem for convergence in $L_2$ and it is related to the answer by Nate Eldredge. Edited to give more details: Suppose ...
2
votes
1answer
41 views

Calculating the rate of convergence from a plot of a limit.

The rate of convergence represents how quickly a sequence approaches its limit. $$ \lim _{n \rightarrow \infty} \frac{\left|x_{n+1}-x^{*}\right|}{\left|x_{n}-x^{*}\right|^{q}}=\mu $$ Here, the rate of ...
0
votes
1answer
24 views

Convergence rate about a limit concerning the Poisson CDF.

The CDF of a Poisson distribution with rate parameter $\lambda$ is $$ P(n;\lambda)=\sum_{k=0}^n \frac{\lambda^ke^{-\lambda}}{k!}. $$ As $n$ goes to infinity, the CDF would certainly approach 1. Now, ...
1
vote
1answer
46 views

the limit of Poisson CDF with diverging rate parameter

The CDF of a Poisson distribution with rate parameter $\lambda$ is $$ P(n;\lambda)=\sum_{k=0}^n \frac{\lambda^ke^{-\lambda}}{k!}. $$ As $n$ goes to infinity, the CDF would certainly approach 1. Now, ...
5
votes
0answers
44 views

Convergence rate law of iterated logarithm for a Brownian motion

The law of iterated logarithm has the following implication for a standard Brownian motion $(W_t, t\geq 0)$, $$ \mathbb{P}\left(\limsup_{t\downarrow 0}\frac{W_t}{\sqrt{2t\ln\left(\ln\left(\frac{1}{t}\...
0
votes
0answers
16 views

Order of Convergence when working with errors

I am looking at the numerical solutions of a problem when using the boundary element method, the exact solution is 0.25 I have 3 errors corresponding to using 20,40 and 80 boundary elements. I have ...
0
votes
1answer
34 views

Find rate of convergence for $\sqrt{n+1} - \sqrt{n} = 0$ as $n$ goes to infinity

We can use Taylor series to expand $\sqrt{x}$ $$ \sqrt{x} = \sqrt{n} + \frac{1}{2\sqrt{n}}(x-n) - \frac{1}{4n^{3/2}}(x-n)^2 + ... $$ The solution provided to me uses expansion point around $\sqrt{n}$. ...
1
vote
0answers
44 views

Sample average L1 converge to mean speed

Say $X_1, \cdots, X_n$ are i.i.d random variables with mean zero, let $S_n = \sum_{i=1}^n X_i$, we know by SLLN $$\frac{S_n}{n}\rightarrow 0\text{ a.s}$$ We could further know that the sequence of ...
1
vote
1answer
130 views

Comparing Rate of Convergence of Two Square Root Algorithms

Source: Rudin's "Principles of Mathematical Analysis" 3.17(d) Problem: Compare the rapidity of convergence of the process $$x_{n+1}=\frac{\alpha+x_n}{1+x_n}=x_n+\frac{\alpha-x_n^2}{1+x_n}$$ ...
0
votes
2answers
63 views

Asymptotic behavior of the CDF of a $\operatorname{Beta}(n,n)$ at $x<1/2$.

I know that the if $X_n \sim \operatorname{Beta}(n,n)$ (see here for a definition) then $\mathbb{P}_{X_n} \to \delta_{1/2}, n \to \infty$ weakly. If $\varepsilon \in (0,1/2)$, I'm wondering about how ...
1
vote
2answers
78 views

Uniform rate of convergence of $\sum_{k=0}^{n} {2n+1\choose{k}}\left(a^{k+1}(1-a)^{(2n+1)-k}+a^{(2n+1)-k}(1-a)^{k+1}\right)$ to $\min(a,1-a)$

This question is related to this one. There, it is proved that $$\forall a \in [0,1], f_{2n+1}(a)\to\min(a,1-a), n\to\infty$$ where $$\forall n\in\mathbb{N}, \forall a\in[0,1], f_{2n+1}(a) :=\sum_{k=0}...
1
vote
1answer
593 views

What does first and second order convergence mean [with minimal equations] for optimization methods?

It can be shown that Newton's method has second order convergence provided some criteria is satisfied, and gradient descent has first order convergence, but what does order of convergence mean here? ...
0
votes
0answers
60 views

Known integral representation of modified Bessel function of second kind? Rate of convergence?

Is this integral representation of the modified bessel function of the second kind $K_{n-1}(2\sqrt{t}),$ known? And does it converge quickly? $$(-1)^n \frac{1}{2}\int_0^1 \frac{t^{\frac{n-1}{2}}}{\log^...
1
vote
1answer
44 views

rate of divergence of a sequence

I have a sequence defined as $\exp((\ln n)^{2})$. As $n \rightarrow \infty$, this sequence diverges. What can I say about its rate of divergence? It is faster than any polynomial rate in $n$, but is ...
0
votes
2answers
57 views

Asymptotic behavior of $\sum_{k=1}^{n^2}\frac{q^{n^2-k}(1-q^k)}{k(1-q^{n^2})}$ when $q=1-\frac{\log(n)}{n}$

Let $q=1-\dfrac{\log(n)}{n}$. Numerical simulations indicate that that \begin{align*} \lim_{n \to \infty}\displaystyle\sum_{k=1}^{n^2}\dfrac{q^{n^2-k}(1-q^k)}{k(1-q^{n^2})} = 0 \end{align*} in a ...
1
vote
0answers
58 views

Rate of convergence of Fourier series: Fourier sums vs their Cesàro means.

Let $1<p<\infty$ and $f \in L^p(\mathbb{T})$. It is known that both Fourier sums of $f$ and Cesàro sums of the Fourier sums of $f$ converges in $L^p(\mathbb{T})$ to $f$, i.e.: \begin{align*} \...
4
votes
1answer
71 views

Is it true that $\mathbb{E}\left[\sum\limits_{k=1}^m \frac{\frac{1}{X_k}}{\sum_{j=1}^m \frac{1}{X_j}}\chi_{(r,+\infty)}(X_k)\right]\to0,m\to\infty?$

The following problem arose in the process of showing the convergence of a particular regression algorithms. Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space. Suppose that $X,X_1,X_2,...:\...
1
vote
2answers
81 views

Solution of $(1-x)^n = x$ : Rate of convergence of $x \to 0$ as $n \to \infty$?

The equation $(1-x)^n = x$ has a solution in $x' \in (0,1)$ and indeed the solution $x' \to 0$ as $n \to \infty$. (Consider $f(x) = (1-x)^n$ noting that $f(0) = 1$ and $f(1) = 0$. As $n$ increases, $...
4
votes
0answers
172 views

Rate of convergence of a bisection-like algorithm

Fix a value $x\in(0,1)$ and recursively define the sequences $$a_0=0,~b_0=1$$ $$c_{n+1}=\frac{\frac{a_n+b_n}2+x}2=\frac{a_n+2x+b_n}4$$ $$a_{n+1}=\begin{cases}a_n,&c_{n+1}>x\\c_{n+1},&c_{n+1}...
-2
votes
1answer
203 views

Numerical Analysis: Heun's method

so I did the loglog plot of the maximum error vs the time step when using Heun's method. I see that for very small step sizes the order gets disrupted. Is there a specific reason for that? I also did ...
1
vote
1answer
29 views

Different way of expressing rate of convergence for a sequence

Suppose that we have a sequence given by an iterative method: $$x_{n+1} = \phi(x_n)$$ where this sequence converges to a fixed point $\alpha$. Also, suppose that the sequence has the following rate ...
0
votes
0answers
43 views

Rate for Sum of Random Variables

I Just read a Paper where we have $(X_1, ..., X_n)$ independent RV with zero mean. And there were an Expression like $$ Var = V + v $$ where $V:= \sum_{1=j}^n \sum_{1=i}^nE(X_j^2)E(X_i^2)$ and $v:= ...
0
votes
1answer
59 views

Convergence and numerical accuracy

I know that a sequence of real numbers $\{x_n\}_{n=0}^\infty$ converges to a limit $L$ which is an irrational number that is only known as the limit of the above sequence (ie there is no other way to ...
2
votes
1answer
161 views

Solving a Min-Max problem analytically.

When studing the asymptotic behaviour of an estimator I encounter the situation that for any $a, b, c \in [0,1]^3$ a sequence $A_n$ is $$ A_n = \mathcal O\left( n^{-a} + n^{-mb} + n^{c-1} + n^{-c(q+m) ...
1
vote
0answers
44 views

minimax rate of U-statistics

I would like your expertise or recommandations for a problem I am trying to solve. Let us take $n$ $i.i.d$ samples $X_1, \cdots, X_n \sim \alpha$. Let us consider a symmetric kernel $h$ of order m. I ...
1
vote
0answers
30 views

Order Statistic - Rate of convergence

Fix some $q\in\mathbb N$ and some probability $p\in[0,1]$. Denote with $F_n$ the the q-th highest oder statistic (i.e. the distribution of the q-th highest draw) of $n$ draws from a uniform ...
1
vote
1answer
47 views

Finding rate of convergence of sequence

Let $\alpha_n$ be sequence that converges to $\alpha$. I'd like to find such numbers $c, d$ that $\alpha_n - \alpha \approx cn^-d$. I've found a solution to a similar problem - finding the order of ...
1
vote
0answers
40 views

What's the definition of “rate of uniform convergence”?

What's the definition of "rate of uniform convergence"? I'm reading "Understanding Machine Learning: From theory to algorithms". You can click the hyperlink to download the book. I came across this ...
0
votes
2answers
270 views

Convergence rate of $\alpha_n = \ln(1+\frac{(-1)^n}{n})$?

Expanding $\ln(1+\frac{(-1)^n}{n})$ into its Maclaurin series we get: $\ln(1+\frac{(-1)^n}{n}) = \frac{(-1)^n}{n} - \frac{(-1)^2n}{2!n} + \frac{(-1)^3n}{3!n} + \cdots + R$ for some remainder R. ...
0
votes
0answers
33 views

Rate of convergence of $n^x$

Rate of convergence of $r_n = n^x$ dependent on the parameter $x$. $r_{n+1}=(n+1)^x = n^x+xn^{x-1}+o(n)$ $lim_{n\to \infty}\frac{r_{n+1}}{r_n} = lim_{n\to \infty}\frac{n^x+xn^{x-1}+o(n)}{n^x} = lim_{...
0
votes
0answers
74 views

Rate of convergence in Newton's method in Numerical Optimization

i'm reading Numerical Optimization. In page 45, Newton's method: "Since $\nabla ^{2} f\left( x^{*}\right)$ is nonsingular, there is a radius r > 0 such that $\Vert \nabla ^{2} f^{-1}_{k}\Vert \...
1
vote
1answer
117 views

What's the rate of convergence of this series?

Let $$S_{n} = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} + \cdots + (-1)^{n} \frac{1}{n!} = \sum_{k=2}^{n} (-1)^{k}\frac{1}{k!}.$$ a) What does $S_{n}$ converge to? Denote the limit point ...
9
votes
1answer
154 views

Bernoulli numbers and $\pi^2$.

It is probably well-known that: $$ \lim_{n\to\infty}\frac{b_{2n}n^2}{b_{2n+2}}=-\pi^2, $$ where $b_n$ are the Bernoulli numbers. By a numerical experiment I have found that the quotient $$ \frac{b_{...
1
vote
0answers
115 views

Does Aitken's $\Delta^2$ method asymptotically improve rate of convergence?

Denoting $y_n = x_n-\frac{(x_{n+1}-x_n)^2}{x_{n+2}-2x_{n+1} +x_n}$ when $x_n\rightarrow_{n\rightarrow\infty} a $ with $p$ convergence order. I showed that $\lim_{n\rightarrow\infty} |\frac {y_n-a}{...
2
votes
1answer
1k views

Newton's Method and Aitken's Method Convergence

I'm trying to solve this problem in my Numerical Analysis class using MATLAB. Newton's Method does not converge quadratically for the following problem. Accelerate the convergence using Aitken's $\...
1
vote
1answer
59 views

Probability- $L^2 \implies \max$ tail inequality

I wonder if anyone can give a hint about whether the following is correct or wrong. If given a probability measure $P$, $D \in L^2(P)$ is a function. Is it true that $$ \max_{1\leq i\leq n} D(X_i) = ...
1
vote
1answer
84 views

How fast does $\,\big(1+\frac 1n\big)^n$ converges to e?

How fast does the sequence $(1+1/n)^n$ converge to $\mathrm{e}$? Is the difference more like $\frac1n$ or more like $\mathrm{e}^{-n}$?
0
votes
1answer
57 views

Does $2\sum\frac{1}{(2k+1)3^{2k+1}}$ converge to $\ln 2$ linearly?

Based on the fact that $$\frac{1}{2}\ln\frac{1+x}{1-x}=\sum_{k=0}^\infty\frac{x^{2k+1}}{2k+1}$$ and evaluating at $x=-1/3$, we can conclude $$\ln 2=2\sum_{k=0}^\infty \frac{1}{(2k+1)3^{2k+1}}\,.$$ ...
0
votes
0answers
28 views

What is the rate of convergence of the argmins of a sequence of uniformly convergent strictly convex functions?

From Theorem 2.1 and 2.2 in Kanniappan (1983) "Uniform convergence of convex optimization problems", if a sequence of strictly convex functions $f_n$ uniformly converge to a strictly convex function $...
0
votes
0answers
198 views

Approximating rate of convergence for ODE algorithms

I have a problem with approximating ROC for numerical algorithms for solving ODE's. It's known, that the global error for Euler's method is of order $O(h)$, and for 4th order Runge Kutta it's $O(h^4)$....
1
vote
0answers
51 views

Numerical estimation of the rate of convergence of a sequence of random variables

Let $(\Omega,\mathcal{A},\mathbb{P})$ be a probability space and $(X_n)_{n\geq 1}$ be a sequence of real valued random variables defined on $\Omega$. Suppose that there exists a sequence $a_n \...
2
votes
1answer
44 views

Comparing the grow rate of two functions with discrete domain

Consider all the possible ways to put $\{0,1\}$ in $m\in \mathbb{N}$ places. E.g., if $m=3$, then the number of possibilities is $8$ $$ \begin{pmatrix} 1 & 1 & 1\\ 1 & 1 & 0\\ 1 & ...
1
vote
1answer
1k views

Quadratic convergence of a specific iteration (Steffensen's method)

DEFINITION (QUADRATIC CONVERGENCE) : Let $\left\{x_k\right\}$ be a sequence of real numbers and $\xi \in \mathbb{R}$. We say that $x_k \to \xi$ quadratically if and only if \begin{align*} &(i) \...
0
votes
1answer
158 views

Asymptotic rate of the largest order statistic.

Let $X_1, \cdots, X_n$ be i.i.d. random variables with distribution $P$. Let $g$ be a measurable function with $P g = 0$ and $P g^2 = 1$. Show that $\max_{1 \leq i \leq n}|g(X_i)| = o_p (\sqrt{n})$. ...
2
votes
1answer
113 views

Properties of norms of inverse Hessians near a solution

In theorem 3.5 of the book on Numerical Optimization by Jorge Nocedal and Stephen J Wright, Second edition, is given the proof for the quadratic convergence to the solution of a sequence of iterates ...
4
votes
2answers
409 views

Rate of weak convergence of sin(nx)

Since $\sin(n\cdot)$ converges weakly to zero, we know that $$ \lim_{n\rightarrow\infty} \int_a^b g(x)\sin(nx)\mathrm{d}x = \int_a^b g(x)\cdot 0\,\mathrm{d}x = 0 $$ holds for all $g\in L^2([a,b])$. ...