Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

learn more… | top users | synonyms (1)

0
votes
1answer
25 views

Behaviour of modified Bessel function of the first kind $I_{\nu}(x)$

As stated in the comments to my previous question, the modified Bessel function of the second kind can be defined as $$K_{\nu}(x) = \frac{\pi}{2}i^{1 + \nu} (J_{\nu}(ix) + iN_{\nu}(ix))$$ The ...
0
votes
2answers
33 views

Prove or disprove: $(\ln n)^2 \in O(\ln(n^2)).$

Prove or disprove: $(\ln n)^2 \in O(\ln(n^2)).$ I think I would start with expanding the left side. How would I go about this?
2
votes
1answer
26 views

asymptotic approximation for number of partitions of integer that do contain 1 nor 2

Hardy and Ramanujan provided a famous asymptotic approximation to $P(n)$ the number of partitions of an integer $n$ when $n$ gets large. I wonder if there is an asymptotic approximation to ...
10
votes
2answers
275 views

Proof of $\sum_{n=1}^{\infty} \frac{x^n \log(n!)}{n!} \sim x \log(x) e^x$ as $x \to \infty$

Prove that $$\sum_{n=1}^{\infty} \frac{x^n \log(n!)}{n!} \sim x \log(x) e^x \,\,\,\text{as}\,\,\, x \to \infty$$ and $$\sum_{n=1}^{\infty} \frac{(-x)^n \log(n!)}{n!} \to 0 \,\,\,\text{as}\,\,\, x \to ...
2
votes
0answers
38 views

Linear convex combinations of $Li(x)=\int_2^x\frac{1}{\log(t)}dt$ and $\frac{x}{\log(x)}$, and prime counting function

Can provide us a linear convex combination of $Li(x)=\int_2^x\frac{1}{\log(t)}dt$ and $\frac{x}{\log(x)}$ a better approximation for $\pi(x)$, the prime counting function? Or not, is better $Li(x)$ ...
0
votes
0answers
11 views

Asymptotic form - Kummer function

Can anyone tell me whether 'a' can be complex or not? Does 'large a' mean large |a| or large REAL a? \http://dlmf.nist.gov/13.8
2
votes
0answers
23 views

Relation between Big O and convergence in limit of a sequence of probabilities

I'm confused on the procedure used to show the theorem 5.52 in van der Vaart "Asymptotic Statistics" p.75. Here the simplified idea. Consider the sequence of real-valued positive random variables ...
2
votes
0answers
28 views

Signs and stochastic big O notation

I'm confused on the relation between stochastic big O notation and signs. In order to illustrate my question: (1) consider a sample of i.i.d. real-valued random variables $\{X_i\}_{i}^n$, each with ...
0
votes
0answers
44 views

Prove that $2^{n+100} = O(2^n)$

Having trouble proving this for Big Oh. just dont know where to start with this one. I learn the basics over big oh notation so for this one, would i have so if $s(n) = 2^{n+100}$ and $a(n) = 2^n$ , ...
5
votes
2answers
4k views

Central Limit Theorem and sum of squared random variables

This is a two-part question. Suppose I am drawing random variables $X_i\sim A$, $1\leq i \leq n$ where $A$ is a zero-mean, finite variance $\sigma_A^2$, symmetric probability distribution having ...
0
votes
0answers
51 views

WKB Approx. Exercise for 2nd Order ODE

Working with the following ODE: $y'' - \frac{1}{2}y' + (\frac{1}{16} + x - e^x)y=0$ W.T.S. there are solutions of the form: $y_1 = ${1+O$(xe^{-x/2})$}$exp(-2e^{x/2})$ and $y_2 = ...
2
votes
0answers
45 views

Asymptotic analysis of non-linear ODE

I'm looking for references on the topic of asymptotic analysis of non linear ODE's of the sort $$ x'' + x'x = 0 $$ This specific case has an analytic solution (with some $\tanh(\cdots)$ involved) and ...
0
votes
0answers
14 views

how to find asymptotic joint distribution of two linear combination of order statistics?

Suppose I have n order statistics from some unknown continuous distribution funciton F(x), $X_{1}\leqslant X_{2}\leqslant...\leqslant X_{n}$. And I have two linear combination of these order ...
0
votes
1answer
20 views

Big-Omega: $\forall x, y \in N: y \in \Omega(x) \rightarrow y^3 \in \Omega(x^3)$

I am currently stuck on the following question: $$\forall x, y \in N: y \in \Omega(x) \rightarrow y^3 \in \Omega(x^3)$$ $$ x^3: x^3(n) = x(n) * x(n) * x(n) $$ $$ y^3: y^3(n) = y(n) * y(n) * y(n) $$ ...
0
votes
0answers
45 views

Does sin(x)/x have a singularity at 0?

I'm pretty sure the answer is no, since it limits to 1, by L'hopital's rule, so it stays bounded. But a solution that I am comparing my work to claims that 0 is a singularity for sin(x)/x. I am ...
4
votes
1answer
162 views

Giving tight asymptotic bounds for $T(n)=T(\frac{n}{\log n}) + \log\log n$

I don't like coming here for such matters, but this is a homework problem from my Analysis of algorithms class. I've come along the Akra-Bazzi method and different variations on the matter , read ...
0
votes
2answers
33 views

Solving recurrence using recurrence trees.

I have a recurrence which I know has the solution $O(\lg n)$, it looks like this: $$T(n) = T(\sqrt n) + \lg n$$ If I understand correctly, the recurrence tree method involves looking for the term ...
2
votes
1answer
44 views

Why does the floor function $x \mapsto \lfloor x \rfloor$ have expansion $x + O(1)$?

Shouldn't it just be the largest previous integer? Why is there a remainder term $O(1)$? Thanks, Edit: I am working on a problem that uses the Abel summation formula, and the integration part of ...
0
votes
1answer
47 views

Prove $\log(n) = O(n)$ using induction

I am using the lecture notes here on page 19 (Algorithm Notes 1) example 1 is the inductive proof of $\log(n) = O(n)$. I understand the base case but I don't understand the rest of the example. ...
0
votes
0answers
50 views

Calculating Running Time (in seconds) of algorithms of a given complexity

I've tried to find answers on this but a lot of the questions seem focused on finding out the time complexity in Big O notation, I want to find the actual time. I was wondering how to find the ...
0
votes
0answers
9 views

Operations with stochastic little o

In deriving some results I arrived to this expression: $$ A_n=n*o_p(||\frac{h_n}{\sqrt{n}}||)+o_p(1) $$ where $h_n$ is a random vector of dimension $l \times 1$, $\{h_n\}_n=O_p(1)$, $||\cdot ||$ ...
1
vote
1answer
16 views

Growth rate of two functions

It's obvious that $x^2>2x+1$ for $x\ge 3$ - we just observe that for $x\ge3$, $3^2>2\cdot 3+1$ and the LHS grows much faster than the RHS. But how to determine: how faster does the LHS grow (and ...
4
votes
2answers
65 views

If an eventual inequality holds for $f$ and $g \sim f$ then does it hold for $g$?

Suppose $f$, $g$, are non-negative functions such that $f \sim g$ (meaning that $f(x)/g(x) \to 1$ as $x \to \infty$). If for all $\lambda > 1$ there exists an $\eta > 0$ such that $$f(\lambda ...
1
vote
0answers
31 views

Big O Notation Clarification

Working through a textbook on algorithms (CLRS intro to algorithms) and just wanted to see if someone could help me understand one of the exercises at the end of a chapter. Problem: Is $n^{2 + 1} = ...
1
vote
1answer
58 views

Is this number in $O(\log(n))$?

Is this number $\big[\log(n) + \sum_{j=1}^{n-1} (\log(j) - (j+1)(\log(j+1)) + j \log(j) +1)\big] \in O(\log(n))$? I simplified it to $\big[\log(n) + \sum_{j=1}^n (-\log(n+1) - j(\log(n)) + 1)\big]$.
0
votes
0answers
19 views

Operations with stochastic big and little o

I have a question related to stochastic little/big o notation. Consider a sequence of real-valued random variables $\{X_n\}_n$. Is it correct $O_p(1)+X_no_p(1)=O_p(1)$ ? Why? I know that ...
1
vote
0answers
12 views

asymptotic normality of m-estimator

I' struggling with an argument in van der Vaart proof of theorem 5.21 at p.52: ...
0
votes
1answer
16 views

Combining deterministic and stochastic asymptotics

Consider a sequence of real-valued random variables, $\{X_n\}_{n}$. Suppose that (*) $X_n \rightarrow_p X$. Consider $\lim_{n \rightarrow \infty} P(X_n>0)$. What I have seen doing in ...
2
votes
0answers
85 views

Asymptotic expansion of integral of $e^{-t}/t^n$.

So we study $$f_{n}(x) = \int_x^{+\infty} \! \frac{e^{-t}}{t^{n}} \, \mathrm{d}t, \quad n \in \mathbb{N^{*}}.$$ I've shown that for every $n$, $f_{n}(x) \sim_{+\infty} \frac{e^{-x}}{x^{n}}$. Now ...
3
votes
1answer
25 views

Big Theta with Negative Coefficient Problem

I had a question in regards to solving a Big-Theta problem. Our professor wanted us to prove that $n^3 - 47n^2 + 18 = \Theta(n^3)$ and to do so rigorously, meaning he does not want us to use the below ...
0
votes
1answer
9 views

Supremum transformations with stochastic convergence

Consider a sequence of real-valued random variables depending on a parameter $\theta \in \Theta \subseteq \mathbb{R}$, $\{X_n(\theta)\}_{n}$. Suppose that (*) $X_n(\theta)\rightarrow_pX(\theta)$ ...
0
votes
0answers
32 views

The ratio of two asymptotically normal distribution

Let $(X,Y)$ be asymptotically normal with their means, variances, and a covariance. Then, I would like to show $X/Y$ is also asymptotically normal. I think there should be some references related to ...
1
vote
0answers
20 views

Three term inner and outer solution to a boundary layer problem

I am unsure how to proceed with the current equation to determine a three-term outer expansion and three-term inner expansion due to the nature of the equation. Equation: $\epsilon ...
0
votes
1answer
27 views

determine two-term outer, inner and uniform expansions

Consider the equation; determine the two-term outer, inner and uniform expansions assuming that $0<\epsilon<<1$ $$\epsilon \frac{d^2y}{dx^2}+\frac{dy}{dx}+y=0, \hspace{5mm} ...
0
votes
2answers
19 views

Is this easy to prove? $\forall N, k \gt 0$, $\pi(x) - \pi(N) \gt \frac{x-N}{2k}$ for all sufficiently large $x$.

Let $\pi(x)$ be the prime counting function. Knowing that $\pi(x) \sim \dfrac{x}{\ln x}$. How could you prove that $\pi(x) - \pi(N) \gt \dfrac{x - N}{2k}$ for all $x \geq $ some $X_0$? I think ...
0
votes
1answer
17 views

Summation of big oh terms

I read about asymptotic notation .I understood the limit definition of big oh notation.But while going about calculating O(1)+O(2)+.......…..+O(n),the sum comes out to be O(n ^2).Can anyone explain ...
1
vote
2answers
23 views

Delta Method corollary

Consider the Delta Method as stated in van der Vaart Theorem 3.1 at page 26 (you can find the page here ...
0
votes
0answers
25 views

Asymptotic expansion using method of steepest descents

I am trying to find the first term in the asymptotic expansion of $$\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}\frac{1}{s^2}e^{t(s-m\sqrt{s^2-1})} ds $$ where $0<m<1$, $c<1$, as $t$ ...
0
votes
0answers
60 views

Asymptotics for the probability a discrete Brownian bridge remains below a logarithmic barrier

Let $(\mathcal{Z}(i))_{1\leq{i}\leq{\text{N}}}$ be a discrete Brownian bridge of lifespan $\text{N}$ conditioned to start and end at $0$, i.e. $\mathcal{Z}(1)=0$ and $\mathcal{Z}(\text{N})=0$. I would ...
0
votes
1answer
24 views

Definitions On Landau Notation (Big O and little o)

What are the definitions on Big O and little o for when $x \in R^m$ approaches $s\in R^m$ And not $x$ going to infinity?
0
votes
0answers
12 views

Decay of a Fourier Transform with parameter

Given $t>0$, consider the following function $f_t:\mathbb{R}\rightarrow\mathbb{C}$ $$f_t(x)=\begin{cases}e^{-tx-itx^2}&x\geq 0\\ 0&x<0\end{cases}$$ Now, let $\widehat{f_t}$ the Fourier ...
1
vote
1answer
27 views

gamma function with negative argument

For $k=0,1,2...$ and small $z$ I want to show that $$\Gamma (-k + z) = \frac{ a_k}{z} + b_k + O(z).$$ I understand that the gamma function cannot be expressed as $$\Gamma ( z) = \int_0 ^\infty ...
0
votes
1answer
43 views

First order, inner, outer and uniform approximations of boundary layer problem

$\epsilon \frac{d^2y}{dx^2}+2\frac{dy}{dx}+2y=0, y(0) = \alpha, y(1) = \beta$ Since we have the general form: $\epsilon \frac{d^2y}{dx^2}+a(x)\frac{dy}{dx}+b(x)y=0$ we can see that $a(x) = 2 >0$ ...
1
vote
1answer
132 views

Derivation of a generalization of Mertens' Third Theorem.

One of Mertens' Theorems states $$\prod_{p\le x}(1-\frac{1}{p})\sim \frac{e^{-\gamma}}{\ln(x)}.$$ I have seen a generalized version that states $$\prod_{m<p\le x}(1-\frac{m}{p})\sim ...
0
votes
1answer
18 views

Convergent, Bounded, O(1) sequences

Consider a sequence of real numbers $\{a_n\}$ and these 3 definitions: (1) $\{a_n\}$ is bounded: $\exists k>0$ s.t. $-k \leq a_n\leq k$ $\forall n \in \mathbb{N}$ (2) $a_n=O(1)$: ...
0
votes
1answer
135 views

Average number of square free divisors for $n\leq x$

Let $d_{sf}(n)$ be the number of square-free divisors of $n$, and let $D_{sf}(k)=\sum_{n=1}^{k} d_{sf}(n)$ denote the corresponding summation function. Mertens showed that the asymptotic expansion of ...
2
votes
1answer
57 views

Find location and width of boundary layer

Consider the boundary value problem $$\varepsilon (2y+y'')+2xy'-4x^2=0$$ subject to $y(-1)=2$ and $y(2)=7$, for $-1 \leq x \leq 2$, $\varepsilon \ll 1$. Find the location and width of the boundary ...
0
votes
1answer
18 views

Relation involving little-o.

I am trying to show that the following relation holds: \begin{equation} \log(1+ax) = log(x) + o(log(x)) \end{equation} as $x\rightarrow \infty$, where $a$ a positive number. I tried using Taylor ...
0
votes
1answer
26 views

Leading order of behavior of nth derivative of Gamma function evaluated at x=1 as n approaches infinity

I'm working from Bender and Orszag's "Advanced Mathematical Methods for Scientists and Engineers: Asymptotic Methods and Perturbation Theory" and I am trying to solve problem 6.48(b): Find the ...