Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
137 questions
0
votes
0
answers
54
views
How can we tighten the bounds of the $\ell_1$-norm of $\mathbf{A}x$ where $\mathbf{A}\in\mathbb{Z}^{m\times p}$ and $x \in \{0,1\}^p$?
I am curious about the upper bound of $\|\mathbf{A}x\|_1$ where $\mathbf{A}\in\mathbb{Z}^{m\times p}$ and $x \in \{0,1\}^p$, for a specific $\mathbf{A}$ as defined below.
I know this is an NP-hard ...
0
votes
1
answer
97
views
Numerically bounding a Exponential-Trigonometric Integral [closed]
I am having some trouble with this (undergrad) problem. The Twitter account I found this from was deleted so I unfortunately have not found an answer.
I have tried decomposing into Riemann sum and ...
- 188k
1
vote
1
answer
148
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 ...
- 21
1
vote
1
answer
105
views
How to lower bound the probability that one Gaussian exceeds many others
I am interested in upper and lower bounding probability that one component of a multivariate Gaussian exceeds all others. For instance, say we have a multivariate Gaussian RV $X \sim N(\mu, \Sigma)$ ...
- 128k
2
votes
1
answer
386
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 = ...
- 63
1
vote
0
answers
82
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-...
- 21
2
votes
0
answers
80
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\...
- 63
2
votes
0
answers
119
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} $$
...
- 4,829
2
votes
1
answer
189
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) + \...
- 34.3k
9
votes
1
answer
788
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 ...
2
votes
1
answer
680
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)...
- 121
1
vote
1
answer
452
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 ...
- 143
1
vote
0
answers
109
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 ...
- 4,829
0
votes
0
answers
52
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 ...
CommunityBot
- 1
3
votes
1
answer
345
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} \...
- 128k
0
votes
0
answers
257
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}{...
- 4,713
2
votes
1
answer
335
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 ...
- 128k
4
votes
1
answer
258
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 ...
- 548
3
votes
0
answers
68
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'...
- 509
4
votes
1
answer
168
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 ...
- 128k
2
votes
1
answer
349
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 ...
- 61.9k
4
votes
0
answers
131
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\...
- 4,049
1
vote
1
answer
365
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 ...
- 9,501
0
votes
0
answers
171
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 \...
- 221
2
votes
1
answer
96
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 ...
- 37.7k
1
vote
0
answers
370
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 ...
- 129
3
votes
1
answer
575
views
Minimum number of perfect matchings in a regular bipartite graph
Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph?
One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
- 13.2k
2
votes
1
answer
383
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\...
- 2,826
5
votes
4
answers
917
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(...
- 34.3k
4
votes
2
answers
275
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 ...
- 37.7k
1
vote
1
answer
2k
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 ...
- 18.7k
17
votes
6
answers
10k
views
Lower bounds for chromatic number of a graph
I am trying to find a good lower bound for chromatic number of one family of graphs. I'm curious what are the known lower bounds for chromatic number. There are two obvious: $\chi(G) \geq \omega(G)$ ...
- 7,857
2
votes
0
answers
222
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: ...
- 33
2
votes
2
answers
532
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 ...
CommunityBot
- 1
2
votes
0
answers
147
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(\...
- 840
2
votes
0
answers
344
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}$ ...
- 33.8k
3
votes
0
answers
95
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,821
2
votes
1
answer
447
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{...
CommunityBot
- 1
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}^\...
- 2,306
1
vote
0
answers
234
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 ...
- 4,049
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 ...
- 111
7
votes
2
answers
3k
views
Lower bound for Euler's totient for almost all integers
Let $\varphi(n)$ be the Euler's totient function. It is well know that $\liminf_{n \to \infty} \frac{\varphi(n)}{n / \log \log n} = e^{-\gamma}$, so that for $\varepsilon > 0$ it results $\frac{\...
- 8,842
2
votes
0
answers
260
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 ...
- 14k
2
votes
0
answers
158
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 ...
- 2,545
0
votes
0
answers
330
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 ...
- 6,853
3
votes
3
answers
6k
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[...
- 18.7k
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. ...
- 6,853
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...)$
- 18.4k
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$)...
- 127
6
votes
2
answers
259
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 ...
- 9,486