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

learn more… | top users | synonyms (1)

2
votes
2answers
60 views

Can you give a closed form or an asymptotic for $\sum_{m=0}^{k-1}\cos(\frac{2\pi m n}{k \log 2})$ for $k\to\infty$?

I want compute, in a closed form or an asymptotic (with a, big oh as, error term) this mean $$\delta_k(n):=\sum_{m=0}^{k-1}\cos(\frac{2\pi m n}{k \log 2})$$ defined for each integer $k\geq 1$. ...
3
votes
2answers
65 views

What is the closed form approximation of the asymptotic growth rate of the superfactorial function?

The asymptotic growth rate of the hyperfactorial function (defined to be: $H(n)=\prod^n_{k=1}k^k$) is apparently (approximately) equal to: I'm curious as to how this result is obtained, and am ...
3
votes
0answers
25 views

A sequence converging to 0 in probability times a sequence bounded in probability

I'm trying to prove the following from Lehman's "Elements of Large Sample Theory" Lemma 2.3.1: If the sequence $\{Y_n, n=1,2,\ldots\}$ is bounded in probability and if $\{C_n\}$ is a sequence of ...
0
votes
0answers
25 views

Modified Bessel functions with negative argument

As recalled in a previous question, the modified Bessel functions of the first and second kind $I_{\nu}(x)$ and $K_{\nu}(x)$ can be obtained from $J_{\nu}(ix)$ and $N_{\nu}(ix)$: that are the Bessel ...
0
votes
0answers
58 views

How to get asymptotic form of the integrals with special functions?

I got difficulty when I try to plot I(x) for $m=1$ and $t=0.2$. The questions is how to get the asymptotic form of the following integral? $I(x,t)=\int_{0}^{\infty} \frac{f(y)}{2 \sqrt{\pi t}} ...
0
votes
1answer
37 views

Mathematical definitions of infill asymptotics

I am writing a paper that uses infill asymptotics and one of my reviewers has asked me to please provide a rigorous mathematical definition of what infill asymptotics is (i.e., with math symbols and ...
4
votes
1answer
41 views

A conditional asymptotic for $\sum_{\text{$p,p+2$ twin primes}}p^{\alpha}$, when $\alpha>-1$

When I've followed a notes that show how obtain a similar asymptotic using Abel summation formula, my case with $a_n=\chi(n)$, the characteristic function taking the value 1 if $p$ is prime (in a twin ...
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?
1
vote
1answer
61 views

Behaviour of modified Bessel function of the second kind $K_{\nu}(x)$

The modified Bessel function of the second kind $K_{\nu} (x)$ should have an exponential - decreasing - behaviour with respect to its variable $x$, as shown in this document (page 19, fig. 4.4). As ...
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)$ ...
2
votes
2answers
112 views

Asymptotic estimate of $\binom nk$

Prove: when $n\to \infty$, we have $$\sum_{k=1}^n\frac1{k^a}\binom nk\sim \frac{2^{n+a}}{n^a},$$ where $a$ is a constant. This problem is hard to me, I have no idea.
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
26 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$ , ...
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
46 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 ...
0
votes
2answers
36 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
48 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
54 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 ...
2
votes
1answer
48 views

Asymptote to sin x/x?

I have seen elsewhere that: $y=\sin x/ x$ has a horizontal asymptote of $y=0$, as it approaches that line as x tends to +/- infinity. Now, why does it not have an asymptote of $x=0$ or $y=1$, as ...
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]$.
4
votes
2answers
66 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 ...
0
votes
0answers
20 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 ...
0
votes
0answers
13 views

Definitions Continuity Using the Order (Landau) symbolism.

Is an $o(1)$ function always continuous?
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: ...
3
votes
1answer
26 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
17 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 ...
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
34 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
21 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
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
18 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 ...
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} ...
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 ...
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
61 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
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 ...
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
26 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$ ...
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
44 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$ ...