Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
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
0answers
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
0answers
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
3answers
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
0answers
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
2answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
3answers
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
2answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
3answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
2answers
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
2answers
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 ...