Stack Exchange Network

Stack Exchange network consists of 174 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 [lower-bounds]

The tag has no usage guidance.

0
votes
0answers
13 views

Non-asymptotic tail-bounds for Hotelling $T^2$ statistic

Let $X_1,\ldots,X_n$ be an i.i.d sample from a distribution on $\mathbb R^p$ with mean $\mu = 0 \in \mathbb R^p$ and $p$-by-$p$ covariance matrix $\Sigma$ of rank $r \le p$. Consider the centered ...
2
votes
1answer
183 views

Complicated bound after using Stirling's approximation

I have this inequality $$\frac{1}{a}\exp\bigl\{-\frac{4}{h^2}\bigr\} \geq \frac{1}{f}$$ where $$ a \leq \Bigl(\pi^{d/2}\Gamma(\frac{1}{2}d+1)^{-1} + 1\Bigr) \left(\frac{h^{d+1}}{2} \Gamma \left(\frac{...
3
votes
1answer
78 views

Non-asymptotic tail bounds for $D_{\text{Hellinger}}(P\|\hat{P}_N)$

Let P be a distribution on a finite set of size $k$ and let $\hat{P}_N=(N_1/N,\ldots,N_k/N)$ be the empirical distribution (frequencies) from a samples of size $N$. Consider the Hellinger distance ...
2
votes
0answers
271 views

Counting / characterizing the isolated points of a particular algebraic variety

I'm not a professional geometer / topologist, so please thanks for your patience :) Setup The following questions are the first in a series of steps I'm undertaking in an attempt to break down a ...
1
vote
1answer
95 views

Any inequalities / estimates for a lower bound of the $L^2$ inner product of a quantity and its derivative?

For some numerical analysis of a fluid, I am wondering if there is any inequality that provides a lower bound (in the $L^2$ norm), for the $L^2$ inner product of a quantity with its derivative. In ...
1
vote
1answer
132 views

Hausdorff distance is a lower (or upper bound) for what probability metric?

In a metric space $X=(X, d)$, given a probability measure $\mu$ and two subsets $A$ and $B$ of positive measure, it's not hard to prove that $$ d(A, B) \le W(\mu|_A, \mu|_B), $$ where $d(A, B):= \...
3
votes
1answer
55 views

Lower bound on the sum of pmf squared of a hypergeometric distribution

I am working on a proof of correctness for an algorithm I came up with. I encountered the following problem en route. I would appreciate if anyone had some idea or could point me to the relevant ...
1
vote
1answer
80 views

A distribution which is Wasserstein-close to a compactly supported distribution is almost compactly supported

I wonder whether this is true: If a distribution is very close (in the Wassertein sense) to another distribution with compact support, then the former must put only tiny amount of mass outside a ...
1
vote
2answers
151 views

Lower bound on misclassification rate of Lipschitz functions in terms of Lipschitz constant

Important note @MateuszKwaśnicki in the comment section has raised a fundamental issue with the current statement of the problem. I'm trying to bugfix it. Setup I wish to show that a Lipschitz ...
2
votes
1answer
71 views

Large deviation upper bound for Chi-squared random variable

Let $X \sim \chi^2_n$ random variable. I am looking for a large deviation upper bound for $X$. The answer here, says that Since you said that you're looking for an upper bound, it should also be ...
4
votes
2answers
138 views

Lower bound on the entries of the Perron vector

Let $A$ be a matrix that satisfies all the conditions of Perron- Frobenius theorem. From the theorem it is known that the entries of the eigenvector corresponding to the largest eigenvalue will be ...
1
vote
0answers
45 views

Bounding quantiles of the noncentral chi distribution

I need to bound the empirical quantiles for a noncentral chi distribution (not chi-squared) $\chi_\nu(\lambda)$, where $\nu$ is the number of degrees of freedom and $\lambda$ the non-centrality ...
0
votes
0answers
60 views

Are these decent bounds for a function?

I am trying to bound a function $f(\mathbf{x},\mathbf{y})$ defined for $0\leq x_i \leq 1$ and $y_i\geq 0$, with $\mathbf{x},\mathbf{y}\in\mathbb{R}^n$. At present, I can prove that for all subsets $S\...
0
votes
0answers
90 views

Lower bound for the probability that $X=\omega\left(\mathbb E[X]\right)$ for $X\sim Bin(n,p)$

Let $X\sim Bin(n,p)$ be a binomial variable and let $\delta\in (0,1)$. I'm looking for a lower bound of the form $\Pr[X > f(\delta)] \ge \delta$. Specifically, if $\delta,p=o(1)$ are not ...
3
votes
2answers
323 views

Nontrivial lower bound on the sum of matrix norms

Let $X, V\in\mathbb{R}^{n\times r}$ such that $X^\top V$ is symmetric. The central quantity I care about is \begin{equation} \|XV^\top\|_{F}^2+\|X^\top V\|_{F}^2 +[\text{Tr}(X^\top V)]^2. \end{...
2
votes
2answers
70 views

Discrepancy bounds for moderate points counts in dimensions from d=2 to 32?

In one dimension d=1 an equally-spaced set of N points in [0,1) has the lowest possible (star) discrepancy D=0.5/N. Unfortunately, I found only asymptotic bounds for other dimensions (e.g. acc. to ...
5
votes
0answers
79 views

Smaller root of a difference of products of polynomials with integer bounded coefficients

Is there a positive constant $K>0$ such that for every polynomials $f_1,\dots,f_4 \in\mathbb{Z}[X]$ with coefficients in {-1,0,1}, every positive root $x$ of the polynomial $$g=f_1f_2-f_3f_4$$ ...
3
votes
0answers
137 views

Lower bound on number of $r$-regular graphs witn $n$ vertices

Consider the set of $r$-regular labeled graphs with $n$ vertices. There are results on its asymptotic size (see for instance this question on MO). Is there a known, explicit lower bound on that size, ...
1
vote
0answers
52 views

Cramer Rao bound for relative estimation

I have an observed vector ${\bf y}$ from which I would like to estimate a parameter vector ${\bf c}$ (denote the estimate $\hat{{\bf c}}$). A feature of our estimation problem is that the involved ...
4
votes
1answer
142 views

Expectation over Pareto Sums

Given $K$ iid random variables $x_i$ with uniform distribution on $(0,1]$ and a constant $\alpha > 0$, the random variable $x_i^{-\alpha/2}$ is Pareto-distributed with scale parameter $1$ and ...
1
vote
0answers
131 views

Bound on eigenvalues of A+B (Hermitan matrices) which is better that the Lidskii and Weyl bounds

I have two positive definite $N\times N$ Hermitian matrices $A$ and $A$ and am interested in bounding the eigenvalues of $A+B$ in terms of the eigenvalues of $A$ and $B$. Let $\lambda_k(\cdot)$ be ...
0
votes
2answers
389 views

Bounds on the smallest real positive root of a polynomial

I'm trying to find upper and lower bounds of the smallest positive root of a polynomial, stated in terms of its coefficients. As I appreciate it might be a very general problem, My specific interest ...
2
votes
1answer
131 views

When does the equality hold in Dias da Silva - Hamidoune Theorem?

Let $p$ be prime number and let $A$ be a $k$-elements subset of $\mathbb{Z}/p\mathbb{Z}$. Dias da Silva - Hamidoune Theorem states that $|h^{\hat{}}A| \geq \min(p, hk -h^2 + 1)$, where $h$ is an ...
1
vote
0answers
97 views

Finding the infimum of the range of a certain non-negative function associated to a $ C^{*} $-algebra

Let $ A $ be a non-trivial $ C^{*} $-algebra and $ n \in \mathbb{N} $. Setting $ \mathcal{D} \stackrel{\text{df}}{=} A^{n} \setminus \{ (0_{A},\ldots,0_{A}) \} $, we can define a function $ f: \...
4
votes
2answers
294 views

Lower Bounds for the Roots of Polynomials

I'm interested in the "size" of the roots of a sequence of Taylor Polynomials of an entire function. For example, consider $\mathrm f(z) = \mathrm e^z$. The Taylor Polynomials, or $k$-jets, are $$\...
6
votes
1answer
199 views

lower bound for Perron-Frobenius degree of a Perron number

A Perron number is an algebraic number which is greater than one in absolute value and is greater than all of its Galois conjugates in absolute value as well. Lind's theorem states that any Perron ...
1
vote
0answers
48 views

Bounds on $\sum_{j=1}^m\frac{\pi^j}{\Gamma(j)(x^2+(j+1/4)^2)}$

During our search of real rooted entire function approximations to Riemann $\Xi$ function, we need to calculate the upper and lower bounds of $$f_m(x):=\sum_{j=1}^m b_j(x):=\sum_{j=1}^m\frac{\pi^j}{\...
2
votes
0answers
62 views

Minimal condition $\sum \rho_{ij} \Psi_{ij} s_i s_j < \sum s_i s_j $, $\mid \rho_{ij} \mid \leq 1$, $s_i \in \mathbb R$ and $\Psi_{ij} \in \{0,1\}$

Consider a sequence of real number $\{s_i\}_{i\leq n}$. Now consider the real numbers $F$, $G$ and $\alpha$ defined below $$F= \sqrt{ \left( \sum ~\rho_{ij} ~\Psi_{ij}~ s_i ~s_j \right)^+}, $$ $$G = ...
3
votes
2answers
175 views

Lower bound for Euler's function

Euler function is defined, for $|x|\le 1$, as follows: $$\phi(x)=\prod_{i=1}^\infty(1-x^i)$$ Upper bounds for $\phi$ can be simply derived from ending the product early, e.g. $$\phi(x)<\prod_{i=1}^...
3
votes
0answers
186 views

A generalization of coupon collector problem - $\geq1$ pick per experiment

Mix $T\geq1$ coupons numbered $1$ to $T$ with a set of $S\geq0$ number of dummy coupons with no numbers. Select $N\geq1$ coupons at each trial at random and put them back. $N=1$ is standard coupon ...
3
votes
1answer
172 views

Possible lower bound in quantum many body system with non-local terms

I am asking a question related to Lieb-Robinson bound and nonlocality. As we know from Lieb-Robinson theorem (see e.g. http://arxiv.org/abs/1008.5137): Suppose a Hamiltonian system is local, i.e. $H=\...
11
votes
2answers
639 views

Lower bound on the first eigenvalue of the Laplace-Beltrami on a closed Riemannian manifold

It has been proved by Li-Yau and Zhong-Yang that if $M$ is a closed Riemannian manifold of dimension $n$ with nonnegative Ricci curvature, then the first nonzero eigenvalue $\lambda_1(M)$ of the (...
1
vote
1answer
92 views

Bound on the weight of the minimum weight generator of [n,k] cyclic codes?

I'm looking at creating sparse generator matrices for cyclic codes of a given length and dimension. A generator matrix of an [n,k] cyclic code can be expressed as $G = \begin{bmatrix}g_0 & g_1 &...
4
votes
1answer
438 views

Lower bound on the tail of the hypergeometric distribution

Suppose there is a bag with $M$ white marbles and $N - M$ black marbles. Let $H(n, N, M)$ be a random variable which is number of white marbles in a draw, without replacement, of $n$ marbles from a ...
1
vote
1answer
70 views

Expectation of logarithmic of a Laplace random varible

Say $Y$ is a random variable with Laplace distribution with zero mean and variance parameter $b$. I am trying to compute the expectation of $\ln(Y+\alpha)$ ($\alpha>0$), that is: $$\int^{\infty}_{0}...
4
votes
1answer
286 views

A lower bound on the $L^2$ norm of a Dirichlet polynomial

The Question. Suppose $0 < \alpha < \beta$ are fixed, and $a_n$ is an arbitrary sequence of real numbers. Is it known how to bound from below \begin{equation*} \int_0^{T} \Big| \sum_{\alpha T &...
3
votes
0answers
246 views

Minimum number of perfect matchings in a regular bipartite graph

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph? One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
2
votes
1answer
180 views

using polynomials as lower / upper bound?

I'm interested in the question of given a differentiable and bounded function $f(\vec{x})$ (over a single variable or multiple variables, over a bounded domain $D$), finding a pair of polynomials $p_1(...
1
vote
3answers
202 views

Minimum number of unlabeled planar graphs

Does anybody know if there is any research on a lower bound on the number of (non-isomorphic) unlabeled planar graphs with maximum node degree $d$? Alternatively, a lower bound on the number of all ...
3
votes
1answer
536 views

Lower bounds on the error term of the prime number theorem

Are there any lower bounds on the error term for the prime number theorem, or in other words, is there a nontrivial $f$ s.t. $$f(x)\ll |\psi(x) - x|$$ where $\psi$ is the Chebyshev function.
8
votes
1answer
401 views

lower and upper bound for $\sum_{k=1}^n \frac{(-1)^{\Omega(k)}}k$?

Are there known any lower and upper bounds for $$ \sum_{k=1}^n \frac{(-1)^{\Omega(k)}}k, $$ where $\Omega(n)$ is the number of prime factors counting multiplicities of $n$? Or at least is it known ...
0
votes
0answers
121 views

Estimating when does a certain binomial sum exceed an upper bound

Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers $$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$ For example $f_{n,0} = 1,f_{...
0
votes
0answers
156 views

partition of an integer n into atmost k =O(log n) parts

Suppose you have a partition p of n into atmost k parts, say $$\{i_1, i_2, ..., i_j, ..., i_{k-1}\}$$ For example $\{1, 4\}$ is a partition of 10 into 3 parts (in this notation i am specifying the ...
2
votes
1answer
134 views

Looking for tighter bounds on a certain solution of a nonlinear equation

I have to solve an equation which is $$\sum_{i=1}^N x_i = \sum_{i=1}^N y_i,$$ where $$x_i = \frac{z_i}{1 + (K_i - 1) w}$$ and $$y_i = \frac{K_i z_i}{1 + (K_i - 1) w}.$$ The $z_i$ are all positive ...
17
votes
1answer
1k views

Quantitative lower bounds related to Zhang's theorem on bounded gaps

Let $\mathcal{H}=\left\{ h_{i}\right\} _{i=1}^{k}$ be an admissible set, and define $$\pi_{\mathcal{H}}(x)=\left|\left\{ n\leq x\ :\ \exists\ i,j\leq k,\ i\neq j\ \text{such that both }n+h_{i},\ n+h_{...
4
votes
2answers
2k views

Lower bound for Euler's totient for almost all integers

Let $\varphi(n)$ be the Euler's totient function. It is well know that $\liminf_{n \to \infty} \frac{\varphi(n)}{n / \log \log n} = e^{-\gamma}$, so that for $\varepsilon > 0$ it results $\frac{\...
3
votes
2answers
162 views

Techniques for showing optimality of given packing

There are some natural packing problems that have been asked in mathematics. Some of them are: 1)How many balls can be placed with in a cube? 2)How many equidistant points can be place on the ...
2
votes
2answers
370 views

Lower bounds on derivative around zero set of a positive smooth function

As part of a different problem, I came across the following simplified question, for which I cannot exhibit a proof nor a counterexample. Note that the assumptions of smoothness and strict positivity ...
0
votes
1answer
479 views

Good lower bound on matching in bipartite graph

Suppose a bipartite graph $G=(V_1 \cup V_2, E)$ is given, and one is interested in matching vertices $V_1$ to vertices $V_2$. Assume Hall's condition does not hold, so a perfect matching does not ...
5
votes
1answer
724 views

Simple lower bounds for Bell numbers (number of set partitions)?

The $n$-th Bell number $B_n$ represents the number of distinct partitions of a set with $n$ distinguished elements. It can be expressed as the infinite sum $B_n = (1/e)\sum_{k=1}^{\infty} (k^n/k!)$, ...