Questions tagged [asymptotics]
Questions involving asymptotic analysis, including growth of functions, Big-$O$ notation, Big-$\Omega$ and Big-$\Theta$ notations.
8,534
questions
0
votes
0
answers
8
views
Notation for dominating (or uniformly bounded) functions
While I developing a new statistical estimator, I wondered is there any good notation for dominating (or uniformly bounded) function.
A situation like this. For some true function $f:\mathbb{R} \to \...
- 563
-1
votes
0
answers
41
views
$\frac{\Gamma(\frac{1}{2}s)}{\Gamma(\frac{1-s}{2})} = O(|t|^{\sigma - \frac{1}{2}})$
I want to prove this formula using Stirling's approximation or otherwise:$\frac{\Gamma(\frac{1}{2}s)}{\Gamma(\frac{1-s}{2})} = O(|t|^{\sigma - \frac{1}{2}})$ wher $s=\sigma+it$.
Can someone please ...
- 9
1
vote
0
answers
11
views
Asymptotic of countour integral with singularity
I need to find the asymptotic of the integral
$$\int_0^{(1+)} \left[\frac{t(e^{-i\tau/n^2}-t)}{1-t}\right]^{in-\frac{1}{2}} dt, \quad n\to+\infty,$$
where the countour starts from $t=0$, goes around $...
- 11
0
votes
0
answers
39
views
Finding an Upper bound for modulus of a function
Consider the integral $$f(s)=\int_{0}^{\infty}\frac{\left(\frac{1}{2}+ix\right)^{1-s}}{\cosh ^2(\pi x)} dx$$ where $s=\sigma+it$ and $\sigma,t\in\mathbb{R}$.
Find a Big-O upper bound for the above ...
user1073065
-2
votes
1
answer
78
views
On asymptotic of logarithm of modulus of a function
Question: I need to bound Riemann zeta function on the vertical line $s=1/2+\epsilon+it$ where $0\leq t\leq T+\epsilon$, $\epsilon>0$ is arbitrarily small and $T+\epsilon>3$ is not an ordinate ...
user1072576
1
vote
0
answers
41
views
trying to find asymptotic or approximate solutions to coupled diffusion-advection-decay equations
I am trying to solve a set of diffusion-advection equations with coupled decay (see unanswered coupled diffusion-advection-decay equations). The equations are as follows:
\begin{align}
u_t - \alpha ...
- 139
0
votes
0
answers
24
views
Asymptotics of a convoluted sum involving $r^{-\alpha}$
Let $\alpha,\beta$ be real constants satisfying $0<\alpha\leq \beta$, and let $R>1$ be an integer. Prove that
\begin{equation}\label{eq:lemma_convolution}
\sum^{R-1}_{r=1}\frac{1}{r^\beta (R-r)...
- 766
0
votes
0
answers
27
views
Is $n\cdot\frac{1}{2}^{nx}$ limited for $x\in [0,1]$ and $n\rightarrow \infty$?
I've got this qustion to answer. I know that answer is no.
My first idea is to use Big O notation, then:
$$ f(n) = n \implies O(f(n)) = n $$
$$ g(n) = \frac{1}{2}^{nx} \implies O(g(n))=?$$
And at the ...
1
vote
0
answers
25
views
determining the limiting behavior of a function defined by a Fourier transform
I need to determine this limit value
$$ \lim_{r\rightarrow 0 } \frac{\partial}{\partial r }\left\{ r \sum_{\mathbb{k} } e^{i \vec{k} \cdot \vec{r} } [k^2 +1 - k (k^2 + 2 )^{1/2}]
\right \} .$$
...
- 583
1
vote
1
answer
89
views
How to obtain logarithmic asymptotic behavior for this integral?
Let $t>0$. Also, let $\delta >0$ be very small. A physics paper claims that
$$\Re\int_0^t \int_0^t \frac{1}{\sinh^2(t_1-t_2-i\delta)} dt_1 dt_2 \approx -2 \log \left( \frac{\sinh t}{\delta}\...
- 1,807
0
votes
0
answers
48
views
Steepest descent for Linearized KdV equation
I take steepest descent on Linearzied KdV equation,
$$
u_t+u_{xxx}=0
$$
And by Fourier transform I know the phase is
$$
i(k^3+k\frac{x}{t})
$$
I want to know asymptotic of the exponential integral
$$
\...
- 63
0
votes
0
answers
27
views
Proof of logarithmic asymptotic identity
I saw the following identity here:
$$
\log(a\,b) = \Theta(\log(a + b)) = c\log(a + b),
$$
for any $a,b>1$ and some constant $c>0$ independent of $a,b$.
Could someone provide any hints why this ...
- 61
1
vote
0
answers
49
views
Asymptotic formula for divergent series $\sum_{k=1}^N \frac{1}{k^\alpha}$ [duplicate]
``Experimentally'', I have found that:
$$s_N = \sum_{k=1}^N \frac{1}{k^\alpha} \sim \frac{N^{1-\alpha}}{1-\alpha}$$
So I conjecture that:
$$s_N = \frac{N^{1-\alpha}}{1-\alpha}f(N), \qquad 0 < \lim_{...
- 307
-1
votes
0
answers
20
views
Asymptotic growth of inverse function [closed]
Let $f, g:\mathbb{R_+}\to\mathbb{R}_+$ be continuous monotonic functions, such that $f(x), g(x)\to+\infty$ as $x\to+\infty$. If $f(x)=\omega(g(x))$, is it true that $f^{-1}(x)=o(g^{-1}(x))$?
1
vote
0
answers
46
views
Prove that given $V_{n}\sim\chi^2_{n}$. Then $\frac{V_{n}}{n}$ tends in probability to $1$ as $n\to\infty$. [closed]
Prove that given $V_{n}\sim\chi^2_{n}$. Then $\frac{V_{n}}{n}$ tends in probability to $1$ as $n\to\infty$.
I´m doing this exercise and I does not know how to do it. Can anybody give me a hint?
We ...
- 89
0
votes
0
answers
20
views
"Asymptotically equal to" notation
It is unclear to me, how $\sim $and $\simeq$ are different. I suppose that both of them mean that two expressions are asymptotically equal to each other.
For example, could we write that $e \simeq \...
- 912
1
vote
0
answers
28
views
Being $X_{n}$ distributed Poisson $(\lambda_{n})$.Prove that $X_{n}$ tends in probability to 0 Also being $Y_{n}=nX_{n}$ Prove that $Y_{n}$ tends to 0
$\lambda_{n}=1/n$
Also you have to prove that they tend to $0$ when $n$ tends to $\infty$.
By definition $X_{n}$ tends to $0$ in probability when $P(|X_{n}-0|>\epsilon)$ tends to $0$ when $n$ tends ...
- 89
1
vote
1
answer
64
views
Difference between the usage of Big-Omega notation as used by Computer Scientists and Mathematicians.
I was reading Hoffstein¹, page 152. They define the counter part of the famous big-$\mathcal{O}$ notation: the big-$\Omega$,
Similarly, we say that $f$ is big-$\Omega$ of g and write,
$$f(X)=\Omega(g(...
- 371
0
votes
0
answers
19
views
Is $2^{O(\sqrt{\log (\log^3 n)})} = 2^{O(\sqrt{\log \log n})}$?
As the question states, I am reading somewhere that:
$$2^{O(\sqrt{\log (\log^3 n)})} = 2^{O(\sqrt{\log \log n})}$$
I don't quite see why, though, as $\log^3 n \neq O(\log n)$?
- 595
0
votes
1
answer
43
views
Illegal transformation of condition for asymptotes?
Obviously, the condition for two functions to be asymptotic is $\lim \bigl(f(x) - g(x)\bigr) = 0$.
But shouldn't that be equivalent to:
\begin{align}
&&\lim f(x) - \lim g(x) &= 0 \\
\...
- 9
2
votes
0
answers
54
views
Prove that $X_{n}$ converges in probability and distribution to $X$.
I´m learning about convergency in probability of a family of random variables. I think I´m not understanding the concept very well, because I can apply it on an exercise when $X_{n}$ converges to a ...
- 89
0
votes
0
answers
32
views
Can we find a constant $h$ such that $g(x)>f(x)$ for all $x>h$
Let us consider the two integer valued functions:
$$f(x)=ax^2+bx+d$$
$$g(x)=3^{x}$$
where $a,b,d$ are positive integers.
My question is: Can we find a constant $h$ such that $g(x)>f(x)$ for all $x&...
- 3,759
1
vote
0
answers
25
views
Akra-Bazzi method for $n^2/\log_2(n)$ driving function
I came across $T(n) = 3T(n/3)+8T(n/4)+n^2/\log_2(n)$ with driving function $f(x) = \frac{x^2}{\log_2(x)}$ in the CLRS 4th ed. textbook and am having a tough time applying the Akra-Bazzi method to it. ...
- 11
-1
votes
0
answers
18
views
Check if growth rate is worse than quadratic?
Let's say I have collected a dataset for estimating algorithmic complexity:
x, t
----
1, 1
2, 4
3, 9
4, 16
where x is the input size and t is the elapsed time. ...
- 99
2
votes
1
answer
60
views
Asymptotics of Laplace like integral with shrinking integration intervals
I want to find the asymptotics of the integral of the form
$$I(M) = \int_0^1 x^M e^{-M f(\frac{x}{\ln M})} dx$$
as $M \to +\infty$. Assume also that $f$ is analytic and increasing near $0$, with power ...
- 125
0
votes
0
answers
26
views
Root locus, deriving the behavior at infinity
I'm reading Control Systems Engineering of Nise, Appendice M.1, Derivation of the Behaviour of the Root Locus at Infinity (Kuo, 1987).
At one point, we have;
$$
f(s) = (1+\frac{b1-a1}{s})^{1/n}
$$
is ...
0
votes
1
answer
58
views
Comparing $n \log_2 (n) /2$ and $\log_2 n!$ asymptotically
I want to compare $n \log_2 (n) /2$ and $\log_2 n!$.
I calculated $\lim_{n\rightarrow\infty} \frac{\frac{n\log_2(n)}{2}}{\log_2 n!} = \infty$ and $\lim_{n\rightarrow\infty} \frac{\log_2 n!}{\frac{n\...
- 347
2
votes
2
answers
62
views
Exponential sum behaves like linear term for large $t$
I've done some calculations on interesting mathematical objects and came to the conclusion that they would behave nicely as expected if we would have that
$$t \sim 2\sum_{n=1}^\infty \exp(-\pi n^2/t^...
- 5,524
0
votes
1
answer
21
views
Relationship between the trace distance and the operator norm for some time dependent integral operator with kernel $K(x,y,t)$.
Let us assume that $L_{K_{t}}$ is a positive, compact operator with time dependent kernel $K(x,y,t)$.
I know that for self adjoint operators
$$ \|A\| = max_{n} |\lambda_{n}|$$
where $\lambda_{n}$ are ...
- 116
0
votes
0
answers
33
views
$\frac{\pi}{2}\tan{\frac{\pi s}{2}} = O(\log\vert s\vert)$?
In order to proof some estimations of $\frac{\zeta'}{\zeta}$ a textbook derived the formula
$$-\frac{\zeta'}{\zeta}(1-s)=-\log(2\pi) - \frac{\pi}{2}\tan{\frac{\pi s}{2}}+\frac{\Gamma'}{\Gamma}(s)+\...
- 587
3
votes
2
answers
91
views
sequence such that $x_{n+1}=n(x_n-n)$
Let $(x_n)$ be a sequence such that $x_{n+1}=n(x_n-n)$
Prove that $x_n=O(n)$ if and only if $x_1=2e$
If we have $x_n=O(n)$ then clearly $x_n=n+O(1)$ so they are equivalent.
I don't get how $x_1$ ...
- 610
1
vote
1
answer
53
views
Asymptotics of Bessel function $J_n(z)$ for $|z| \gg n$ but $|z|\not\gg n^2$
Let $\{n_j\}_{j=1}^\infty$ be a sequence of integers such that $n_j \to +\infty$, let $z_j = x_j + iy_j$ be a sequence of complex numbers approaching the real line, i.e. $x_j \to + \infty$ and $y_j \...
- 43
-1
votes
0
answers
20
views
What proportion of numbers less than $x^a$, $a>0$, are also on the order of it?
Let $x,\ x_0,$ and $y$ all be positive. I say that a number $y$ is on the order of $x$ if $Ay\leq x \leq By$ for all $x>x_0$ where $A$ and $B$ are positive constants. What proportion of numbers ...
- 73
3
votes
1
answer
61
views
Follow up question: asymptotics of a two dimensional integral
This is a follow up question of Asymptotics of a two dimensional integral about asymptotics of integrals.
The problem is to find the leading order term of this integral.
$$\int_0^1d\epsilon\int_{-\...
- 135
0
votes
0
answers
18
views
Comparison of convergence rates
I'm currently trying to compare two different types of assumptions on the convergence rate of a sequence. Let $(a_k)_{k \in \mathbb{N}}$ denote a sequence of positive real numbers. The following ...
- 137
2
votes
2
answers
45
views
Equivalent of a recurrence sequence $I_n=\frac{4n-3}{4n}I_{n-1}$
I have this sequence $(I_n)$ defined by $I_0=\frac{\pi}{2\sqrt2}$ and for all $n\ge1$, $I_n=\frac{4n-3}{4n}I_{n-1}$ (for those interested, it comes from $I_n=\int_0^1 \frac{t^n}{t^{3/4}(1-t)^{1/4}}{\...
- 4,676
1
vote
1
answer
35
views
How to show that $\forall n \geq 1$, $\frac{n^{2n}}{n!^2} \geq (\frac{n+1}{n})^{n^2-n}$?
I tried using the fact that $(n+1)/n \leq 2$ and thus $\frac{n^{2n}}{n!^2} \geq 2^{n^2-n}$ but this does not seem to be true.
- 13
2
votes
1
answer
39
views
Computing the asymptotics of a principal value integral
I have been looking at the following principal value integral (with $x>0$ and $0< \sigma < 1$)
$$
\mathrm{P.V.} \int_0^\infty \frac{v^{-\sigma} e^{-x v}}{1 - v} dv,
$$
and I would like to ...
- 185
1
vote
0
answers
40
views
Asymptotics of function from asymptotics of antiderivative
If $f$, $g$ are positive functions, $f(x)\sim g(x)$ for large $x$ means that $\lim_{x\rightarrow \infty}f(x)/g(x)=1$.
In the book "The Riemann Zeta function" by H. M. Edwards, in Chapter 4, ...
- 800
2
votes
0
answers
87
views
Flipping $n$ sticky coins until they are all heads
Consider a collection of $n$ coins, of which $k$ initially are heads. These coins are "sticky" and, when flipped, remain the same with probability $p > 1/2$, and flip over with ...
- 21
0
votes
0
answers
21
views
Why does a given image value of a function $x H^3(x)$ where $H(x)$ contains hypergeometric functions have preimage value?
Prof. Edward B. Bender is a famous combinatorial mathematician. In his paper of A Survey of Asymptotic Behaviour of Maps published in Journal of Combinatorial Theory, there is a part of analyzing the ...
- 355
0
votes
0
answers
15
views
Prove or disprove this statement about asymptotic relation between functions.
Let $f,g,h: \mathbb{N} \to \mathbb{N}$ be an increasing functions.
Prove or disprove these statements:
a) if $f(n)=\Theta(g(n))$ then $\max\{f(n),g(n)\}=\Theta(\min\{f(n),g(n)\})$.
b) if $f(n)=\...
- 2,051
0
votes
1
answer
25
views
Find mle of theta from some mixed density
I'm trying to find a mle from:
$$ P_\theta(x) = (1 + \theta) I(0 \leq x \leq 1/2) + (1 - \theta) I(1/2 < x \leq 1)$$
Then,
\begin{align*}
L(\theta) &= \Pi_{i=1}^n P_\theta(x_i) = (1+\theta)^k (...
- 437
2
votes
1
answer
81
views
Asymptotics of a two dimensional integral
I am working on the following integral
$$\int_0^1d\epsilon\int_{-\epsilon}^\epsilon dt\left(\sqrt{1-(\rho+t)^2}-\sqrt{1-\rho^2}\right)e^{-N t^2},$$
where $\rho=1-\epsilon$, $N\rightarrow \infty$. The ...
- 135
4
votes
2
answers
92
views
Slight variation of Mertens' third theorem. Do we have an estimate of $\sum_{d \mid n\#}(-1)^{\omega(d)}\dfrac{\sigma_0(d)}{d}$?
Define $f(n)$ to be:
$$
\sum_{d \mid n\#}(-1)^{\omega(d)}\dfrac{\sigma_0(d)}{d}
$$
But $\sigma_0(d) = 2^{\omega(d)}$ for any $d \mid n\#$ a primorial, so:
$$
f(n) = \prod_{p \text{ prime} \\ p \leq n} ...
- 19.2k
1
vote
0
answers
31
views
Generalized Master Theorem (Divide-and-Conquer) using Ceil / Floor
I'm a bit tired of virtually all books deriving the master theorem always using their own variation: They sometimes use inequalities $T(n)< T(\frac{n}{b})+f(n)$, sometimes are more sloppy and use $\...
- 92
2
votes
2
answers
65
views
Asymptotics of an integral with singular derivation
I want to evalute the leading order term of the following integral as a series of $1/N$ and $\epsilon$,
$\int_{-\epsilon}^\epsilon dt (\sqrt{1-(\rho+t)^2}-\sqrt{1-\rho^2})e^{-N t^2}$, where $\rho=1-\...
- 135
0
votes
0
answers
28
views
Conditions and correct interpretation of Borel summation
Hello to the community.
In my line of research (theoretical particle physics) it is customary to apply the strategy of Borel summation to infinite power series in order to find closed forms and/or ...
1
vote
2
answers
47
views
Possible growth rates of a matrix entry with respect to exponentiation
Let $A = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}$, so $A^n = \begin{pmatrix}1 & n \\ 0 & 1\end{pmatrix}$. Thus, $(A^n)_{1,1} = 1 = \Theta(1)$, and $(A^n)_{1,2} = n = \Theta(n)$.
...
- 2,170
0
votes
2
answers
40
views
Expansion of logarithm with little o
Prove that
$$
\ln (1+z+o(z))=z-\frac{z^{2}}{2}+o\left(z^{2}\right), \quad z \rightarrow 0.
$$
My attempt is to use Taylor's expansion, so we get
$$\ln (1+z+o(z))=z+o(z)+o(|z+o(z)|^2).$$ What are ...
- 1