# Questions tagged [lower-bounds]

The lower-bounds tag has no usage guidance.

103
questions

**2**

votes

**0**answers

63 views

### Size of an “average” ϵ-net on the unit sphere

This is a question I originally asked on math.stackexchange, but didn't receive a satisfying answer.
Let $\epsilon>0$ and consider constructing a set $S_\epsilon\subseteq S^{d-1}$ of points on the ...

**0**

votes

**0**answers

17 views

### Lower-bound smallest eigenvalue of covariance matrix of $y = f(Ax)$, for $x$ uniform on unit-sphere

Let $A=(a_1,\ldots,a_)$ be a fixed $k \times d$ matrix (with $d$ large), and $x$ be a random vector uniformly distributed on the unit-sphere in $\mathbb R^d$. Let $f:\mathbb R \to \mathbb R$ be a ...

**1**

vote

**0**answers

39 views

### Analytic lower-bound for minimal value of $\|x\|^2$ such that $\|Cx-b\|^2 \le c^2$ (a hyperellipsoid)

Let $C$ be an $n \times p$ matrix and $b$ be a column vector of length $n$, and $c>0$. Let $E := \{x \in \mathbb R^p \mid \|Cx-b\| \le c\}$, a hyperellipsoid in nonstandard position.
Question 1. ...

**11**

votes

**3**answers

969 views

### What is the limit of $a (n + 1) / a (n)$?

Let $a(n) = f(n,n)$ where $f(m,n) = 1$ if $m < 2 $ or $ n < 2$ and $f(m,n) = f(m-1,n-1) + f(m-1,n-2) + 2 f(m-2,n-1)$ otherwise.
What is the limit of $a(n + 1) / a (n)$? $(2.71...)$

**1**

vote

**0**answers

21 views

### Given a unit vector $x\in\mathbb R^d$, what is the worst possible within-cluster sum of squares for 2-means clustering?

This is a question I originally posted to math.stackexchange.com but it didn't attract any answers, and I was wondering if someone here can help.
Consider a unit vector $x\in\mathbb R^d$ ($\|x\|_2=1$)...

**5**

votes

**2**answers

99 views

### Distance of low-rank matrices to the identity for the $\infty$-norm

I am trying to get a lower bound (or even the exact value) of
$$
\min_{X \in \mathbb{R}^{n\times n}} \|X - I_n\|_{\infty} \enspace \text{s.t.} \enspace \mbox{Rank}(X) = m
$$
where $m \leq n$, and the ...

**0**

votes

**0**answers

54 views

### Lower-bound on expected value of norm of transformation of random vector with iid Rademacher coordinates

Let $n$ be a large positive integer. Let $A$ be a positive-definite matrix such with eigenvalues $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n$ such that $\lambda_n = o(1) \to 0$ and $\lambda_i=\...

**0**

votes

**0**answers

75 views

### Spread of a disease on a modular chessboard (torus) - lower bound

I learned about the following result from one of Peter Winkler's books:
It is impossible to infect the entire $n\times n$ chessboard (usual chessboard) starting from fewer than $n$ infected cells.
The ...

**2**

votes

**0**answers

260 views

### Mertens Bound and the Riemann Hypothesis

Let $M(x)$ denote the Mertens function ($M(x)=\sum_{i=1}^{x}\mu(i)$ where $\mu(i)$ is the Möbius function) and let $\Lambda(i)$ denote the Mangoldt function ($\Lambda(i)$ equals $\log(p)$ if $i=p^{m}$ ...

**7**

votes

**0**answers

185 views

### Restricted divisor summatory function

I have a problem that boils down to prove that the succession $\{a_n\}$ tends to infinity, where
$$a_n:=1+\sum_{0\leq j<n}D_{2j+1}(n-j)$$
and $D_{m}(n)$ is the number of divisors $d>1$ of $n$ ...

**1**

vote

**0**answers

147 views

### Is this lower bound on the singular values of the sum of two matrices correct?

Equation 7 of this paper (Ramazan Türkmen, Zübeyde Ulukök, Inequalities for Singular Values of Positive Semidefinite Block Matrices, International Mathematical Forum, Vol. 6, 2011, no. 31, 1535 - 1545)...

**0**

votes

**0**answers

105 views

### How to adapt an equation from a paper to a Cox–Ingersoll–Ross stochastic differential equation, and why?

I quote from Delbaen and Shirakawa - An interest-rate model with upper and lower bounds.
Starting from a stochastic differential equation of the form:
$$dr_t=\alpha\left(r_{\mu}-r_t\right)dt+\beta\...

**1**

vote

**0**answers

39 views

### A lower-bound on matrix-function with vector product

I am currently trying to show that a sequence of homeomorphisms converges to some limiting homeomorphism using Anderson's the inductive convergence criterion. However I can't explicitly compute the ...

**0**

votes

**0**answers

148 views

### Lower bound of exponential sum

This question is a close cousin of the following:
Lower bound on exponential sums
Let $\phi:[0,1]\to \mathbb R$ be a smooth function with $\frac 1 {10}<\phi'< 10, \frac 1 {10}<\phi''< 10$. ...

**1**

vote

**1**answer

506 views

### Finding the expectation $\mathrm{E} (1/ X)$ for a negative binomial random variable $X$

Suppose a random variable $X$ is distributed as $\operatorname{NB}(\mu, \theta)$, and its mass is as follows
$$ \mathrm{P}(X = y) = \binom{y + \theta - 1}{y} \left(\frac{\mu}{\mu + \theta}\right)^{y}\...

**2**

votes

**0**answers

550 views

### An interesting sequence of numbers arising from the Riemann hypothesis

A very good coincidence occurred today with me. While just plotting random functions in Mathematica, I entered this command:
...

**0**

votes

**1**answer

74 views

### better lower (and upper) bound for $i$'s moment of function of binomial random variable with $i = \frac{1}{j}, j \in \mathbb{N}$

I want to derive a lower bound for $E\left[\left(\frac{X}{k-X}\right)^{i}\right] $ with $X \sim Bin_{(k-1),p}$ and $ k \in \mathbb{N} $. So far I could prove that
\begin{equation}
E\left[\frac{X}{k-X}\...

**2**

votes

**1**answer

173 views

### How to find upper and lower bound

Let $\Sigma \in S_{++}^n$ be a symmetric positive definite matrix with all diagonal entries equal to one. Let $U \in \mathbb{R}^{n \times k_1}$, $W \in \mathbb{R}^{n \times k_2}$, $\Lambda \in \mathbb{...

**0**

votes

**1**answer

79 views

### Lower-bound on smallest singular-value of rectangular random matrix

Let $X$ be a random $N \times n$ matrix with iid entries from $\mathcal N(0, 1)$ and with $n/N =: \lambda(N,n) \le \lambda_0$, for some $\lambda_0 \in (0, 1)$. That is, $X$ is genuinely rectangular (...

**3**

votes

**1**answer

71 views

### If $X \sim N(0,I_m)$, what is a necessary and sufficient condition on $u_m > 0$ such that $\lim\sup_{m\to \infty} P(\|X\|^2 \ge u_m|X_1|) = 1$

Let $m$ be a large positive integer and $X=(X_1,\ldots,X_m) \sim N(0,I_m)$. I wish to show that the squared norm of $X$ is much much bigger than the absolute value of any of the $X_j$'s. For example, ...

**1**

vote

**2**answers

143 views

### What is the approximation of $\log(|\zeta'(\frac{1}{2}+it)|)$ in Dirichlet polynomial if it is exists?

I have done some search many times on web to find any approximation of $\log|(\zeta'(s))|$ in Dirichlet polynomial but I didn't got it, Probably that $\log(|\zeta'(s)|$ dosn't have a Dirichlet ...

**0**

votes

**0**answers

38 views

### Upper bounding the sum with hypergeometric and binomial probabilities

Could you please help me upper bound this tricky expression:
$$P(A)=\sum_{i=0}^n{\left( 1 - \dfrac{\binom kq \binom {n-k}{i-q}}{\binom {n}{i}} \right)}^I \binom ni p^i {(1-p)}^{n-i}$$.
So far I only ...

**1**

vote

**1**answer

57 views

### How to compare the minimums of two discrete convex functions?

I have a question that troubled me for a long time.
If I have two convex discrete function $f(·)$ and $g(·)$ such that $f(·) \ge g(·)$. (may be not necessary?)
Let $x_1 = \text{argmin } f(·)$, ...

**0**

votes

**0**answers

54 views

### Bounding the absolute value of a complex integral with itself

I already asked a similar question on this topic, but after a small discussion, I noted that I did must boil down the problem such that the solution space so to say to maybe have a concrete answer. I ...

**0**

votes

**0**answers

71 views

### Bounding the absolute value of a complex integral

I'm working on some problems involving Fourier transforms and convolution problems and there is one problem I cannot solve. In my situation we have a complex valued function $f(ix)$, with $x\in\mathbb{...

**7**

votes

**1**answer

160 views

### Is this lower bound for the size of minimal vertex cover new/interesting?

I have found this lower bound for the size of minimal vertex cover (and proved it).
If a simple connected graph G on n vertices has largest and smallest eigenvalues $\lambda_1,\lambda_n$, ...

**2**

votes

**3**answers

980 views

### Probability of a random variable greater than its expected value

We have a lot of probabilities lower bounding as (e.g. chernoff bound, reverse markov inequality, Paley–Zygmund inequality)
$$
P( X-E(X) > a) \geq c, a > 0 \quad and \quad P(X > (1-\theta)E[...

**8**

votes

**2**answers

488 views

### Lower bound on exponential sums

Let $k\geq 2$. Consider the following norm of exponenetial sum:
$$
I(N,p,k)=\int_0^1\int_0^1 \left|\sum_{n=0}^N e^{2\pi i (n x+n^k y)}\right|^p dxdy.
$$
Bourgain mentioned on Page 118 of
https://...

**-1**

votes

**1**answer

162 views

### Any simplification of this inequality if it is true? :For $t\geq 1.22$: $|\zeta(0.5+it)|\leq 0.5 \frac{|\Gamma(0.5+it)|}{|\Gamma(-0.5+it)|}$

When I tried to give bounds for $\zeta(0.5+it)$ using some transformations over Gamma function using the function $f(x)=\exp(-n x)$ over the range $(0,+\infty)$ , For $ Re(s)=\frac12 $ and $t >0$ ...

**0**

votes

**0**answers

51 views

### if $\max_{z \in K} |\zeta(z+it)-f(z)|<\epsilon.$ then is this $\lim_{t\to \infty} \inf \frac {|\zeta'(z+it)|}{|f'(z)|} $ a finit limit?

Universality theorem of Riemann zeta function states that :Let $K$ be a compact subset with connected complement lying in the strip $\{1/2 < \operatorname{Re}(z)<1\}$, and let $f : K \rightarrow ...

**4**

votes

**2**answers

208 views

### Lower bounding decoding error in a noisy adversarial channel

Problem description
Suppose we have a finite alphabet $\mathcal{X}$, where each letter $X \in \mathcal{X}$ indexes into some fixed set of distributions, $\{P_{1},\ldots,P_{|\mathcal{X}|}\}$. For ...

**0**

votes

**1**answer

150 views

### Survey papers on spectral radius [closed]

Let $M$ be a $n\times n$ matrix.
Are there any survey papers which give lower and upper bounds on its spectral radius?
What are the ways to find some lower bounds and upper bounds on $\rho(M)$ ...

**2**

votes

**1**answer

151 views

### Lower-bound for $E[\min(X, k)]$ where $X$ is sum of Bernoulli random variables with $E[X]$ being a linear function of $k$

Given a real number $\alpha \in [0.5, 1.5]$, an integer number $k>1$, and a set of independent Bernoulli random variables $x_1, \dots, x_n$, I am interested to find a lower-bound for $F(\alpha, k)= ...

**0**

votes

**1**answer

117 views

### Are there known bounds on the expectation of the truncated Beta distribution?

Let $X\sim beta(\alpha,\beta)$ be a random variable and let $\tau\in(0,1)$.
Are there any known closed-form bounds (I'm specifically interested in lower bounds) on
$$
\mathbb E[X\ | X\le \tau]?
$$

**2**

votes

**1**answer

116 views

### Minimum local permutation data needed to globally merge locally sorted sequences?

We have $k$ blocks of integer sequences $B_1,\dots,B_k$ where $B_i$ is a sequence $$a_{i,1},\dots,a_{i,n_i}$$ with $a_{i,j}\leq a_{i,j+1}$.
Denote the permutation matrix $M_{\ell,\ell'}$ that merges $...

**3**

votes

**2**answers

209 views

### Given a polynomial constraint equation in $n$ variables, can one conclude that the sum of the variables is non-negative?

Currently I'm stuck as follows;
at least a positive proof if $n=3$ would be a great nice-to-have!
Consider real numbers $x_1,x_2,\dots,x_n$ satisfying
$$\prod^n_{k=1}\left(1-x_k^2\right)\:=\:\...

**5**

votes

**3**answers

129 views

### Fast computation of a ball with radius r with largest number of input points

We are given a set S of n points equipped with some metric and an integer $r>0$. We define $B(x,r) \subseteq S$ (the ball with radius r centered in x) to be the set of points in S within distance r ...

**1**

vote

**0**answers

113 views

### Prove that these linear programming problems are bounded by $O(k^{1/2})$ [closed]

The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:
$$\begin{array}{ll} \text{minimize} &...

**0**

votes

**0**answers

186 views

### What do square roots as minimums have to do with Harmonic numbers?

In an earlier question where I conjectured (and GH from MO confirmed) that the von Mangoldt function is the limit at s=1 of a certain Dirichlet series:
$$\Lambda(m)=\lim_{s\to 1+}\zeta(s)\sum_{d\mid ...

**1**

vote

**0**answers

81 views

### Bounds on spectral radius using chromatic number

I am struggling with this question:
If I have a connected graph $G$ on $n$ vertices and $m$ edges with chromatic number $d$ then how can I give a bound(lower and upper) on its spectral radius in ...

**2**

votes

**1**answer

241 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

**1**answer

118 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 ...

**3**

votes

**0**answers

549 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

**1**answer

944 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 ...

**5**

votes

**1**answer

410 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

**1**answer

99 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

**1**answer

88 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

**2**answers

296 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 ...

**3**

votes

**2**answers

209 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 ...

**7**

votes

**2**answers

479 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 ...