Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
259 views

Lower bound and limit of a sum with binomial coefficients

Let $$A_k = \sum_{i=1}^k i {3k-2i-1 \choose i-1} {2i-2 \choose k-i}$$ $$B_k = \sum_{i=1}^k i {3k-2i-2 \choose i-1} {2i-1 \choose k-i}$$ $$C_k = \sum_{i=1}^k (3k-2i-2) {3k-2i-3 \choose i-1} {2i\...
user avatar
  • 115
5 votes
4 answers
660 views

Limit of a sum with binomial coefficients

Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$ $$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$ $$C_k = \frac{\sum_{i=1}^k(...
user avatar
  • 115
3 votes
2 answers
175 views

An inequality involving binomial coefficients and the powers of two

I came across the following inequality, which should hold for any integer $k\geq 1$: $$\sum_{j=0}^{k-1}\frac{(-1)^{j}2^{k-1-j}\binom{k}{j}(k-j)}{2k+1-j}\leq \frac{1}{3}.$$ I have been struggling with ...
user avatar
  • 115
0 votes
0 answers
37 views

Bounds for ratio of Bessel functions

I know several good papers where bounds of Bessel function ration considered. For instance, the following Bessel function ratio, $$h(z) = \frac{I_{\nu}(z)}{I_{\nu+1}(z)}$$ has bounds $$h(z)<\frac{z}...
user avatar
0 votes
0 answers
48 views

Nontrivial lower-bound for $\mathbb P(f(X) \le \alpha \|\nabla f(X)\|)$

Let $f:\mathbb R^d \to \mathbb R$ be a differentiable function whose gradient is $L$-Lipschitz (w.r.t euclidean norm), for some fixed $L \in [0,\infty)$. Let $X=(X_1,\ldots,X_d)$ be a concentrated ...
user avatar
  • 5,580
2 votes
0 answers
65 views

When does Le Cam's method give tight lower bounds for distribution testing?

In the context of statistical estimation or distribution testing, Le Cam's method is a way to prove lower bounds on the minimax sample complexity ([1,2,3,4], further details below). My question is: ...
user avatar
  • 33
2 votes
0 answers
105 views

How is the Cauchy-Schwarz equality and the assumption on the support of $g$ used to derive this bound?

I am currently reading On Uniqueness Properties of Solutions of Schrödinger Equations and a having trouble understanding a claim made on page 1819. Context from the paper: let $g\in C^\infty_0(\...
user avatar
  • 336
0 votes
0 answers
82 views

Extension of the Gershgorin circle theorem for symmetric matrices and localization of positive eigenvalues

In mathematics, the Gershgorin circle theorem can be used to localize eigenvalues of a matrix (including symmetric). Let $A$ be a real symmetry $n × n$ matrix, with entries $a_{ij}$. For $i∈{1,…,n}$ ...
user avatar
  • 125
3 votes
0 answers
68 views

Probability of winning a $k$-rounds coin toss game

Let $p,q \in [0,1]$ with $p>q$. I denote by $B_k(p), B_k(q)$ two independent random variables following the binomial distribution, with parameters $(k,p)$ and $(k,q)$ respectively. Informal ...
user avatar
  • 131
2 votes
1 answer
70 views

Asymptotic behavior of the moments of non-negative sequences

We consider a sequence $u = (u_k)_{k\geq 1}$ such that $u_k \geq 0$ for any $k \geq 1$. We assume that there exists a critical $p_c \in \mathbb{R}$ such that, for any $q<p_c <p$, $$\sum_{k=1}^\...
user avatar
  • 2,010
1 vote
0 answers
103 views

"Tails" of a multinomial distribution

Let $X_1,\dots,X_N$ denote a collection of independent samples of a uniform multinomial random variable in $\mathbb{Z}^k$, with the number of trials equal to $n\ll k$. (By "uniform", I mean ...
user avatar
  • 3,668
1 vote
0 answers
29 views

Are there known bounds on these ratios of chromatic polynomials?

The chromatic polynomial $P(G, \lambda)$ gives the number of proper vertex colorings of the graph $G$ with $\lambda$ colors. I'm interested in how many possible colorings you loose when you add an ...
user avatar
  • 111
2 votes
0 answers
76 views

Gershgorin-type bounds for smallest eigenvalue of positive-definite matrix

I would like to know if there are known results for bounding eigenvalues of positive-definite matrices, in particular gram matrices $AA^\top$ based on easily computable functions of $A$. Gershgorin ...
user avatar
  • 109
2 votes
0 answers
105 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 ...
user avatar
  • 608
0 votes
0 answers
116 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 ...
user avatar
  • 5,580
1 vote
0 answers
42 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. ...
user avatar
  • 5,580
11 votes
3 answers
1k 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...)$
user avatar
1 vote
0 answers
25 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$)...
user avatar
  • 127
5 votes
2 answers
133 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 ...
user avatar
  • 187
0 votes
0 answers
107 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=\...
user avatar
  • 5,580
0 votes
0 answers
88 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 ...
user avatar
  • 1
2 votes
0 answers
293 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}$ ...
user avatar
7 votes
0 answers
214 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$ ...
user avatar
1 vote
0 answers
266 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)...
user avatar
1 vote
0 answers
97 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 ...
user avatar
0 votes
0 answers
168 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$. ...
user avatar
1 vote
1 answer
843 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}\...
user avatar
  • 173
2 votes
0 answers
567 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: ...
user avatar
0 votes
1 answer
177 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}\...
user avatar
  • 91
2 votes
1 answer
308 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{...
user avatar
  • 91
0 votes
1 answer
137 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 (...
user avatar
  • 5,580
3 votes
1 answer
74 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, ...
user avatar
  • 5,580
1 vote
2 answers
172 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 ...
user avatar
0 votes
0 answers
42 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 ...
user avatar
  • 1
1 vote
1 answer
62 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(·)$, ...
user avatar
  • 13
0 votes
0 answers
137 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{...
user avatar
  • 119
7 votes
1 answer
197 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$, ...
user avatar
3 votes
3 answers
2k 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[...
user avatar
  • 141
8 votes
2 answers
566 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://...
user avatar
-1 votes
1 answer
164 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$ ...
user avatar
0 votes
0 answers
53 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 ...
user avatar
3 votes
2 answers
212 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 ...
user avatar
0 votes
1 answer
176 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)$ ...
user avatar
  • 424
2 votes
1 answer
271 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)= ...
user avatar
  • 189
0 votes
1 answer
177 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]? $$
user avatar
  • 608
2 votes
1 answer
121 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 $...
user avatar
  • 1,698
3 votes
2 answers
222 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)\:=\:\...
user avatar
  • 467
5 votes
3 answers
137 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 ...
user avatar
1 vote
0 answers
128 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} &...
user avatar
  • 1,017
0 votes
0 answers
213 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 ...
user avatar
  • 1,017