Questions tagged [upper-lower-bounds]

For questions about finding upper or lower bounds for functions (discrete or continuous).

Filter by
Sorted by
Tagged with
1 vote
0 answers
5 views

Variational Lower Bound with latent SDE

In this paper https://arxiv.org/pdf/2007.06075.pdf, the authors give a formula in equations 13 and 14, for the ELBO for a specific VAE (latent variable governed by an SDE) that I have difficulty ...
user avatar
1 vote
1 answer
39 views

Solution verification: is that quantity bounded from below?

I would like to to draw your attention on a problem that my class mate posted earlier, showing you our idea for a possible solution. Let $p>1, s>0$ and $F$ be a function such that $$F(t)\le \...
user avatar
  • 817
0 votes
1 answer
40 views

Is that quantity bounded from below?

Let $p>1,s>0$ and $F$ be a function such that $$F(t)\le \frac{|t|^p}{p} +|t|^{p+p^{\prime}}e^{|t|^{p^{\prime}}}\quad\mbox{ for all } t\in\mathbb{R},$$ where $p^{\prime}$ denotes the conjugate ...
user avatar
  • 2,173
1 vote
0 answers
29 views

Integral bound from Steven Orey article

I am trying to show that $$ \int_0^\infty e^{-x^2/2}(x^2+s)^{-\beta}\, dx\leq 4s^{\frac12-\beta} $$ for $\beta>1/2$ and $s>0$. It appears in this article: https://link.springer.com/article/10....
user avatar
-1 votes
0 answers
15 views

A bound on a function involving exponentials [closed]

Does there exist constants $c,x_0>0$ such that $$\sqrt{e^{1/x}-1}\left(1-\sqrt{e^{-1/x}}\right)\leqslant \frac{c}{x^2}$$ for all $x>x_0$? So far I have only been able to show that this is $O(x^{...
user avatar
  • 29
1 vote
0 answers
18 views

Show that the logaritmic primal barrier $B(x,\rho)$ is not bounded from above (for $x\in \Omega$) for any fixed $\rho>0$

Let $x\in\mathbb{R}$. Consider the problem $$\text{minimize}\quad \frac{1}{1+x^2}\quad\text{s.t}\quad x\geq 1$$ Show that the logaritmic primal barrier $B(x,\rho)$ is not bounded from above (for $x\...
user avatar
0 votes
0 answers
30 views

Exercise A.14(b) in "Supplement for Measure, Integration & Real Analysis" by Sheldon Axler.

I am reading "Supplement for Measure, Integration & Real Analysis" by Sheldon Axler. I have no idea about Exercise A.14(b). Please tell me a solution to Exercise A.14(b). Exercise A.14: ...
user avatar
  • 6,147
2 votes
1 answer
28 views

Upper bound for a certain sum involving multinomial coefficients

It is clear that $$ \sum_{\vert \alpha \vert=k}\frac{k!}{\alpha!}=n^k,$$ where $k$ is a given positive integer and $\alpha\in \mathbb{N}^{n}$ such that $\alpha=(a_1, \dots, \alpha_n)$, $\vert \alpha \...
user avatar
  • 668
-2 votes
1 answer
53 views
+100

Corrected conjecture about a possible inequality $\sum_{i=1}^{n}\sqrt{\frac{x_i+1}{4x_i^2+10x_i+4}}\leq \frac{n}{3}$ .

Hi it's a follow up of Prove $\sum_{cyc}{\sqrt{\frac{x+1}{x^2+16x+1}}}\geqslant 1$ and $ \sum_{cyc}{\sqrt{\frac{x+1}{4x^2+10x+4}}}\leqslant 1$ for $x,y,z>0,xyz=1$ : Problem : Let $x_i>0$ and $n$ ...
user avatar
  • 3,399
8 votes
4 answers
203 views

Inequality involving sums with binomial coefficient

I am trying to show upper- and lower-bounds on $$\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}\min(i, n-i)$$ (where $n\geq 1$) in order to show that it basically grows as $\Theta(n)$. The upper-bound is easy ...
user avatar
0 votes
1 answer
32 views

Let ${A_n}$ be one set sequence, why lower limitation is $\varliminf_{n\rightarrow \infty}A_n=\bigcup_{n=1}\bigcap_{k=n}A_n$, How to understand it?

I'm confused about the definition of upper limit and lower limit of a set sequence. Could I think the lower limitation of one set sequence as "The largest intersection while $n$ goes to infinity&...
user avatar
1 vote
0 answers
18 views

Tight bounds for the expected maximum value of k IID Binomial(n, p) random variables

What is the tightest lower and upper bound for the expected maximum value of k IID Binomial(n, p) random variables I tried to derive it : $$Pr[max \leq C] = (\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^...
user avatar
0 votes
0 answers
21 views

Difficulty understanding some inequalities in S,A,I,R disease modelling

Consider this paper (reading the entire pdf is not required) on disease modelling. There are four real functions of interest, based on constant positive parameters $\mu,\nu,\delta,\beta$ and four ...
user avatar
  • 103
0 votes
0 answers
12 views

Number of elements in $Z^n$ with norm 2 less than some positive B [duplicate]

Is there any result or tight bound on the cardinal of : $\{\textbf{z}\in\mathbb{Z}^n / \lVert\textbf{z}\rVert_2 \leq B\}$ for some positive $B$. Did not find any topic on this, sorry if it is a dupe.....
user avatar
  • 1
4 votes
1 answer
200 views

Multiplicative energy and Cauchy-Schwartz

Let $A$ be a finite set in a ring, and define $E(A) =\left|\left\{(a, b, c, d) \in {A}^{4}: c a=d b\right\}\right|.$ A number of papers (e.g. here) quote the lower bound $$E({A}) \geq \frac{|{A}|^{4}}{...
user avatar
  • 251
1 vote
1 answer
50 views

What is an example of a nonempty subset of $\mathbb{R}$ that is bounded above that does not contain its least upper bound?

What is an example of a nonempty subset of $\mathbb{R}$ that is bounded above that does not contain its least upper bound? This is an on-a-review sheet for my final. I thought the completeness axiom ...
user avatar
0 votes
0 answers
32 views

Upper bound for sum of waves

Let the function $f(t)$ be defined as a linear combination of sinusoidal waves, with different amplitudes, frequencies and phases, i.e. $$f(t) = \sum_{i=1}^n a_i \sin \left( \omega_i t + \varphi_i \...
user avatar
  • 563
1 vote
0 answers
38 views

Prove $\sum_{x\le Q} e(\alpha x)\ll \lVert \alpha\rVert^{-1}$ for $\alpha\not \in\mathbb Z$

I just want to know the proof that $\left\vert\sum_{x\le Q} e(\alpha x)\right\vert\ll \lVert \alpha\rVert^{-1}$ for $\alpha\not \in\mathbb Z$, for any positive integer $Q$. Here $\lVert x\rVert$ means ...
user avatar
1 vote
1 answer
59 views

If $f(x)=-e^{-x}$ on $(0,\infty)$, Prove that $\inf_{x>0}$ $f(x)=-1$.

If $f(x)=-e^{-x}$ on $(0,\infty)$, Prove that $inf_{x>0}$ $f(x)=-1$. For all $x>0$, $f(x)>-1$ then $-1$ is a lower bound of $f$ on $(0,\infty)$. I did it up to here. And I want to find a any $...
user avatar
1 vote
0 answers
12 views

Uniform bound on product of Gamma functions in an article by Jerison and Kenig

I have been trying to read Jerison and Kenig's article Unique continuation and absence of positive eigenvalues for Schrödinger operators, and I am having difficulties understanding how they obtain the ...
user avatar
0 votes
1 answer
37 views

Prove that $f(x)=\frac{1}{x}$, $g(x)=x$ are unbounded on $(0,\infty)$.

Prove that $f(x)=\frac{1}{x}$, $g(x)=x$ are unbounded on $(0,\infty)$. We show that $f$ is unbounded by assuming that there is a bound $M>0$ and then arriving at a contradiction. From the graph of $...
user avatar
1 vote
0 answers
22 views

Necessary and sufficient condition for Radon transform of a probability density function to be bounded

Let $f:\mathbb R^n \to \mathbb R$ be a probability density function, meaning that $f \ge 0$ and $f \in L^1(\mathbb R^n)$, and define its Radon transform $R[f]$ by $$ R[f](w,b) := \int_{\mathbb R^n}\...
user avatar
  • 8,309
1 vote
2 answers
29 views

Upper bound for binomial coefficients tighter than $(ne/k)^k$

In Shiryaev's book problems in probability, an upper bound for binomial coefficients is shown in section 1.2.1: $$\binom{m+n}{n}\le(1+m/n)^n(1+n/m)^m.$$ It seems that this bound is sharper than the ...
user avatar
  • 11
0 votes
1 answer
68 views

Confusing statement regarding Routh-Hurwitz criterion

I'm currently reading "On the Solutions and the Steady States of a Master Equation" by Joel Keizer. Keizer introduces a matrix $\Lambda$ with the following properties: $-\Lambda_{ij} \geq 0$ ...
user avatar
  • 35
0 votes
0 answers
17 views

Find the upper bound probability of a collision in a packet scheduling problem - Exercise

Let $G$ be a graph representing a network. On this network we have $N$ packets, each with a starting node, a path and an end node. Time is discrete, so each packet move only at a certain instant. When ...
user avatar
1 vote
0 answers
30 views

Lower bounding a exponential/binomial expression

I have been struggling to lower bound the following expression \begin{equation} f(N):= \frac{1}{N}\sum_{i=1}^N \frac{1}{2^N} \sum_{k=1}^{i} 2^{i-k} \binom{N+k-2}{k-1} , \end{equation} with some simple ...
user avatar
  • 198
0 votes
0 answers
24 views

Using CDF to upper bound MGF

I have some random variable with a complicated but known analytical CDF and I need an upper bound on the MGF. Direct MGF computation is intractable due to the messy nature of the CDF so I was trying ...
user avatar
3 votes
1 answer
42 views

Exponential bound for tail of standard normal distributed random variable

Let $X\sim N(0,1)$ and $a\geq 0$. I have to show that $$\mathbb{P}(X\geq a)\leq\frac{\exp(\frac{-a^2}{2})}{1+a}$$ I have no problem showing that $\mathbb{P}(X\geq a)\leq \frac{\exp(\frac{-a^2}{2})}{a\...
user avatar
  • 73
0 votes
1 answer
17 views

Bound product of two numbers by sum of their squares

How can I bound the product of two reals by the sum of their squares? Let $s = a^2 + b^2$ and $p = ab$. Can I find a constant $C$ and an exponent $\alpha$ such that this holds? $$ p \leq Cs^\alpha $$ ...
user avatar
  • 4,336
1 vote
0 answers
29 views

Bound on amount of minima of finite Fourier sum

Consider a finite Fourier sum of the form $$f(\theta) = \sum_{i=1}^n r_i \cos(m_i \theta) \,,$$ where $n \geq 1$ is an integer, the $r_i$ are positive real numbers and the $m_i$ are integers. Is there ...
user avatar
  • 109
0 votes
2 answers
39 views

A different upper bound for the binomial coefficient

I need to prove the following statement: If $3\leq k < t$ then \begin{equation*} \binom{t}{k} < 2^{t-1}-k+1. \end{equation*} I was given the hint to prove it by induction over $t$ with $k$ ...
user avatar
0 votes
1 answer
30 views

Upper bound for $(1+x)^{1/2}$ where $x>0$

I am trying to find an upper bound, which is an algebraic function in $x$, for $(1+x)^{1/2}$ for $x>0$. Note that $x$ need not be less than $1$. Binomial expansion can be used if $x<1$ but here ...
user avatar
  • 3,126
0 votes
0 answers
21 views

What about The Catalan–Dickson conjecture for this sequence $ S(n)^{S(S(n))^{S(S(S(n))))\dots}} $ with $S(n)=\sigma(n)-n$?

It is known that aliquote sequence defined as $S(n)=\sigma(n)-n$ where $\sigma(n)$ is the sum of power divisor function (is the sum of all of $n’s$ natural divisors.),The Catalan–Dickson conjecture ...
user avatar
-1 votes
0 answers
31 views

Proving {a^ncb^n | n > 0} is not bounded above and bounded below

I've been trying to prove that { a^ncb^n | n ∈ ℕ / {0} } is bounded below and not bounded above, but I am not sure if my proof is correct. Let A = { a^ncb^n | n ∈ ℕ / {0} }, ∑ = {a, b, c} Bounded ...
user avatar
2 votes
0 answers
39 views

A version on Gronwall's inequality with interval $[-\tau, t]$

Let $\tau$ and $T$ be positive constants and $u:[-\tau,T] \rightarrow \mathbb R$ be a Riemann integrable function. Assume that for all $t \in [0, T],$ $$u(t) \leq a+b \int_{t-\tau}^{t}u(s)ds.$$ Is it ...
user avatar
1 vote
1 answer
48 views

If a real-valued $f(t)$ is absolute continuous on a domain $[a,\,b]$, Does it imply it is also absolute integrable $\int_a^b |f(t)|dt < \infty$?

If a real-valued $f(t)$ is absolute continuous on a domain $[a,\,b]$, Does it imply it is also absolute integrable $\int_a^b |f(t)|dt < \infty$? If is not true in general, please give some counter-...
user avatar
  • 891
1 vote
1 answer
24 views

Upper bound on a difference of two square root functions

I am trying to find an upper bound on $\sqrt{x+y}-\sqrt{x}$, $x\geq 0,y\geq -x$. I would think $\sqrt{x+y}-\sqrt{x}\leq \sqrt{|y|}$ but I'm not sure how to prove that because although both sides are ...
user avatar
  • 3,126
0 votes
0 answers
77 views

Upper bound for Meijer-G function

What I need is a monotonically decreasing function that forms an upper bound for the following function: \begin{equation} - G_{0,6}^{4, 0}\biggl({-\atop -\frac{1}{2},\frac{1}{2},\frac{5}{6},\frac{7}{6}...
user avatar
  • 1
0 votes
0 answers
50 views

Bounding this summation

Let $\{x_n\}_{n\geq 0}$ be a sequence of non-negative integers such that for every $n\geq 1$ it holds that $$x_n \leq x'_{n-1} = \max\left\{ 1,\, \sum^{n-1}_{k=0}x_k\right\}.$$ Prove that $$ \sum^{M}_{...
user avatar
0 votes
1 answer
78 views

The lower bound about the binomial coefficient

From easy computation we can get \begin{align*} {n\choose{\ell}}=\frac{n}{\ell}\cdot\frac{n-1}{\ell-1}\cdots\frac{n-(\ell-1)}{1}\geq\frac{n^{\ell}}{\ell^{\ell}}, \end{align*} where the last inequality ...
user avatar
  • 1,396
0 votes
1 answer
23 views

Is a continuous function on an open or semi-open interval bounded?

Per sagemath.org: A function is said to be continuous on an interval when the function is defined at every point on that interval and undergoes no interruptions, jumps, or breaks. If some function f(...
user avatar
  • 23
0 votes
0 answers
12 views

Looking for upper bound for a sum over compositions

Consider the matrix \begin{bmatrix} 1 & \alpha_1 & 0 & \dots & & & 0 \\ \alpha_1 & 1 & \alpha_2 & 0 & \dots & & 0 \\ 0 & \alpha_2 & 1 & \...
user avatar
2 votes
1 answer
201 views

Bounding spectral radius of special matrix (extension of the extension)

This is an extension of Bounding spectral radius of special matrix (extension), which has been already solved. Let $A$ be an $n \times n$ matrix with all nonnegative entries and row sums strictly less ...
user avatar
0 votes
0 answers
32 views

Thighter bound than Chebyshev for the error of an estimator

I have seen Chebyshev inequality applied to bound the error of an estimator wrt to its expected value. For example, the estimator of the mean of a set of values after they have been protected with a ...
user avatar
  • 19
0 votes
1 answer
49 views

Algorithmic Fine-Grained Space Lower Bounds

Given an algorithmic problem, theoretical computer science has powerful tools in order to give lower bounds on the number of required computation steps, based on the strong time hypothesis (SETH). For ...
user avatar
  • 454
4 votes
4 answers
136 views

Finding "growth" rate of a sum

Question Let $n$ be a positive integer. The sum in question is: $$S_n=\sum_{i=1}^{ n}\frac{1}{2^i}\bigg(1-\frac{1}{2^{i}}\bigg)^{n}.$$ Clearly this sum is convergent, and it seems like the sum goes to ...
user avatar
1 vote
1 answer
42 views

The additive Chernoff bound for the absolute value.

I am trying to derive a generic, additive Chernoff bound for $\Pr[|X-\mu|\leq a]$ with $a>0$. By generic I mean a Chernoff bound in terms of the moment generating function instead of assuming a ...
user avatar
  • 902
0 votes
1 answer
46 views

Determine whether the family $\mathcal{F}=\{f \text{ holomorphic in } \mathbb{D} : f(0)=1 \text{ and } \mathfrak{R}f(z)>0 \}$ is normal

Let $\mathcal{F}=\{f \text{ holomorphic in } \mathbb{D} : f(0)=1 \text{ and } \mathfrak{R}f(z)>0 \: \forall z \in \mathbb{D}\}$. I want to determine whether this is a family of normal functions. In ...
user avatar
  • 1,355
-2 votes
1 answer
26 views

Can we limit both sides of an inequality involving least upper bound?

Suppose we have the sequence $a_n$ such that $a_n \leq \sup\{a_k : k \geq n\}$ for all $n \in \mathbb{N}$ and $\lim_{n\rightarrow\infty}\space a_n$ exists. Can we conclude that $\lim_{n\rightarrow\...
user avatar
3 votes
1 answer
152 views

Show $\sum^M_{i=1}a_i/\sqrt{a'_{i-1}}\leq(\sqrt2+1)\sqrt{a'_M}$ for non-negative integers $a_i$ with $a_n\leq a'_{n-1}=\max\{1,\sum^{n-1}_{k=0}a_k\}$

Let $\{ a_0, a_1, \dots\}$ be a sequence of non-negative integers such that for every $n\geq 1$ the sequence satisfies $a_n \leq a'_{n-1} = \max\{ 1, \sum^{n-1}_{k=0}a_k\}$. Show that $$ \sum^{M}_{i=1}...
user avatar
  • 503

1
2 3 4 5
37