# Questions tagged [lower-bounds]

The lower-bounds tag has no usage guidance.

135
questions

1
vote

0
answers

49
views

### Counting the number of local minima of a function that is the sum of square roots of cosines

Suppose you are given a set of functions $f_1, \ldots, f_n$. Every function is defined as follows
$$f_i(x) = \sqrt{1+C^2_i-2C_i\cos (x-D_i)}$$
where $0<C_i<1$ and $0\leq D_i<2\pi$ are real-...

2
votes

1
answer

319
views

### A maximal inequality

Let $\{X_i\}_{i\in\mathbb{N}}$ be i.i.d. symmetric random variables, with $-1\leq X_i\leq 1$, $\mathbb{E}(X_i) =0$, $\mathbb{E}(X_i^2) = 1$. We have that:
$$
P\left(\bigcap_{k = 1}^{n}\frac{|\sum_{i = ...

2
votes

0
answers

48
views

### Bound from above and from below the probability that a 1-D centered random walk remains at each step inside a square root boundary

Let $W_n = \sum_{i = 1}^{n}X_i$ be a random walk on $\mathbb{R}$, where the increments $X_i$ are i.i.d., symmetric around the origin ($X\sim -X$), such that $-1\leq |X(\omega)| \leq 1$ $\forall\omega\...

2
votes

0
answers

95
views

### Upper and lower bounds on the number of solutions to the equation $\frac{\pi}{4} = \sum_{k=1}^{n} c_{k} \arctan \left(\frac{1}{x_{k}} \right) $

Background
The Norwegian mathematician and astronomer Carl Størmer did important work on the equation
$$\frac{\pi}{4} = \sum_{k=1}^{n} c_{k} \arctan \left(\frac{1}{x_{k}}\right), \label{1}\tag{1} $$
...

1
vote

0
answers

88
views

### Obstacles to computing $\pi(n)$ in $O(n^{2/3-\epsilon})$ time

Edit: Apologies, as mentioned in the comments I failed to notice the analytic algorithms that take $O(n^{1/2+\epsilon})$ time, so this question doesn’t make much sense. It’s possible there is a ...

1
vote

1
answer

143
views

### Bound on a two-dimensional recursive series

For $n,k\in\mathbb{N}$, let $f(n,k)$ be defined as follows.
If $n \geq k$ and $n > 2$, then
$$
f(n,k) = \frac{k(n-k)}{n(n-1)}f(n-2,k-1) + \frac{k(k-1)}{n(n-1)}f(n-2,k-2) + \frac{n-k}{n}f(n-1,k) + \...

9
votes

1
answer

679
views

### The expected value of product of random variables which have the same distribution but are not independent

Given a positive integer $k$, is there a positive real number $c(k)$ such that $\mathbb{E}\left(\prod_{i=1}^k X_i\right)\geq c(k)$ for any $k$-random variables $X_1,X_2,\ldots,X_k$ which all have the ...

1
vote

1
answer

351
views

### Markov Inequality for lower bounds

In a paper I found a strange application of Markovs inequality which I couldn't follow maybe you can help. $X_k$ is the set of $k$-element Subsets of $\mathbb{Z}_d^n$ we fix a $C^{-1} \in X_{k-1}$ and ...

1
vote

0
answers

106
views

### What is known about the average growth rate of the denominators of $n$ Egyptian fractions summing to one?

Motivation
In the following question posted here on MO and over at MSE, user Noah Schweber asks about a weighted count on Egyptian fraction representations (EFRs). To that end, he defines the ...

0
votes

0
answers

46
views

### Lower bound for the fractional Sobolev norm of the Hermites function

For $r \in (0, 2)$, I am interested in a lower bound for the quantity :
$$I_r(n) := \int_{\mathbb{R}} |f_n(x)|^2 |x|^{r} dx$$
where $f_n(x) = (-1)^n (\sqrt{\pi} n! 2^n)^{-1/2} e^{x^2/2} \dfrac{d^n}{dx^...

0
votes

0
answers

51
views

### Classifier-specific lower bounds on the misclassification rate in binary classification

Consider a binary classification problem for $(X,Y)$, and let $\hat{f}$ be a proposed classifier. We wish to bound the misclassification rate $P(\hat{f}(X)\ne Y)$. There are many known lower bounds on ...

2
votes

1
answer

267
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

237
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

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

4
votes

1
answer

235
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

64
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

328
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

160
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

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

1
vote

1
answer

279
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

169
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

95
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

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

2
votes

1
answer

381
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

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

4
votes

2
answers

263
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

195
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

141
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

299
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

90
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

78
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

204
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

32
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

212
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

153
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

259
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

45
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

31
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

220
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

333
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

127
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

334
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

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

2
votes

1
answer

561
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

123
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

238
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

591
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

298
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}\...