# Questions tagged [lower-bounds]

The lower-bounds tag has no usage guidance.

127
questions

2
votes

1
answer

150
views

### Simple anticoncentration bound for binomially distributed variable

The following question, which arose during my research, seems deceivingly simple to me, but I could not find any elegant and formal argument.
For a binomially distributed variable $X \sim \text{Bin} \...

0
votes

0
answers

171
views

### Is it possible to bound Mertens function $M(n)$ from an inclusion-exclusion formulation?

In this post I proposed a formulation of Mertens function $M(n)$ using the inclusion-exclusion principle, as follows:
$$M(n)=-\pi\left(n\right)+\left(\sum_{p_{i}<\sqrt{n}}\pi\left(\lfloor\frac{n}{...

2
votes

1
answer

110
views

### The lower bound of bivariate normal distribution

Suppose $(Z_1, Z_2)$ is the zero-mean bivariate normal distribution with covariance $\left( \begin{matrix} 1 & \rho; \\ \rho & 1\end{matrix} \right)$ with positive $\rho > 0$. What I want ...

0
votes

0
answers

29
views

### $\min(|\lambda_{\min}(A(c))|)$ for a special matrix $A(c)$ defined over $\{-1,-1\}^N$

For a given constant $E$, is there way to find the lower bound of the following expression?
$\min_{c\in\{-1,+1\}^N, -\sum_{i,j}c_ic_j=E}(|\lambda_{\min}(A(c))|)$ for matrix $A(c)$ defined over $\{-1,-...

0
votes

0
answers

37
views

### A Pinching inequality with respect to a continuous basis

For a generic trace-class matrix $A=\sum_{n,m}A_{n,m}|n\rangle\langle m|$, one can easily find the bound $\|P[A]\|_1\leq\|A\|_1\leq \|A\|_{1,1}$, where $\|A\|_1=\sum_{k}\sigma_k(A)$ is the trace norm, ...

3
votes

1
answer

180
views

### Bounds for the crossing number in terms of the braid index?

Is there a lower bound on the crossing number of a knot (resp., link) with braid index $b$?
For knots, I believe the smallest crossing number for braid index 2 is 3, the smallest crossing number for ...

3
votes

0
answers

59
views

### Does this information theoretical thought experiment have a name or corresponding area of research?

I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...

2
votes

1
answer

264
views

### Lower bound on sum of independent heavy-tailed random variables

I have a sum of $n$ i.i.d random variables $X_i$ such that $E[X_i] = 0$,$\mathrm{E}[|X_i|^{1 + \delta}]$ exists for some $0 < \delta < 1$ but $\mathrm{E}[|X_i|^{1 + \delta+ \epsilon}]$ does not ...

4
votes

1
answer

123
views

### Existence of copula bound pointwise strictly smaller than the Fréchet-Hoeffding upper bound

Consider bivariate copulas $C_1$ and $C_2$ with $\max\{C_1(u,v), C_2(u,v)\}< M_2(u,v)$ for all $u,v \in(0,1)$, where $M_2(u,v) := \min\{u,v\}$ is the Fréchet-Hoeffding upper bound.
Is there a ...

4
votes

0
answers

102
views

### Log of a truncated binomial

Let $X$ follow a binomial distribution with $n$ trials and success probability $p$, and let $0\leq k\leq n$. Are there any natural approximations or bounds for the ratio $$\frac{\boldsymbol{E}\log\...

0
votes

0
answers

31
views

### Minimal value of condition number of positive-definite matrices, w.r.t $\ell_1$ norm

Let $n \ge 1$ be an integer and let $p \in [1,2]$. For any $n \times n$ positive-definite matrix $M$, let $\kappa_p(M)$ be the condition number of $M$ w.r.t to the $\ell_p$-norm on $\mathbb R^n$, i.e
\...

1
vote

1
answer

122
views

### Tree width and clique width of regular graphs

Consider a $k$ regular graph of $n$ vertices, where $3 \leq k \leq (n-1)$. Is there any upper or lower bound, in the worst case, known for either the tree-width or the clique width of each $k$ regular ...

0
votes

0
answers

157
views

### How many elements have a "small" order in a finite field?

I'm hoping that this is an easy question for someone.
How many elements can we expect to have multiplicative order at most $n^{1/c}$ in one of the finite fields $\mathbb{F}_p$ with $p$ prime with $n \...

2
votes

1
answer

85
views

### Lower bound on the number of balanced graphs

Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs
and ...

1
vote

0
answers

215
views

### Lower bound on the sum of the product of random variables

Let $X_i$ be the $i$-th element of the vector $X=(X_1, ..., X_m)$ of i.i.d. random variables.
I am looking for a lower bound for the expression
$\mathbb{P}((\sum^n_{i=1}\prod^{m_i}_{j=1}(X_j))^2 \geq ...

1
vote

1
answer

321
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\...

5
votes

4
answers

763
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(...

3
votes

2
answers

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

2
votes

0
answers

98
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: ...

2
votes

0
answers

122
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(\...

2
votes

0
answers

167
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}$ ...

3
votes

0
answers

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

2
votes

1
answer

74
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}^\...

1
vote

0
answers

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

1
vote

0
answers

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

2
votes

0
answers

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

2
votes

0
answers

129
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

198
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

43
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

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...)$

1
vote

0
answers

26
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

165
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

230
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

110
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

317
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}$ ...

8
votes

0
answers

255
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

353
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)...

1
vote

0
answers

112
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

186
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$. ...

2
votes

1
answer

1k
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

577
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

234
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

351
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

187
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

84
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

198
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

72
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

67
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

171
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

242
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$, ...