Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [upper-lower-bounds]

For questions about finding upper or lower bounds for functions (discrete or continuous).

1
vote
0answers
20 views

L2 metric entropy with bracketing

I am going through the proof of Theorem 3.1 in chen and white 1999. The authors use the upper bound of the $L_2$ metric entropy with bracketing $\mathcal{H}_{[]}(w, \Theta_n) = 2^kr_nB_n(1+d)\log(2^...
1
vote
1answer
79 views

Let $n_1,\ldots,n_k$ be positive integers summing to $N$. What's an upper bound for $\sum_{i=1}^k1/\sqrt{n_i}$?

Disclaimer. Sorry, I haven't looked into this one in any detail (as I should have). I was just thinking there out-of-be an elementary principle out here (pigeon-hole, Cauchy-Schwarz, Jensen, etc.). ...
-1
votes
0answers
26 views

Relation between Maximum Likelihood Estimator (MLE) and Cramér-Rao Lower Bound [on hold]

Suppose that $X_1,X_2, ...$ are i.i.d Bernoulli random variables with unknown success probability $\theta∈[0,1]$. Show that the MLE of $\theta$ attains the Cramér-Rao lower bound and is therefore the ...
0
votes
1answer
28 views

What is a good estimate for $\sum_{t=0}^T \frac{1}{\gamma^t}\frac{1}{\sqrt{t + 1}}$, where $0 < \gamma < 1$?

Let $0 < \gamma < 1$ and $T$ be a "large" nonnegative integer. Question What is a good estimate (upper bound) for $\sum_{t=0}^T\dfrac{1}{\gamma^t}\dfrac{1}{\sqrt{t + 1}}$? In general, for $\...
1
vote
0answers
23 views

Can a bound be given to $\sum_{a=1}^{p-1}\chi(a)\left(\frac{a^2-1}{p}\right)$, which is smaller than $p$, where $\chi$ is a dirichlet character?

Here $(\cdot)$ denotes the legendre symbol and $p$ be an odd prime number. All terms are of norm 1. So one bound is $p$. can one better bound be given to the sum?
0
votes
0answers
20 views

Analyzing the error of the Lagrange Interpolation of $x^2-\sin(10x)$

Given the function $f(x)=x^2-\sin(10x)$, find degree, $N$, of the lagrange interpolation satisfying that the error $\vert f(x)-p(x)\vert < \epsilon = 10^{10}$ in the interval $I= [0,3]$. Here is my ...
0
votes
1answer
28 views

Bound $|x^TAy|$ in terms of $\|A\|$ and $|x^Ty|$

Under what conditions on a square matrix $A$ of size $n$ do we have $|x^TAy| \le |x^Ty|$ for all $x,y \in \mathbb R^n$ ? Notes The above inequalities hold for $A \in \{0, I\}$, and so by simple ...
0
votes
2answers
16 views

Double Integral Bounds / Substitution

I am having trouble following these steps in a reading on multivariable calculus. Due to a change of variables: $ \displaystyle\int_0^1 \int_0^s v^7 dv \, ds = \...
0
votes
0answers
19 views

Multivariable Calculus - Change of Bound Help!

I am having trouble following these steps in a reading on multivariable calculus. Due to a change of variables: $ \displaystyle\int_t^T \int_t^s \theta_v dv \, ...
0
votes
1answer
35 views

Inequality involving log-sum-exp, variance, and mean

Fix $z_1,\ldots,z_n \in \mathbb R$. Let $\mu_n:= mean(z_1,\ldots,z_n):=\frac{1}{n}\sum_{i=1}^n z_i$, $lse_n(z_1,\ldots,z_n)=\log(\sum_{i=1}^n e^{z_i})$, and $\sigma^2_n := variance(z_1,\ldots,z_n):=\...
1
vote
1answer
28 views

Lower bound given expectation and standard deviation.

A random variable X with integer values only has mean 3 and standard deviation 2. Under those assumptions, which is the best lower bound for $P[0\leq X \leq 6]?$. By my calculations, it is $\frac{5}{...
0
votes
0answers
14 views

Upper bound of a set [closed]

Consider the set $S= \{s\in\mathbb{R}, s>0, s^n<a\}$. Here $n$ is a natural number $>1$ and $a$ is a positive real number. My question is, can I say that 1 is not an upper bound of the ...
1
vote
1answer
20 views

Gaussian complexity bound

I am reading Foundations of Machine Learning (1st edition). It seems that most generalization bounds in the literature are based on Rademacher complexity, rather than Gaussian complexity. So, I was ...
1
vote
2answers
28 views

Least upper bound for the maximum of two random variables

Two independent random variables are not negative and E[X]=a, E[Y]=b. We define a new random variable Z=max{X,Y}. If t>0 and t>max{a,b} calculate the best (least) upper bound for the probability P[Z>t]...
1
vote
1answer
27 views

Upper bound of a function 2

Consider function $f:\mathbb{R}_{\geq 0} \times [0,1] \rightarrow \mathbb{R}$ defined with: $$ f(z,\alpha) = (1+\alpha) \left [ z- \frac{z^{\alpha}}{2} - z^{\alpha+1} \right].$$ Prove that $f(z,\alpha)...
2
votes
1answer
31 views

The expected weight-ratio between weighted and un-weighted balls when picked from a bin without replacement

The Problem The problem, I believe, can be stated in the following way: Given $K$ white balls all with without weight (one can say that the weight is $0$) and $N - K$ red balls with individual ...
1
vote
1answer
38 views

Show a sequence converges to a real number less than $\log(2)$

So I'm working on trying to show that $$\sum_{k=2}^{n-1}\frac{1}{\log(k)}-\int_{2}^n\frac{1}{\log(x)}$$ converges to a real number less than $\log(2).$ It's not hard to show the sequence is monotone ...
3
votes
1answer
60 views

The upper bound of $\lim \limits_{n\to\infty} \sum \limits_{i=1}^n e^{-i}\sqrt{i}$?

The target is to find the upper bound of the summation. I can only get that: since $\sqrt{i}<i$, $$S < \sum \limits_{i=1}^n e^{-i}i = \frac{1-e^{-n}}{e(1-e^{-1})^2} - \frac{n}{e^{(n+1)}(1-e^{-1}...
1
vote
1answer
19 views

Pointwise bound of the gradient of solutions of heat equations in the half-space.

I want to investigate the decay of $L(x)$: $$L(x) := \int_{\mathbb{R}^3_+} \nabla_x \Phi(x-y,1/2)(\eta(y)g(y))dy,$$ where $g:\mathbb{R}^3_+ \rightarrow \mathbb{R}^3$ is infinitely smooth away from ...
-1
votes
1answer
14 views

Bound on an indefinite integral in kernel density estimation

I am having trouble on what is probably a simple step in the proof of Theorem 24.1 in Asymptotic Statistics by Van der Vaart. Let $\int K(y) dy = 1$. The author writes: $$h^4 \int K(y)y^2 dy \int \...
1
vote
1answer
23 views

Bound of an Integrable function (Analysis)

For non-negative Riemann integrable function f in [a,b], and dissection $\mathcal D= {x_0,x_1,...,x_n } $, if $p(f,\mathcal D) $ is defined as $$p(f,\mathcal D)=\prod_{k=1}^n [1+(x_k-x_{k-1}) \inf_{x\...
1
vote
3answers
48 views

Upper bound estimate $ab^3\leq c(a^2+b^2)^2$. Find optimal, or good, constants $c$

I am trying to find a good upper bound estimate for the expression $ab^3$, where $a,b\in\mathbb R$, and it should be of the form $ab^3\leq c (a^2+b^2)^2, c\in\mathbb R.$ (The reason for the latter is,...
0
votes
0answers
16 views

upper bound to sum of exponentials

Let $k\geq 1$ and $$ \beta_j=\frac{20^{j-1}}{(\log\log T)^2} $$ for $1\leq j\leq \mathfrak{I}-1 $ where $$ \mathfrak{I}=1+\max\{j\mid \beta_j\leq e^{-1000k}\} $$ So $\beta_{\mathfrak{I}}$ is the ...
0
votes
0answers
23 views

Using Markov's Inequality to Derive a Conclusion about random variable

I'm wondering whether I can use Markov's inequality to reach the following statement: Given Markov's inequality on a non-negative random variable X: $ P[X\geq a] \leq \frac{E[X]}{a}$ We can do the ...
2
votes
1answer
36 views

Bound for the cardinality of a minimal generating set of a finite group [duplicate]

Given a finite group $G$ of order $n\geq 2$, it obviously has a minimal generating set (a generating set of minimal cardinality) let's say of cardinalty $m$. I am looking to find out if a bound for $m$...
0
votes
0answers
21 views

Upper bound on difference of function value

I have the function of form $f(X) = -2A^TXZ + 4XZX^TXZ$ where $Z,A,X,Y \in R^{n \times n}$. I wanted to get an upper bound on $\|f(X_1)-f(X_2) \|^2_F$ such that $\|f(X_1)-f(X_2) \|^2_F \leq L \|X_1 - ...
1
vote
1answer
29 views

$\frac{d^2y}{dx^2}=f(x)$ with boundary conditions, how to find integration bounds

Given $$\frac{d^2y}{dx^2}=f(x),\quad y(-1)=y(1)=0,$$ I used $u=y'$ and $u(x_0)=u_0$ to get $$ u(x)=u_0+\int_{x_0}^xf(\xi)d\xi. $$ Then we have $y'=u$, which we can integrate again using $y(x_0)=y_0$ ...
0
votes
0answers
22 views

Step size in gradient descent

I am trying to minimize the function $f(X) = \|A - XYY^TX^T\|_F^2$ where the gradient of $f$ follows the bound given belew where $A,X,Y \in R^{n \times n}$ $$\|\nabla f(X_1) - \nabla f(X_2)\|\leq L\|...
0
votes
1answer
66 views

Show the inequality $\lvert \sin(z)\rvert > \frac{2}{\pi}$ for $z$ on the circle of radius $(n+1/2) \pi$.

I want to show the inequality $\lvert\sin(z)\rvert > \frac{2}{\pi}$ for $z$ on the circle of radius $(n+1/2) \pi$. What I have gotten so far is using the fact that $\lvert\sin(x+iy)\rvert^2 = \...
0
votes
0answers
14 views

Finding lower bound for standard deviation

I have a random variable $R_n$ and a constant $w_n$ (which are related to a oriented percolation problem from https://arxiv.org/abs/1610.10018 on section 4.1(ii)) with the following properties: (...
2
votes
0answers
106 views

How to proceed in proving this recurrence-relation upper bound?

Assume I have $n \in \mathbb{N}$ and $p_0, ..., p_{n-1}$ such that $0 \le p_k \le 1$ for all $k = 0,...,n-1$. Now consider the following recurrence relation: $\begin{align}P_{0,0}&=1\\P_{a,0}&...
0
votes
2answers
17 views

Markov's inequality over sum of two functions of a RV

I'm wondering whether Markov's inequality can be applied over the following example, as I need an upper bound for the probability determined by: $ P( f_1(X) + f_2(X) \geq \alpha ) $ Above, X is a ...
0
votes
1answer
45 views

Bound on hessian when Lipschitz gradient is bounded

I know that if we have a Lipschitz gradient $$\|\nabla f(x) - \nabla f(y)\|\leq L\|x-y\|,\, \forall x,y, $$ we can say that $\nabla^2f\preceq LI.$ I have a problem where difference of gradient is ...
0
votes
0answers
28 views

lower bound for determinant of $(X^TY)$

Am looking for a lower bound for determinant, $\det(X^TY)$ where $X^T$ is $p \times n$ and $Y$ is $n \times p$. Is it $Tr(X^TY)^{-1}$? Regardless, what are other lower bounds for this? $X,Y$ are real-...
0
votes
0answers
33 views

Upper bound for independent Normal random variables

I want to fined a condition for variance of independent normal random variables to show that Entropy Integral is finite. I guess i have to show, if \sigma_n decreases to 0 then is the Entropy Integral ...
2
votes
1answer
48 views

Upper and Lower bounds Exam style question

Ewan uses a piece of wood 0.8m long, correct to 0.02m, to make a shelf. He then marks out the shelf every 10cm. He finds he has space at the end. What is the maximum length the space could be. So I ...
0
votes
0answers
27 views

Finding the least upper bound for a sequence

Define $f(1) = 10$ and $f(n) = f(\lfloor n/2\rfloor) + f(\lfloor n/3\rfloor) + 17n$. Find the smallest value $k$ so that $f(n) \leq kn$ for all $n$. I plugged in $f(1)$ into the function, which ...
0
votes
0answers
8 views

Derive a lower bound of weighted sum

I have the following expression $$w_1 a_1 + w_2 a_2 + \cdots + w_n a_n,$$ where $a_i$ are non-negative constants in the range $[L,U]$ and $w_i\in [0,1]$ are the weights satisfying $$w_1 + w_2 + \...
0
votes
1answer
28 views

Markov Inequality example confusion

Basic q I'm sure. Markov's inequality states that the upper bound to the probability that the realization of a random variable exceeds a given threshold is defined thus: $P(|X| \ge c) \le \frac{E[X]}{...
0
votes
1answer
46 views

Numerical Approximation Solution to Exponential Equation

I have a question about finding an approximate value $x$ for the following expression: $$\frac{(e^{x\alpha_{1}})^2 + (e^{x\alpha_{2}})^2 + \ldots + (e^{x\alpha_{n}})^2}{\displaystyle \left(\sum_{i = ...
1
vote
0answers
44 views

Approximating $\max \big\{\frac{x_\tau}{x}\big\}$ as $x$ and $x_\tau \rightarrow 0^+$

I have the following delay system: $$x'(t) = g(t,\tau,x,x_\tau)$$ Given that $g(\cdot)$ is smooth and bounded, $x(t)$ is bounded in a non-negative region. What are some possible ways to obtain an ...
0
votes
2answers
20 views

Show $\frac{ (n+k)!}{n! \sqrt{n+k}} \le ( f(n) )^k \sqrt{k!}$ for some function $f$

Let $k$ and $n$ be positive integers. Can we show the following inequality: \begin{align} \frac{ (n+k)!}{n! \sqrt{n+k}} \le ( f(n) )^k \sqrt{k!}, \end{align} where $f(n)$ is some funciton of $n$...
-1
votes
2answers
26 views

How to prove that infimum of this set is $0$

How do I prove that the infimum of the set $A=\{x+\frac{1}{n}:x\in(0,1),n\in\mathbb{Z^+}\}$ is $0$? Clearly $0$ is a lower bound of A since $1/n$ is greater than $0$ for all $n$. How do I show that ...
0
votes
1answer
21 views

Markov Inequality Upper Bound

Suppose X is a random variable such that $E[2^X] = 4$. Give an upper bound for P(X ≥ 3). I know I must use Markov's inequality here: P(X ≥ a) = $\frac{E|X|}{a}$ For other problems I have solved I ...
0
votes
2answers
28 views

Upper bound on alternating harmonic series

Let $a > 0$. Is the following statement true: \begin{align} \ln(2) = \sum_{n=1}^\infty{\frac{(-1)^{n+1}}{n}} > \sum_{n=1}^\infty{\frac{(-1)^{n+1}}{n+a}} \end{align} From my intuition the ...
0
votes
0answers
22 views

Find the least upper bound of a binomial distribution

In this problem we are given a random variable $X$ of binomial with $n=119 ,p=0.5$. I have calculated $\mathbf{E}[X]=59.5$ and $\mathbf{Var}[X]=29.75$. Looking for $D$ in order to have $\Pr[|X-\mathbf{...
0
votes
2answers
24 views

Inequality with bounded functions

Consider $$8-\frac{8B}{A}+\frac{2B(B-1)}{(A+1)(A-1)}$$ I would like to check if this expression is positive or not. I know that $a \leq A \leq b$, for some positive integers $a,b$. Moreover, I ...
0
votes
1answer
26 views

Bounding sum (log factor)

I want to prove that $$ \sum_{\substack{1\leq n\leq T \\ n\neq m}}n^{-\frac{1}{2}}\left|\log \frac{m}{n}\right|^{-1}\ll T^{\frac{1}{2}}\log T $$ for any $1\leq m \leq T$. Do you have any hint how I ...
1
vote
0answers
23 views

A problem about the monotonicity of a series [duplicate]

I followed this problem Prove that $\ x_{n}=\int_{n}^{2n} \frac{x+a}{x^{3}+2a}dx$ is decreasing and sincerely, the answer is overwhelming for me too, as it seems for the guy who posed the question. ...
0
votes
0answers
16 views

To find real solution or upper bound for polynomial

I have a equation $X + a X^n -1 = 0 \quad \quad (1)$. where $a>1$; $X$ is a probability $P_{(n)}$ indexed by $n$; $X \in (0,1)$; $\lim_{n \to \infty} X = 1$ and $\lim_{n \to \infty} X^n = 0$. ...