Questions tagged [asymptotics]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
11 views

Apply the method of hyperpolas to $\sum_{n \le {x}^{1/k}} n * Fraction \left(\frac{x}{{n}^{k}}\right)$

I am using the example from Theorem 1 of Friedrich Pillichshammer "Euler's Constant and Averages of Fractional Parts" (https://www.dmg.tuwien.ac.at/nfn/gamma.pdf) we have for integers $k >...
2
votes
0answers
43 views

The properties of $A^{1 /2} B^{1 / 2 } - B^{1 / 2} A^{1 / 2}$.

Suppose $A$ in $\mathbb{R}^{p \times p}$ is a strictly positive defined symmetric matrix. Now suppose there exists a weakly consistent estimator for the matrix $A$, say $B_n$, which satisfies $\| B_n -...
8
votes
2answers
92 views

What is the asymptotic expansion of $x_n$ where $x_{n+1} = x_n+1/x_n$?

Let $x_{n+1} = x_n+1/x_n, x_0 = a \gt 0$ and $y_n = x_n^2$. What is the asymptotic expansion of $x_n$ ($y_n$ will do)? I can show that $y_n =2n+\dfrac12 \ln(n) + O(1) $. Is there an explicit form for ...
1
vote
1answer
48 views

What is big O notation of the following functions?

So I have few simple functions I wrote and I would like to find out how to calculate their big O notation. This is my first function: ...
0
votes
1answer
23 views

How do I calculate Big Omega Notation for a function?

I was looking at the definition of Big Omega: \begin{align} \Omega(g(n)) &= \{ f(n): \text{ there exist positive constants }c \text{ and }n_0 \\ &\ \ \ \ \ \ \ \ \text{ such that }...
1
vote
1answer
37 views

How to neatly organize all real increasing functions?

Let $I$ be the set of increasing functions $\mathbb{R}\longrightarrow\mathbb{R}$ modulo asymptotic behavior, i.e. \begin{equation} f\sim g \qquad\Longleftrightarrow\qquad \lim_{x\rightarrow+\infty}\...
0
votes
1answer
25 views

Behaviour of the Gamma function near zero

The Gamma function on the positive real half-line is defined via the reknown formula $$ \Gamma(z)=\int_0^\infty x^{z-1}e^{-x}dx, \quad z>0. $$ A classical result is Stirling's formula, describing ...
2
votes
4answers
67 views

Asymptote for $y=\frac {x^2}{kx+1}$

We want to find the asymptote of $$y=\frac {x^2}{kx+1}$$ as $x\to \infty$. By synthetic division or binomial expansion, we arrive at $$y=\frac 1k \left(x-\frac 1k\right)$$ which is the correct answer. ...
0
votes
1answer
35 views

Evaluating $\lim_{n\to\infty} \left(\frac{n!}{n^n}\right)^{1/n}$ using Stirling's approximation

Although it is a very simple question, I am not able to get similar results using Stirling's approximation as obtained using Integration. Here is what I have attempted. $$L=\lim_{n\to\infty} \left(\...
0
votes
0answers
23 views

Inverse of Big O possible? [closed]

I have O(k), and I have information that p = O( $k^{-y}$ ).I need to find O(p) in terms of O(k) or k. Can we call an inverse big O function on p? Like $O^{-1}(p) = $k^{-y}$ I am confused about it ...
0
votes
1answer
16 views

What is the asymptotic growth of the terms in this expression?

Let's say we have $k$ variables in this expression: $(n_1+n_2+n_3+...+n_k)^2$. When you expand it, you get something like $n_1^2+n_1n_2+n_2^2+...$ , using the multinomial theorem. Now, if we multiply ...
0
votes
1answer
20 views

$f ( n ) = n ^ { 2 } + \sqrt { n }$. Whether $2 ^ { 2 ^ { f ( n ) } } = \Omega ( g )$

Let $f : \mathbb{N} \rightarrow \mathbb{R}$ be the function $f ( n ) = n ^ { 2 } + \sqrt { n }$. Determine whether the following statement is true or false, providing a proof for your answer. $2 ^ { 2 ...
0
votes
1answer
47 views

Time complexity of a piece of nested code?

I have a piece of code that tells us the order of the following code, which $O(log n)$. My question is, what is the fastest way to find that this piece of code is that time complexity?
1
vote
1answer
40 views

An asymptotic about Integral of Legendre Polynomials

I want to show asymptotics of the following integral involving Legendre Polynomial: For $0<t<\theta<\frac\pi2$, $$\Big|\int_0^\theta \frac{1}{\sqrt{\theta}+\sqrt{\theta-t}} \frac{1-P_n(\cos ...
1
vote
1answer
21 views

Bernoulli trial and asymptotic analysis

I want to find such function $p(n)$ in a way that obtaining one succes will be asymptotically-equivalent to obtaining two failures. I basically want to have something like this: $$ \lim_{n \to \infty}{...
1
vote
1answer
51 views

Expected earliest point at which a sock matches an earlier sock

The University of Waterloo CEMC's Problem of the Month for November, the problem statement for which can be seen here, was authored by me. (As far as I know, it is original, though I have come to ...
0
votes
0answers
8 views

Convergence of $\hat \beta_N - \hat \beta_{N-1}$ where $\hat \beta_N$ is the least squares solution of $Y_N = X_N\beta_N + \varepsilon_N$?

Suppose we are given a set of random observations $\{y_i,x_{i1},\dots,x_{ip}\}_{i=1}^N$. Based on these observations, we can form the multiple linear regression model in matrix form $$ Y_N = X_N\...
0
votes
1answer
21 views

Difference between $O(|V|+|E|)$ and $O(V+E)$

From CLRS: Given an adjacency-list representation of a multigraph $G = (V,E)$, describe an $O(V + E)$ time algorithm ... I am struggling to understand what $O(V+E)$ means. Is it supposed to be $O(|V|...
2
votes
1answer
41 views

Asymptotic approximation for $E[X_n]$ where $\{X_n\}$ converges in probability to a constant $\mu$?

I have a sequence of bounded random variables $\{X_n\}$, i.e. $|X_n| \le C$ for all $n$. Suppose this sequence convergences in probability to a constant $\mu$ with known rate of convergence, e.g. $$ ...
0
votes
1answer
37 views

Is Big-O closed under composition?

to show: if $f,g\in O(h)$ then $f(g)\in O(h)$ Proof: let $h= n^2$ then $f(g)=(n^2)^2= n^4$ now its easy to see that $n^4\notin O(n^2)$ which implies the proposition is false this completes the proof ...
2
votes
0answers
52 views
+50

Approximating a double sum by a double integral

Related to this question, I'm interested in bounding from above the following sum $$ S:=\sum_{x=0}^\infty \sum_{y=0}^\infty (x+y)^m e^{-\frac{x^2}{2i} - \frac{y^2}{2j}}, $$ which I hope to do by ...
0
votes
1answer
16 views

Interchanging Iterated Limits for a compactly convergent sequence of functions

Let $\mathcal{A}\left(\mathbb{D}\right)$ denote the space of all holomorphic functions $f:\mathbb{D}\rightarrow\mathbb{C}$, where $\mathbb{D}$ is the open unit disk in $\mathbb{C}$, let $\omega$ be a ...
1
vote
2answers
31 views

Order of complexity proofs. Show that $n^3-5n+1=O(n^3)$.

Show that $n^3-5n+1=O(n^3)$. I did the following: Using the definition of big-Oh, we need to show that there exist $n_0$ and $C$ such that $n^3-5n+1 \leq Cn^3$ is valid for some constant $C > 0$ ...
1
vote
0answers
14 views

asymptotic normality of z-estimator

I'm working on Problem 5.4.1 in Bickel and Docksum's Mathematical Statistics Let $X_1, \dots, X_n$ be i.i.d. random variables distributed according to $P\in\mathcal{P}$. Suppose $\psi:\mathbb{R}\to\...
0
votes
3answers
66 views

How can I prove $(n^2)!$ greater growth than $(n!)^n$ [duplicate]

I tried take limit n goes to infinity. Wolfram solved the limit and $(n^2)!$ has greater growth rate but there is not step by step solution. I think I can simplify $(n!)^n$ to $(n^n)^n$ But how can I ...
0
votes
1answer
35 views

Solve the following recurrence-relations

Solve the following recurrence-relations: my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$ but i didn't get the same ...
0
votes
0answers
22 views

$\lim_{n \to \infty}\frac{\log{(\prod_{a_i\leq n} a_i)}}{(\text{number of }a_i\leq n)\log{n}}$ for $\{a_n\}$ a subsequence of natural numbers

This is a generalization of Limit of $\frac{\log(n!)}{n\log(n)}$ as $n\to\infty$. . Precisely, let $\{a_n\}$ be a subsequence of $1, 2, 3, ...$. Let $A(n):=\sum_{a_i\leq n}1$ counts the number of $...
1
vote
1answer
85 views

Cannot see why this formula is wrong

In the book of "Introduction to Algorithm 3rd Edition", p.86, there is subtitled, "Avoiding pitfalls", and it states When $T(n) = 2 \cdot T(\lfloor(n/2)\rfloor)+n$ , and if we ...
0
votes
0answers
33 views

Does either/both of the properties $E[M]=mp$ and $M\stackrel{a.s.}{\to}mp$ imply that $E\left[\frac{1}{M}\right]=\frac{1}{mp}$?

Let $X_1,\dots,X_m$ be a set of $m$ i.i.d observations. Define $$ M = \sum_{i=1}^m 1_{X_i \in [a,b]}. $$ where $1_{X_i \in [a,b]}$ is the indicator function for the observation $X_i$ falling in the ...
2
votes
0answers
73 views
+50

Existence of an asymptote for $g(x)=\frac{f(x)f'(x)+f(1)f'(1)}{f'(x)+f'(1)}-f\left(\frac{xf'(x)+f'(1)}{f'(x)+f'(1)}\right)$

Working with the Slater's inequality (compagnion of Jensen's inequality) I find this statement : Let $f(x)$ be a continuous,$n$ times differentiable ,convex and non constant on $(0,\infty)$ and ...
1
vote
0answers
19 views

Subtraction in the asymptotic limit

Let $0 < c < 1$ be a constant. Is it true that for any such constant $c$, for a large enough $n$ \begin{equation} c - \mathcal{O}\left(\frac{n}{2^{n}}\right) \geq c' \end{equation} where $c'$ is ...
3
votes
2answers
113 views

is there any difference between these three logarithms?

is there any difference between $\log(n)^{\log(n)}$ vs $(\log n)^{\log n}$ vs $\log n^{\log n} $ from asymptotic growth rate? maybe all the same. I doubt about notation. maybe this is very basic or ...
2
votes
1answer
62 views

Asymptotic limit in a system of ODEs

I have the following system of differential equations: \begin{align} \begin{cases} \frac{d}{dt}a_t=-a_tb_t\\ \frac{d}{dt}b_t=b_t(a_t-c_t)\\ \frac{d}{dt}c_t=c_t(b_t-1)\\ \frac{d}{dt}d_t=c_t \end{cases} ...
1
vote
1answer
31 views

Is $f(n)$ asymptotic to $g(n)$?

$\pi(n)$ is the prime counting function and $li(n)$ is the logarithmic integral. $$f(n)=e^{-\frac{1}{\pi\big(\frac{1}{n}\big)}}$$ and $$ g(n)=e^{-\frac{1}{li\big(\frac{1}{n}\big)}}$$ Is $f(n)\sim g(n)...
0
votes
1answer
42 views

Is $\sqrt{n}(\bar X_n - \bar X_m)$ tight?

My question is a bit more specific than the title. Suppose $\{X_i\}$ is iid with finite second moments, and suppose we select some random subset $D_n \subset \{1, \dots, n\}$ such that $n_d = |D_n|$, ...
2
votes
1answer
78 views

Show that $\sin\left(\frac{1}{n}\right)=\frac{1}{n}-\frac{1}{3!~n^3}+O\left(\frac{1}{n^5}\right)$

Show that $\sin\left(\frac{1}{n}\right)=\frac{1}{n}-\frac{1}{3!~n^3}+O\left(\frac{1}{n^5}\right)$. In fact, this result is pretty obvious but when I did this in homework I basically got no points ...
0
votes
1answer
34 views

Manipulating a series with big-O-notation

Let's assume we are given a series $\sum\limits_{k=1}^{\infty}a_k$ which we want to check for convergence. Two scenarios: 1.) After some manipulations of $a_k$ we get something like: $a_k= \frac{1}{k}+...
0
votes
0answers
13 views

summation and big Theta

We are given by $\sum_{i=1}^{b_n}a_i(n)=a_1(n)+\cdots+a_{b_n}(n)=n-1$, where $(b_n)$ is a nondecreasing sequence, and for $i=1,\dots,b_n$, $a_i(n)$ is also a nondecreasing sequence. Let $x_n=\mathrm{...
0
votes
0answers
16 views

Joint Asymptotic Distribution

I'm self-studying large sample theory and I ran into a problem. Can someone help? The image of the problem is here. Exercise 6.4 Let $X_1,\dots,X_n$ be independent $U(0,1)$ random variables. Find the ...
-2
votes
0answers
80 views
+100

Find conditions on two parameters $c,d>0$ such that the asymptotics of an integral diverges

Let us start from defining: $$\underset{c,d}{g(x)}=\displaystyle{\int_{\frac{1}{2}}^{x}}z^{c-1}(1-z)^{d-1}dz\tag{1}$$ and: $$m(y)=\frac{2}{l^2}\displaystyle{\int_{\frac{1}{2}}^{y}}\frac{\underset{c,d}{...
0
votes
1answer
39 views

Show that $(\log n)^{\log n}\in\Omega (n)$

Show that $(\log n)^{\log n}\in\Omega (n)$ Proceeding with a common logarithm property, we get $$(\log n)^{\log n}=(n^{\log\log n})$$ How do I deduce that $$(n^{\log\log n})\in\Omega(n)$$ If I say ...
1
vote
1answer
14 views

Distribution of Y, which is Poisson with mean 1 minus 1. How do we derive the Expectation and Variance?

My question is about the following statement: Consider a random walk whose step size has distribution Y, which is Poisson with mean 1 minus 1. Asymptotically the critical items are that Y has zero ...
1
vote
1answer
47 views

Understanding equality sign in context of big-O-notation

I am not quite sure if I have understood correctly the equality sign when using big-O-notation. Let's consider the following example of a sequence: $\left(a_n\right)_{n\in\mathbb{N}}:= 5+f(n)$, where $...
1
vote
1answer
33 views

How to prove $\ln(n) = o\left(e^{\ln(n)^{1/3}}\right)$

I want to prove, that $\ln(n) = o\left(e^{\ln(n)^{1/3}}\right)$ ((Landau-Notation)) Normally I would do this by showing that $$\lim _{n \rightarrow \infty} \frac{\ln (n)}{e^{\sqrt[3]{\ln (n)}}}=0$$ ...
2
votes
2answers
42 views

How close is the sample mean $\mu_N$ for $N$ random variables to the sample mean $\mu_{N-1}$ for $N-1$ random variables?

Define $\mu_{N}$ to be the sample mean for $N$ i.i.d. random variables that each have mean $\mu$ and variance $\sigma^2$: $$ \mu_{N} := \frac{1}{N} \sum_{i=1}^N X_i. $$ Now consider the sample mean if ...
0
votes
0answers
27 views

Very Hard : Error Bound on asymptotical approximation [duplicate]

Very Hard: Suppose I have a polynomial $g(x)=x^p $+ lower order terms. Asymptotically the inverse is $g^{-1}(x) \sim x^{1/p}$ for large $|x|.$ What is a bound of the error of this asymptotical ...
-1
votes
1answer
36 views

Are these two asymptotic notations equal?

I see two notations and try to understand these are the same or not? (from two views) $O( n * (log m) * (log n))$ is equal to $O( n * (log m + log n))$ from logarithm property and from asymptotic ...
1
vote
2answers
56 views

Asymptotic formula for Mean of Sum of Power of Divisors $\frac{ \sum_{i=1}^{n}\sigma_v(i)}{n}\sim\frac{n^v\zeta(v+1)}{v+1}$

Question: Define the sum of $v$-powers of divisor $\sigma_v(n)=\sum_{d|n}d^v$ for $v \in \mathbb{R}$. Prove that for all $v>0$, $$\frac{ \sum_{i=1}^{n}\sigma_v(i)}{n}\sim\frac{n^v\zeta(v+1)}{v+1}$$ ...
0
votes
1answer
33 views

Bounding an Error on the inverse.

Suppose $f(x) = x^p + $ lower order terms. Then Asymptotically $f^{-1}(x) \sim x^{\frac{1}{p}} $ for large $|x|$. How can we bound the error in this asymptotic approximation in terms of $|x|$
0
votes
0answers
9 views

Inverse functions and asymptotic equivalence 2

Let $f$ and $h_1$ be monotone functions. Let $g$ be the inverse function of $f$ and $h_2$ the inverse function of $h_1$. Furthermore we know that $f\sim h_1$. If the last statement holds - under what ...

1
2 3 4 5
149