Skip to main content

Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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-...
loizuf's user avatar
  • 21
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 = ...
MathRevenge's user avatar
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\...
MathRevenge's user avatar
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} $$ ...
Max Muller's user avatar
  • 4,605
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 ...
Geoffrey Irving's user avatar
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) + \...
macat's user avatar
  • 145
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 ...
fengzju's user avatar
  • 99
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 ...
Mathhead123's user avatar
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 ...
Max Muller's user avatar
  • 4,605
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^...
jvc's user avatar
  • 183
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 ...
tim523's user avatar
  • 13
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} \...
reservoir's user avatar
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}{...
Juan Moreno's user avatar
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 ...
香结丁's user avatar
  • 331
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 ...
Charles's user avatar
  • 9,004
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'...
exfret's user avatar
  • 489
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 ...
Kaiyue Wen's user avatar
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 ...
Corram's user avatar
  • 143
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\...
Tom Solberg's user avatar
  • 3,929
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 ...
RandomMatrices's user avatar
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 \...
Matt Groff's user avatar
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 ...
35T41's user avatar
  • 123
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 ...
Scriddie's user avatar
  • 129
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\...
macat's user avatar
  • 145
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(...
macat's user avatar
  • 145
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 ...
macat's user avatar
  • 145
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: ...
π314's user avatar
  • 33
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(\...
Diffusion's user avatar
  • 763
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}$ ...
dtn's user avatar
  • 145
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 ...
Argemione's user avatar
  • 131
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}^\...
Goulifet's user avatar
  • 2,226
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 ...
Tom Solberg's user avatar
  • 3,929
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 ...
M. Stern's user avatar
  • 111
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 ...
trenta3's user avatar
  • 109
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 ...
R B's user avatar
  • 608
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 ...
dohmatob's user avatar
  • 6,764
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. ...
dohmatob's user avatar
  • 6,764
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...)$
José María Grau Ribas's user avatar
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$)...
M A's user avatar
  • 127
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 ...
PAb's user avatar
  • 187
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=\...
dohmatob's user avatar
  • 6,764
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 ...
Steve's user avatar
  • 1
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}$ ...
Sourangshu Ghosh's user avatar
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$ ...
Nick Belane's user avatar
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)...
Gabriele Oliva's user avatar
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 ...
ABIM's user avatar
  • 4,809
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$. ...
Thomas Yang's user avatar
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}\...
香结丁's user avatar
  • 331
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: ...
user avatar
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}\...
qwert's user avatar
  • 89