Questions tagged [asymptotics]
For questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.
9,485
questions
3
votes
1
answer
387
views
Hoeffding for bounded random variables, extension of Rademacher case
In Vershynin's High-Dimensional Probability, he first proves the Hoeffding bound on page 17
$$\mathbb{P}\left\{\sum_{i=1}^N a_iX_i \geq t\right\} \leq \exp \left(
-\frac{1}{2} \frac{t^2}{\|a\|^2_2}...
- 28.1k
3
votes
2
answers
152
views
Is $(n+1)! = \mathrm{o}(n^n)$?
Continuing http://math.stackexchange.com/a/2431263, it seems to me that you can prove with the same method that $(n+1)! = o(n^n)$.
Namely:
Let $a_n=\frac{(n+1)!}{n^n}$. Then:
$$\frac{a_{n+1}}{a_n}=...
user691231
3
votes
1
answer
134
views
Asymptotics of Binomial Transform of a Sequence
I have a sequence of nonnegative integers $w(k)$ that I know grows asymptotically as $$w(k)\sim C\frac{\rho^k}{k^\alpha}.$$ Here, $C\approx 3.422$, $\rho\approx 4.729$, and $\alpha\approx 4.515$ are ...
- 1,287
3
votes
2
answers
118
views
Asymptotic expansion of $Li^{-1}$ and zeros of $F(s)$ and $G(s)$
If you downvote please leave some constructive feedback.
I would like to compare and visualize/gain insight about the zeros of two functions, $F(s)$ and $G(s).$ $\pi(m)$ is the prime counting ...
- 1,080
3
votes
1
answer
170
views
Sharp bounds for the principal branch of the Lambert W function?
I'm looking for references for bounds on the principal $W_0$-branch of the Lambert W-function, specifically in the range $[ -\frac 1e, 0)$. I'm trying to work with the expression $W(-xe^{-x})$ with $x ...
- 6,128
3
votes
2
answers
81
views
Is n O(n)? Is n Ω(n)?
I have a homework assignment (though this isn't part of it!) which I want to be sure on. This may be a stupid question.
The functions in question are $f(n) = 2^n$ and $g(n) = 3^n$. I'm pretty sure ...
3
votes
2
answers
563
views
Bessel integral asymptotics
I'm looking at the integral
$$I(\alpha,f)=\int_{-\pi}^\pi K_0 \left ( \alpha \sqrt{1+f(x)^2-2f(x)\cos(x)} \right ) dx.$$
Here:
$\alpha \gg 1$.
$f$ is a smooth, $2\pi$-periodic function. $f(0)=1$. ...
- 102k
3
votes
1
answer
4k
views
Solving a recurrence relation with floor function
I'm having trouble solving this recurrence relation:
\begin{align}
T(n) &=
\begin{cases}
2\,T\big(\big\lfloor \frac{n}{\sqrt{2}} \big\rfloor - 5\big) + n^\frac{\pi}{2} &\text{if } n > 7 \\
...
- 549
3
votes
1
answer
309
views
Asymptotics of Hilbert transform from asymptotics of original function
Suppose we have a locally integrable function $f: \mathbb R^+ \to \mathbb R$ and we consider the 'Hilbert transformed' function
$$ h(t) := \int_0^\infty \frac{f(\tau)}{t -\tau} \mathrm d \tau. $$
We ...
- 1,416
3
votes
1
answer
75
views
Rigorous derivation of the long-time limit of oscillatory integrals
I am trying to estimate the following integrals in the limit $t\to+\infty$:
$\displaystyle\int_{-\infty}^{+\infty}\mathrm d\omega\,f(\omega)\frac{1-\cos(\omega t)}{\omega^2}$ and $\displaystyle\int_{-...
- 95
3
votes
1
answer
195
views
A bound for a sum over square-free numbers: $\sum_{n \leq X} \frac{\mu(n)^2 \tau_k(n)}{\phi(n)} \ll (\log X)^k$
How can one show that $$\sum_{n \leq X} \frac{\mu(n)^2 \tau_k(n)}{\phi(n)} \ll (\log X)^k \ ?$$ Here, $$\tau_k(n) = \sum_{\substack{d_1,d_2, \dots, d_k \in \mathbb{N} \\ d_1d_2\cdots d_k=n}} 1.$$ I'm ...
- 2,124
3
votes
1
answer
77
views
What does f(n) and g(n) mean in this question?
The question I’m trying to answer is about asymptotic inequality.
The question states,
If $f(x)$ and $g(x)$ are polynomials with respective leading terms $ax^{n}$ and $bx^{m}$ then $\frac{f(n)}{g(n)} ...
- 93
3
votes
1
answer
301
views
Degenerate Eigenvalue Perturbation
Suppose we want to approximate the eigenvalue problem
$$\left(A+\varepsilon B\right)x=\lambda x,$$
where
$$ A=\begin{bmatrix}1&1&0\\0&1&0\\0&0&-1\end{bmatrix},\qquad B=\begin{...
- 537
3
votes
1
answer
252
views
Approximation of a root of a polynomial of degree k
I know that solving every polynomial of degree higher than 5 is not possible via a closed formula. However, how is it possible to find an approximation for $x_{k, a}$ the biggest positive root of
$$P(...
- 1,671
3
votes
1
answer
292
views
Asymptotic expansion of the sum $ \sum\limits_{k=1}^{n} \frac{\binom{n+1}{k} B_k}{ 3^k-1 } $
The situation :
I am looking for an asymptotic expansion of the sum $\displaystyle a_n=\sum_{k=1}^{n} \frac{\binom{n+1}{k} B_k}{ 3^k-1 } $ when $n \to \infty$.
(The $ B_k $ are the Bernoulli numbers ...
- 237
3
votes
1
answer
134
views
Has asymptotic analysis become an archaic subject? If so, why?
Every applied math survey book I have which was written before the 1980s has an extensive treatment of asymptotic analysis; some of the older physics and engineering literature uses it liberally. Yet ...
- 4,775
3
votes
1
answer
178
views
Asymptotics of a double integral
I want to calculate the asymptotic form as $x\to 0$ of the following integral.
\begin{alignat}{2}
I_2(x) = \int_0^{\infty}du\int_0^{\infty}dv\, \frac{1}{(u+v)^{\frac{3}{2}}}\exp\left(-\frac{x}{u+v}\...
3
votes
2
answers
9k
views
Question about proof that $n! = \omega(2^n)$
I'm reading CLRS and have came across this sub-question:
Proof that $n! = \omega(2^n)$
I have seen several solutions that are more or less the same as the one stated here. The solution simply says
...
- 14.4k
3
votes
1
answer
227
views
Asymptotic expansion of the given integral
How to find the first few terms in the asymptotic expansion of the given integral, as z tends to infinity, $$\int_0^\infty dt \left\{\frac{t-(e^ t -1)}{t(e^ t-1)}+1/2 \right\}e^{-tz} $$ Does this ...
- 117
3
votes
1
answer
60
views
A question concerning dot product of sequences with a specific asymptotic growth.
This question was posted/originated after a failure of a more generic attempt here:
Let $\alpha_n$ be a sequence of positive Reals. It is known that $$\alpha_n \sim \log(n)$$
Let $\beta_n$ be ...
- 4,247
3
votes
1
answer
69
views
Estimate $\sum_{j=0}^{n} \dfrac{1}{(j+1)(n-j+1)}$.
Estimate,
or give an exact formula for
$g(n)
=\sum_{j=0}^{n} \dfrac{1}{(j+1)(n-j+1)}
$.
This comes from my answer here:
Cauchy product of $\sum\limits_n^{\infty}\frac{1}{n}$ with itself
Numerical ...
- 108k
3
votes
3
answers
75
views
Which one is bigger for large value of $n$?
I stumbled upon this question, among $n^{\frac{7}{4}}$ and $n(\log^9(n))$, which one is bigger?
I think that leaving out n from both leaves $n^{\frac{3}{4}}$ and $\log^9(n)$.
Now let's take $n^{\...
- 471
3
votes
1
answer
248
views
Asymptotics of a double integral: $ \int_0^{\infty}du\int_0^{\infty}dv\, \frac{1}{(u+v)^2}\exp\left(-\frac{x}{u+v}\right)$
I want to calculate the asymptotic form as $x \to 0$ of the following integral.
\begin{alignat}{2}
I_2(x) &=&& \int_0^{\infty}du\int_0^{\infty}dv\, \frac{1}{(u+v)^2}\exp\left(-\frac{x}{u+v}...
- 299
3
votes
2
answers
536
views
An asymptotic expansion involving the gamma function in QFT
In quantum field theory a common term that arises for which we require an expansion is,
$$\frac{\Gamma(2-d/2)}{(4\pi)^{d/2}}\left(\frac{1}{\Delta} \right)^{2-d/2} = \frac{2}{\epsilon}-\log \Delta - \...
- 1,766
3
votes
1
answer
289
views
Asymptotic Expansion or Perturbation of an Ordinary Differential Equation
Consider the following ordinary differential equation.
$$u''+f(u)=0, \tag1$$
where $''$ stands for second derivative, and $f\in C^1(-\infty,\infty)$, $f(0)=0,\,f'(0)=1$.
Multiply both sides by $u'$ ...
- 9,822
3
votes
1
answer
13k
views
Solve $T(n) = 3T(n/4) + n$ with iteration technique only
Solve $T(n) = 3T(n/4) + n$ with iteration technique only
I've got a solution for this one, but I did not understand what is pointed in red there, can anyone please explain how they did it?
- 4,128
3
votes
1
answer
173
views
What's about $\sum_{n=1}^\infty\frac{\mu(n)}{n}r^n,$ when $0<r<1$?
I am interested in
Question. It is possible to get an expression or bounds (upper and lower bounds) for $$\sum_{n=1}^\infty\frac{\mu(n)}{n}r^n,$$
where $0<r<1$ is a fixed real, and $\mu(n)$...
user243301
3
votes
2
answers
466
views
asymptotics of the Gamma function and remainder
I have found the following asymptotic formula in a book:
$$\lim_{\vert y\vert\rightarrow\infty}\vert \Gamma(x+iy) \vert e^{\frac{\pi}{2}\vert y\vert}\vert y \vert^{\frac{1}{2}-x}= \sqrt{2\pi}. $$
I ...
- 645
3
votes
1
answer
601
views
Asymptotic analysis references
I'm self studying asymptotic analysis with
Bruijn (1981) - Asymptotic Methods in Analysis
Bleistein and Handelsman (1986) - Asymptotic Expansions of Integrals
but the texts are terse, without too ...
- 10.5k
3
votes
2
answers
851
views
Minimize a particular function in one variable
For given $a,b$, what is the minimum value of the following expression?
$$
\frac{a}{x^2+b}+x,\qquad x>=0, a>0,b>0
$$
Differentiating the above gives a messy polynomial.
I tried plugging ...
- 378
3
votes
1
answer
2k
views
Asymptotic distribution of zero-drift Geometric Brownian Motion as $t \to \infty$
If we fix the drift at $\mu = 0$, then my geometric brownian motion will have stationary mean, but it seems that the variance will grow without bound. What does the limiting distribution look like for ...
user237392
3
votes
1
answer
195
views
What is known about the asymptotics of Riccati's equation?
I'm interested in examining the asymptotic behavior of Riccati equations of the form
$$
y'(x) = f(x) + g(x) y^2(x)
$$
for $x \to \infty$. I've done some digging but I can't seem to find a simple ...
- 1,058
3
votes
1
answer
240
views
Asymptotic lower bound for R(k,k)
I'm reading Spencer's lectures on the probabilistic method. Using the Lovasz local lemma, we've shown that $R(k,k)>n$ if
$$
4{k \choose 2} {n \choose k-2} 2^{1-{k \choose 2}} < 1.
$$
Now I'm ...
- 3,530
3
votes
2
answers
147
views
Asymptotic complexity of sum of poly-logarithmic functions
I'm trying to figure out what's the asymptotic complexity for the following sums:
$$\sum_{k=1}^n lg^s k$$
$$\sum_{k=1}^n k^rlg^s k$$
s and r are positive constants.
I think i should be using ...
- 143
3
votes
1
answer
370
views
Twin prime conjecture implies $\limsup_{n\to\infty}\frac{\sigma(n)\pi(n)}{n^2}\left(\pi(\log n)-\frac{\pi_2(\log n)}{2C_2}\right)=e^{\gamma}$?
Let $\sigma(n)$ the sum of positive divisor function, $\pi(x)$ is the prime counting function, $\pi_2(x)$ is the twin prime counting function (we will assume that Twin prime conjecture holds), $C_2$ ...
user243301
3
votes
1
answer
131
views
Non linear second order ODE
I really need help solving this :
$$y_{xx}-\left(y^{3}-y\right)-\varepsilon\frac{1}{2}\left(1-y^{2}\right)=0
$$
With boundary conditions :
$$ y(\pm \infty )=-1 $$
I need to find a solution that ...
- 435
3
votes
1
answer
307
views
What are the bounds (upper and lower) for $|A+A|$?
Let $A$ be a finite set of real (or complex) numbers. If I consider sets with small sizes, we have that:
If $A$ is the empty set, then $A+A$ is also empty.
If $A$ is a singleton, then $A+A$ is ...
- 18.3k
3
votes
1
answer
128
views
Find this limits $\lim_{n\to\infty}n^2\bigl(n(H_{2n}-H_{n}-\ln{2})+\frac{1}{4}\bigr)$
Question1:
Find this limits
$$\lim_{n\to\infty}n^2\left(n(H_{2n}-H_{n}-\ln{2})+\dfrac{1}{4}\right)$$
where $$H_{n}=1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}$$
Question 2:
Can we obtain a ...
- 93.4k
3
votes
1
answer
253
views
Improvements of Dusart's lower bound for $ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}$.
Let $\gamma$ be the Euler-Mascheroni constant.
In this paper (Theorem 6.12) it is proved that for $x\ge 2793$, $$ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}> 1-\frac{1}{5 \left(\log x\right)^2+1}...
- 7,249
3
votes
1
answer
79
views
Is the Pattern in the Number of Digits in the Bernoulli Numbers Showing Something Significant
For the first couple of powers of $10$, the number of digits in these show a certain pattern, is this a coincidence or is their a reasonable explanation. Specifically if we look at
$$ \lfloor \log_{10}...
- 1,046
3
votes
3
answers
57
views
Growth of fraction of products with $\sqrt{n}$ terms
Is the growth of $$f(n):=\dfrac{(n+1)(n+2)\ldots(n+\sqrt{n})}{(n-1)(n-2)\ldots(n-\sqrt{n})}$$ polynomial or not? That is, does there exist constants $k,m$ such that $$f(n)<n^k$$ for all $n>m$?
- 1,735
3
votes
1
answer
284
views
How to find asymptotics of this sum
Is there any way to find $f(n)$ in this term: $$\sum_{k=2}^n \frac1{\ln \ln(k!^{k!})} \sim f(n)?$$
The tilde symbol means that $$\lim_{n\to∞} \frac{f(n)}{\sum_{k=2}^n \frac1{\ln \ln(k!^{k!})}} = 1$$
- 89
3
votes
2
answers
347
views
Is there a closed form for $\sum_{j=1}^{n} j^2\log{j}$?
Question
Is there a closed form for $\sum_{j=1}^{n} j^2\log{j} = 1\times0 + 2^2\times\log{2} + 3^2\log{3} + \dots + n^2\log{n}$? I'm trying to look for the simplest $\Theta$ notation.
Attempt
Let $g(n)...
user99297
3
votes
1
answer
110
views
Asymptotic analysis of an integral with growing, highly oscillatory integrand
I recently came across the following integral
$$\int_0^{\omega} t^{\frac{n-1}{2}}|\cos(t^n)|\,dt.$$
Here $n>1$ is an integer. I was curious as to what its asymptotic form would be. It seems to be ...
- 29.5k
3
votes
1
answer
829
views
Source needed: Does asymptotic normality yield asymptotic unbiasedness and consistency?
Assume that $$\sqrt{n}(\hat g - g(\theta)) \xrightarrow{d} Z, $$ where $Z$ is $N(0,\sigma^2)$.
Does this already imply asymptotic unbiasedness and/or consistency, i.e.,
$$ E[\hat g] \rightarrow g(\...
- 2,096
3
votes
2
answers
222
views
Integration by expansion
Consider the integral
\begin{equation}
I(x)= \frac{1}{\pi} \int^{\pi}_{0} \sin(x\sin t) \,dt
\end{equation}
show that
\begin{equation}
I(x)= \frac{2x}{\pi} +O(x^{3})
\end{equation}
as $x\rightarrow0$....
- 311
3
votes
2
answers
45
views
Existence of $f_n(t)=o(f(t))$ where $(f_n)$ is a sequence of functions.
Let $(f_n)$ a sequence of functions over $\mathbb{R}$ to $\mathbb{R}$,
Show that there exist $f:\mathbb{R} \rightarrow \mathbb{R}$ such that $f_n(t)=o(f(t))$
I suspect that $f_n$ converges pointwise ...
user117932
3
votes
1
answer
216
views
Scaling a function with two 'asymptotes' of which one is non-constant
I have a bunch of curves that look roughly like the example below. Each curve has two 'asymptotes' a constant value for $x\rightarrow0$ and a linear curve for $x\rightarrow\infty$ (although, as in the ...
- 414
3
votes
1
answer
417
views
Big O proof of Fourier Coefficient
Let $f(x)$ be a $2\pi$ periodic function on R. Assume that Hölder continuous:
$$\sup_{x\neq y} \frac{|f(x)-f(y)|}{|x-y|^{-\alpha}} \leq C$$
for some constants $C$ and $\alpha \in \,]0,1]$. Prove ...
- 101
3
votes
1
answer
406
views
Explanation for Terry T. post
I read here that : " If one inserts these inequalities into the Legendre sieve and optimises the parameter, one can improve the upper bound for the number of primes in $[N,2N]$ to $$O \left(\frac{N \...
- 9,115