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 ...
- 351
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-...
- 2,738
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{...
- 110k
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\...
- 17.2k
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$
...
- 110k
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\...
- 6,598
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 $...
- 110k
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 ...
- 11.3k
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}\...
- 29.5k
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\...
- 29.5k
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 ...
- 475
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:
- 95.2k
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$...
- 148k
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) = \...
- 28.8k
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$. ...
- 556
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 $...
- 43.5k
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 ...
- 95.2k
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-...
- 110k
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.; ...
- 1,697
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 $\...
- 58.2k
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 ...
- 686
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$....
- 642
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}...
- 110k
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^...
- 22.6k
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 $...
- 35.2k
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 + ...
- 36.9k
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/ \...
- 110k
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 \...
- 172k
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,\...
- 2,189
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 + \...
- 2,226
Only top scored, non community-wiki answers of a minimum length are eligible