37
votes

### What is the limit of $a (n + 1) / a (n)$?

The value is close to $e$ but not. It's actually the positive real root of $p(t) := t^3 - 2t^2 + t - 8$. This is solvable via ACSV (see book by Pemantle and Wilson 2013). To summarize, the ...

9
votes

Accepted

### lower bound for Perron-Frobenius degree of a Perron number

If a Perron number $\lambda$ has negative trace, then any Perron-Frobenius matrix must have size strictly greater than the algebraic degree of $\lambda$, for example the largest root of $x^3 + 3x^2-...

9
votes

Accepted

### Probability of a random variable greater than its expected value

Let $Y:=X-EX$. We need to obtain a lower bound on $P(Y>0)$.
Suppose that $-a\le Y\le b$ for some real $a>0$ and $b>0$, and that $EY^2\ge s^2$ for some real $s$. Then
$$1_{Y>0}\ge\frac{...

9
votes

Accepted

### What is the limit of $a (n + 1) / a (n)$?

Decided to do a separate answer as there is a subtle point involved which is not mentioned in my comments to the answer by @Max
Starting from the generating function by Max Alexeyev
$$
\sum_{m,n\...

9
votes

Accepted

### Simple anticoncentration bound for binomially distributed variable

Let $Z\sim N(0,1)$, $p_n:=n^{-1/4}$, $q_n:=1-p_n$. By the Berry--Esseen inequality,
$$P(X\ge EX)\ge P(Z\ge0)-0.5\frac{n(p_nq_n^3+q_np_n^3)}{(np_nq_n)^{3/2}}=\frac12-o(1)$$
as $n\to\infty$. $\quad\Box$
...

8
votes

Accepted

### Lower bound on exponential sums

There are a few things to clear up.
The first is that, on the page in the Bourgain paper you mention, he actually proves the lower bound $I(N,6,2)\gg N^3\log N$ from the fact that
$$ \left\lvert\...

7
votes

Accepted

### Given a polynomial constraint equation in $n$ variables, can one conclude that the sum of the variables is non-negative?

A counterexample: $n=4$,
$$(x_1,\dots,x_4)=\left(-\frac{1}{4},-\frac{3}{8},-\frac{3}{8},\frac{\sqrt{1970156929}-2048}{45375}\right).
$$
So, by what you noted, your conjecture fails to hold for any $...

7
votes

### Lower bound on exponential sums

The result for $I(N,6,2)$ was proved by Rogovskaya N. N. in the article An asymptotic formula for the number of solutions of a certain system of equations. The proof is elementary. Main idea is to ...

7
votes

### What is the limit of $a (n + 1) / a (n)$?

Here is a derivation for an explicit formula for $a(n)$.
The generating function for $f(m,n)$ is
$$F(x,y) := \sum_{m,n\geq 0} f(m,n)x^m y^n = \big(1 + \frac{3x^2y^2}{1-xy(1+2x+y)}\big)\frac{1}{1-x}\...

7
votes

### Limit of a sum with binomial coefficients

Simplifying we have:
$$S_k = \frac{\sum_{i=1}^k i\binom{k}{2i-k}\binom{2k - i - 1}{k - 1}}{k\binom{2k-1}{k}}.$$
It follows that $S_k$ equals the coefficient of $x^k$ in
$$\frac{1+2x}{2(1+x)(1-x)^k\...

6
votes

Accepted

### Nontrivial lower bound on the sum of matrix norms

No. With $n = r = 2$, set $$X = \bigg(\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \bigg) \, , \quad V = \bigg( \begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array} \bigg) \, .$$
In ...

6
votes

Accepted

### Lower bound on the entries of the Perron vector

This seems to be answered in the accepted answer to this question: The height of the Perron-Frobenius eigenvector
For convenience, here is the estimate:

5
votes

### Fast computation of a ball with radius r with largest number of input points

I asked the participants at a conference
to consider this problem,
and the consensus was that subquadratic time is possible, through one of two routes.
(1) Lift the points to the paraboloid $z=x^2+y^2$...

5
votes

### A distribution which is Wasserstein-close to a compactly supported distribution is almost compactly supported

The claimed inequality is not true. The simplest possible counterexample works: let $x,y \in \mathbb{R}^n$ with $|x-y| = \epsilon$, and take $\mu = \delta_x$, $\nu = \delta_y$. Then $W_1(\mu,\nu) = \...

5
votes

Accepted

### Hausdorff distance is a lower (or upper bound) for what probability metric?

A general note is that the answer depends heavily on the properties of $\mu$.
First a note that in general $d_H(A,B) \not \le C \cdot W_p(\mu|_A,\mu|_B)$ for $p\in[1,\infty)$ and some $C>0$. ...

5
votes

### Proofs of Lower Bounds for Ramsey Numbers?

There have been a two recent improvements on the Barak-Rao-Shaltiel-Wigderson result result mentioned by Ryan Williams. There are now explicit construction of a $2^{(\log\log N)^C}$-Ramsey graph over $...

5
votes

### Lower Bounds for the Roots of Polynomials

I am not sure how you are using Rouche's theorem, but if you make $f(z) = e^z,$ while $g(z)=e^z - P_k(z),$ then the minimum of $|e^z|$ on $|z|\leq R$ is $\exp(-R),$ so as long as this is larger than ...

5
votes

Accepted

### An inequality involving binomial coefficients and the powers of two

For $j=0,\dots,k-1$,
\begin{equation*}
\frac1{2k+1-j}=\int_0^1 x^{2k-j}\,dx.
\end{equation*}
So,
\begin{equation*}
\begin{aligned}
s:=&\sum_{j=0}^{k-1}\frac{(-1)^{j}2^{k-1-j}\binom{k}{j}(k-...

5
votes

Accepted

### Limit of a sum with binomial coefficients

Ryabenko-Skorokhodov algorithm is implemented in Maple package SumTools since Maple v11. (DefiniteSumAsymptotic function). Check this reference if you want to see all the details.
Ryabenko, A. A.; ...

5
votes

Accepted

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

Certainly. All you need is $EX^2=+\infty$. Then the characteristic function $f_X(t)$ satisfies $\lim_{t\to 0}\frac{1-|f(t)|}{t^2}=+\infty$, so for every finite interval $I\subset \mathbb R$, we have $\...

4
votes

### Bounds on the smallest real positive root of a polynomial

The structure of the polynomial $P(x)=−ax^q+bx^p−c$, for $a,b,c>0$, $q>p$ is very suitable for analysis with Descartes Rule of Signs.
Since $P(x)$ has two sign changes in its coefficients it ...

4
votes

Accepted

### What is the approximation of $\log(|\zeta'(\frac{1}{2}+it)|)$ in Dirichlet polynomial if it is exists?

A Dirichlet polynomial is a function of the form
$\sum_{1\le n \le X} a_n n^{-s}$, where $a_n$ are complex numbers and
$s = \sigma + i t$ with $\sigma$ and $t$ real. It is an analytic
function of $s$....

4
votes

Accepted

### 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$

For real $u_m>0$, the probability in question is
$$p_m:=P(\|X\|^2\ge u_m|X_1|)=P\Big(\frac{|X_1|}{\|X\|^2/m}\le\frac m{u_m}\Big).$$
Passing to a subsequence, without loss of generality
$$\frac{u_m}...

4
votes

Accepted

### Distance of low-rank matrices to the identity for the $\infty$-norm

Theorem 1.1 from Alon's paper "Perturbed identity matrices have high rank: proof and applications" says that if $\|X-I_n\|_\infty<c$ with $1/(2\sqrt n)<c<1/4$, then $m\gg \log n/(c^...

3
votes

Accepted

### Any inequalities / estimates for a lower bound of the $L^2$ inner product of a quantity and its derivative?

I don't think what you want is possible.
In phase space $x$ and $v$ are basically quantities that can be independently prescribed. The first terms of your left hand side is linear in $v$. So fixing $...

3
votes

### Large deviation upper bound for Chi-squared random variable

See B. Laurent and P.Massart, Adaptive estimation of a quadratic functional by model selection, Ann. Stat., 28 (2000) 1302--1338.
Equations (4.3) and (4.4) say that for any $x\gt 0$:
$$P(X_n \ge n + ...

3
votes

Accepted

### Lower bound on the sum of pmf squared of a hypergeometric distribution

Suppose that $i=n-i=m$ (so that $n=2m$) and $m$ is even; I suppose that such $i$ and $m$ you consider relevant. Then
\begin{equation}
p_X(x)=\binom mx^2\Big/ \binom{2m}m\le\binom m{m/2}^2\Big/ \...

3
votes

Accepted

### Complicated bound after using Stirling's approximation

I understand from the reference to Stirling that you are looking for a large-$d$ approximation of
$$a_{\rm max}= \Bigl(\pi^{d/2}\Gamma(\frac{1}{2}d+1)^{-1} + 1\Bigr) \left(\frac{h^{d+1}}{2} \Gamma \...

3
votes

### Discrepancy bounds for moderate points counts in dimensions from d=2 to 32?

As I understand it, you might be interested in a quantity called the inverse of the star-discrepancy. Given dimension $d$ and some $\varepsilon > 0$, the inverse of the star-discrepancy $n(d,\...

3
votes

### Nontrivial lower bound on the sum of matrix norms

Let function $f : \mathbb R^{m \times n} \to \mathbb R_0^+$ be defined as follows
$$f (\mathrm X) := \| \,\mathrm X \mathrm A^\top \|_\text{F}^2 + \| \,\mathrm X^\top \mathrm A \,\|_\text{F}^2 + \...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

lower-bounds × 130pr.probability × 34

inequalities × 17

co.combinatorics × 16

nt.number-theory × 15

probability-distributions × 14

linear-algebra × 12

matrices × 11

st.statistics × 10

graph-theory × 8

analytic-number-theory × 8

asymptotics × 8

measure-concentration × 8

reference-request × 7

matrix-analysis × 7

binomial-distribution × 7

limits-and-convergence × 6

polynomials × 5

it.information-theory × 5

approximation-theory × 5

fa.functional-analysis × 4

integration × 4

eigenvalues × 4

matrix-theory × 4

binomial-coefficients × 4