Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [upper-lower-bounds]

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

0
votes
1answer
20 views

Lower bound on Sum of squared differences

Consider $n+2$ real numbers $x_i$ with $0 \leq x_i \leq \frac{1}{2}$. Additionally, not all $x_i$ are the same. Now define two quantities $\Phi = 4\sum_{i=0}^{n+1}x_i^2$ $\Phi' = \sum_{i=1}^{n}(x_{...
1
vote
1answer
53 views

A lower bound for $(1-e^x)^n$

I want to find a lower bound for $$(1-e^x)^n$$ $n$ integer, $x$ real, and $1-e^x\geq 0$. One lower bound is (Bernoulli's inequality) $$(1-e^x)^n\geq 1-ne^x$$ But I need a tighter lower bound that is ...
0
votes
1answer
44 views

Bounded operators versus bounded sequences

Let $X$ be a Banach space, $Y$ normed, $A_n\in B(X,Y)$. Prove that $(\|A_n\|)$ is bounded if and only if for all $x\in X$ and for all $f\in Y^*$: $(|f(A_n(x))|)$ is bounded. Any hints on that? $A_n$ ...
1
vote
1answer
49 views

Isoperimetric inequality for non-spherical multivariate Gaussian

Disclaimer: Sorry in advance, if the question is not very reasonable. Recently (like a few days ago...), I've started studying isoperimetric inequalities, and my thoughts on the subject are rather ...
0
votes
0answers
32 views

A guess on the bound of the product of bounded sequence $\{x_{k}\}$ with $\lim_{t\to\infty}\prod_{k=0}^{t}(1-x_{k})=0$ exponentially.

Let $\{x_{k}\}$ be a bounded sequence, i.e., $|x_{k}|\le T$ for some positive constant $T$. Also, $x_{k}\neq 1$ and $x_{k}\neq 0$. If \begin{align*} \lim_{t\to \infty}\prod_{k=0}^{t}(1-x_{k})=0 \end{...
4
votes
2answers
55 views

A bound for the products of a bounded sequence $\{x_{k}\}$ with $\lim_{t\to \infty}\prod_{k=0}^{t}(1-x_{k})=0$

Let $\{x_{k}\}$ be a bounded sequence with $x_{k}\neq 1$, and if \begin{align*} \lim_{t\to \infty}\prod_{k=0}^{t}(1-x_{k})=0. \end{align*} The question is can we infer \begin{align*} \prod_{k=0}^{t}...
0
votes
1answer
27 views

Probability Whole Sample Below Expectation

Let $X_1,X_2,\ldots,X_n$ be i.i.d real-valued random variables with finite variance $\sigma^2>0$. Can we non-trivially upper bound the probability $$ \mathbb{P}\bigl(\max_{1\leq i\leq n} X_i < \...
2
votes
3answers
67 views

Upper bounding this integral.

Would appreciate any help in finding a good closed form upper bound on this integral not in terms of the exponential integral $Ei(x)$: $$ I = \int_{t=0}^x \frac{e^t-1}{t}dt$$ So far I have tried ...
1
vote
1answer
48 views

What is a simple upper bound for $\exp\left(-\frac{1}{2}(x-(2\log(1/\delta)^{1/2}))^2\right)$ given $x \ge0$ and $\delta \in (0, 1)$?

Question For $x \ge 0$ and small $\delta \in (0, 1)$, what is a "simple" good upper bound for $$u(x,\delta) := \exp\left(-\frac{1}{2}(x-(2\log(1/\delta)^{1/2}))^2\right), $$ that doesn't involve $x$ ...
0
votes
0answers
42 views

Bounds on $\sum_{l=0}^j (-1)^l 3^{j-l}\binom{j}{l}\sum_{k=0}^{\alpha n} \binom{n-j}{k-l}$

In the course of solving some optimization, I encountered the following sum: $\sum_{l=0}^j (-1)^l 3^{j-l}\binom{j}{l}\sum_{k=0}^n \binom{n-j}{k-l}=2^n, \quad j\in\left\{0,1,\dots,n\right\}$. I am ...
1
vote
2answers
38 views

Check if $a_n=(n-1)/(n+1)$ is bounded

It seems that $n\geq 0$ but I can't get a bound out of this. This sequence is increasing so $a_n \geq a_0=-1$ if I understand correctly but for it to be bounded don't we need an upper bound also?
1
vote
1answer
30 views

What bound does Chebychev’s inequality give for $P(Y ≥ 3 \text{ or } Y ≤ 1)$?

Suppose you flip four fair coins. Let Y be the number of heads obtained. (a) What bound does Chebychev’s inequality give for $P(Y ≥ 3 \text{ or } Y ≤ 1)$? $E(Y) = \sum_{y=1}^{4}yP(Y = y) = \sum_{y=1}^...
0
votes
1answer
24 views

Find a bound to the mean of a sum of Bernoulli variables

Let $\delta_i$ be a set of independent Bernoulli variables with $\mathbb{E}(\delta_i)=p$ for all $i=1,\ldots,n$. Let $$X = \sum_{i=1}^n |1-\frac{1}{p}\delta_i|$$. I get that $$\mathbb{E}(X)=\sum_{k=0}...
4
votes
3answers
106 views

Variable in upper bound of sum

I need to find a solution $x$ of the following equation: $$\sum_{n=0}^{\left[\frac{0.9}{x}\right]} (1-nx) = 45$$ where $[.]$ denotes the nearest integer function. I am an engineer and I'm currently ...
0
votes
0answers
28 views

Bounding length of Vectors

I have problems to bound a potential. Let $w_i$ be vectors for $i = 0,\dots, n$ and $||w_i||$ the Euclidean norm of $w_i$. $\Phi = 4 \sum_{i=0}^n ||w_i||^2$ $\Phi' \leq ||w_0 - w_1||^2 + ||w_{n-1}...
0
votes
0answers
9 views

Identifiability of Normal From Conditional Measure (Monotonicity of CDF Ratios)

Let $Z_x \sim \mathcal{N}(x,1)$, $D_1 = [0,c]$, and $D=[-c,c]$. Can we determine $x$ from $$f(x) = \mathbb{P}(Z_x\in D_1 | Z_x\in D) = \frac{\Phi(c - x) - \Phi(-x)}{\Phi(c - x) - \Phi(-c-x)}?$$ In ...
2
votes
3answers
86 views

Upper bound of the integral $\frac{a^{n}}{n!}\int_{0}^{1} e^{at} t^{n}(1-t)^{n}dt$.

I came across this integral in a proof related to using the Legendre polynomial to establish irrationality. $$ I_{n}=(-1)^{n} \frac{a^{n}}{n!} \int\limits_{0}^{1} e^{at} t^{n}(1-t)^{n}dt $$ The ...
0
votes
0answers
19 views

Simple lower bound on Gaussian CDF evaluated at sum: $G(s + t)$ in terms of $G(s)$, with $s, t \ge 0$ and $s \le 1$

Let $G: s \mapsto \int_{-\infty}^s g(s)ds$ be the CDF of the standard Gaussian (with $g(s) := (2\pi)^{-1/2}\exp(-s^2/2)$ the density) and $s \le 0 \le t$. Question what is a simple lower bound for ...
3
votes
3answers
147 views

Is there a clean way to show $\frac{\log(x-\tfrac12\log x)}{\log(x+\tfrac12\log x)}>1-\tfrac1x$ for all $x>1$?

In writing a paper I had to show that the inequality holds for large enough $x$, which is easy, but I ended up being pretty sure it holds for all $x>1$, so I would like to include the proof of the ...
1
vote
0answers
35 views

Tight upper and lower bounds of the CDF of a summation of random variables

I have this random variable $$Y = \sum_{k=1}^KX_k$$ where $X_k$ are i.i.d. random variables with CDF and PDF $F_X(x)$ and $f_X(x)$, respectively. In my application, the CDF of $Y$ denoted by $F_Y(...
1
vote
0answers
29 views

Obtaining an upper bound on transition probabilities by truncation

Consider a two-dimensional Markov chain. Let's call the first dimension "Level" and the second dimension "Phase". The state space is $(\ell, p)$ such that $\ell \geq 0$ and $0 \leq p \leq h$. The ...
0
votes
1answer
35 views

Lower bound spectral radius of matrix

Let $\alpha, \beta, \gamma \in (0, 1)$ such that $\alpha < \beta, \gamma < \beta$. Let $d \in \mathbb{N}, d \geq 4$. I am interested in bounding from below the spectral radius $\rho(K)$ of the ...
3
votes
2answers
67 views

Expected Proportion of Random Variables

In the case that non-negative random variables $X_i$ are i.i.d we have $$\mathbb{E}\frac{X_i}{X_1+\dots+X_n} = \frac{1}{n}.$$ What can be said in the non-identical case? Specifically, if $X_i\geq 0$ ...
2
votes
0answers
97 views

When does the busy beaver function surpass TREE(n)? [closed]

Since TREE is a computable function the BB function grows faster than it, but TREE seems to grow much more quickly early on, so when does Busy Beaver surpass it?
0
votes
0answers
16 views

How to calculate upper bound of combinations?

I have 10 nodes and 14 RF antennas and 14 millimeter wave antennas. How can I calculate the upper bound of all combinations of distributions of these RF and millimeter wave antennas on the 10 nodes ...
0
votes
1answer
49 views

indicator function with integrals

I have a following integral $$\int_{0}^{T-b}f\left(\tau\right)d\tau$$ where $T-b$ is an arbitrary constant number. I try to change the limits of this integral by using an indicator function and I ...
1
vote
0answers
35 views

Chi-squared distribution tail bound

I have been studying about tail bounds and I read the following claim: A variable $\xi \sim N(0, 1)$ satisfies the following tail bound for $t \geq 1$: $ \mathbb{P}(\xi \geq t) \leq e^{-t^2/2} $ ...
0
votes
0answers
23 views

What bound can we place on the similarity of projections of vectors?

Assume we have a collection $X$ of $m > n$ unit vectors $\{x_1,...,x_m\}$ in $\mathbb{C}^n$, and let $\langle \cdot, \cdot \rangle$ be the usual inner product on $\mathbb{C}^n$. Define the "...
0
votes
1answer
36 views

Chernoff bound $ \mathbb{P} \left\lbrace \Big| X - \mathbb{E}(X) \Big| > t \right\rbrace $

How to apply the Chernoff bound to upper bound the following probability: $$ \mathbb{P} \left\lbrace \Big| X - \mathbb{E}(X) \Big| > t \right\rbrace $$ where $X$ follows the distribution given ...
0
votes
1answer
32 views

Upper bound for the integral.

Is there an upper bound for the following integral in terms of $c$ and $A$ ? $\int_{-\infty}^{+\infty}\frac{(1+|x+c|)^A}{(1+|x|)^B} dx$, where $c, A\in \mathbb R$ and $B\in \mathbb R^+$. Here $A$ ...
2
votes
0answers
30 views

Is there a bounded function that is always greater than $M (t) = \max_{s \in [0, t]} \left| \zeta \left( \frac{1}{2} + i s \right) \right|$?

Is there a bounded function that is always greater than $M (t) = \max_{s \in [0, t]} \left| \zeta \left( \frac{1}{2} + i s \right) \right|$ ?
2
votes
4answers
50 views

Is subtracting inequalities allowed? $\sup(A+B)= \sup(A)+\sup(B)$ - proof verification

Given sets $A$ and $B$ define $A+B =\{ a+b:a \in A \ and\ b \in B \}$. If these sets are nonempty and bounded above show $ \sup(A+B)= \sup(A)+\sup(B)$. My Attempt: Let $\sup A= \alpha$ and $\sup B= ...
1
vote
0answers
36 views

Solving OR bounding sums of solutions to certain linear diophantine equations

(This question arose during group work on classifying modular tensor categories.) Let $p$ and $q$ be two distinct primes. We seek integral solutions $\lbrace x_{i,j} \rbrace$ to the equation \begin{...
3
votes
2answers
81 views

A better lower bound of the definite integral $\int_0^1\frac{\ln^2x}{e^{2x}}\,dx$

In this post of my blog, I proved that $$\int_0^1\frac{(x^2-3x+1)\ln x}{e^x}\,dx=-\frac1e.$$ Now if we apply the Cauchy-Schwarz inequality for integrals, we get $$\frac1{e^2}\le\int_0^1(x^2-3x+1)^2\,...
0
votes
0answers
37 views

Upper bound on some sum

Let $n\geq 1$, $\epsilon>0$, $v\in \mathbb{R}^n$ and $c>0$. I want to prove that: $$\sum_{k=1}^n \left|v^2_{k+1}-v^2_k \right|\sqrt{\epsilon \frac{k}{n^{\frac{1}{3}}}+c} \leq \sqrt{\epsilon}n^\...
2
votes
3answers
77 views

Prove $2+2\cos(2\pi\theta) \leq 4\exp(-2\|\theta \|^2)$.

I'm struggling to prove the following easy looking inequality from page 7 of Maynard's Primes with Restricted Digits . Let $\theta \in \mathbb{R}$, and let $\|\theta\|$ denote the distance to the ...
1
vote
0answers
25 views

Mutual Information between dataset and output of algorithm

I am trying to understand how the Mutual Information behaves when I have a sequence of iid samples $X^n$, where each $X$ takes values in an alphabet $\mathcal{X}$ and I have an algorithm $\mathcal{A}:\...
0
votes
0answers
26 views

When finding the upper bound, why is a ceiling evaluated to a +1?

Why does removing the ceiling result in $a + 1$? I'm reading Introduction to Data Compression by Guy E. Blelloch on page $19$ on Information Theory, here he is proving an upper bound. $$ \begin{...
1
vote
2answers
50 views

Clean Proof that a set is bounded in multiple dimension

Say $M:=\{(x,y)\in \mathbb R^{2}:x^2+y^2\leq 1\}$ I am confused on how to prove the a multidimensional set is bounded. This is important in order to be able to prove that $M$ is indeed compact. It ...
0
votes
4answers
56 views

Show that $f(x) = { 1\over x^2 + \ln^2x }$ is bounded

How do i show that $f(x) = { 1\over x^2 + \ln^2x}$ is bounded? Let $g(x) = x^2 + \ln^2x$. The domain of $f(x)$ is $x > 0$, for the denominator we have that $x^2 > 0$ and $\ln^2x > 0$ hence ...
1
vote
0answers
18 views

Upper bound of $ \sum_{n\leq x}f(n) $ where $ f(n)=\sum_{r=1}^{n-1}\mu(r)\mu(n-r) $

$Cx^2$ is a trivial bound by just counting the total number of terms in these sums. From here I have attempted to use $$ \sum_{n\leq x} \mid \mu(n) \mid =\frac{6}{\pi^2}x(1+o(1)) \text{, } x \to \...
0
votes
2answers
52 views

Properties of the solution of the Ordinary Differential Equation $y' = y(y-1)(y-2)$ as per the Initial conditions?

Consider the Ordinary Differential equation $y' = y(y-1)(y-2)$. Then from the different initial conditions, can we derive properties of the function $y$ ? 1) I thought of finding the solution to ...
0
votes
1answer
25 views

Mean of a function, under different distributions

Define a function: $f: X \rightarrow \mathbb{R}$. The notation $\mathbb{E}_{x \sim D}[f(x)]$ denotes the mean of the function under distribution $D$, where $D$ is a continuous distribution defined ...
0
votes
0answers
9 views

Can we comment upon the minimum eigen value for the following matrix?

Considering the matrix $$k_{\Omega}I + k_RJC $$ where $k_R, k_{\Omega} \in \mathbb{R} > 0$, $I = 3\times 3$ Identity matrix, $J \in \mathbb{R}^{3\times 3}$ positive definite matrix and $C = \frac{1}...
1
vote
1answer
40 views

Arc-length without bounds

When I tried to calculate the Arc length of $r = (\cos^3x, \sin^2x)$, I used the arc length formula and got $\cos x \cdot \sin x(3\cos x+2)$. I do not get why we don't need the bounds (range) for the ...
0
votes
1answer
32 views

Let $f(t)$ be a polynomial. When $\sum_{k=1}^n f(\sin{kx_0})$ is bounded for any $x_0$?

Let $x_0 > 0$, $f(t)$ be a polynomial. What is condition specified for $f(t)$ to sequence $(s_n)=\sum_{k=1}^n f(\sin{kx_0})$ be bounded? For example: if $f(t) = t$ then $|(s_n)|=|\sum_{k=1}^n \sin{...
1
vote
1answer
19 views

Upperbound of tail event

Let $X_n\sim \mathcal{E}(n)$ I need to show that $P (\{X_2 + \ldots + X_n \geq 3 \log{n} \text{ infinitely often}\}) = 0$. I also have the following hint: with $n \geq 2 \text{ and } 0 \leq x \leq \...
0
votes
0answers
18 views

Bounds on the a posteriori error covariance of Kalman filter

I am looking to derive a lower bound for the a posteriori error covarinace ($\bar{\Sigma}$) in discrete-time Kalman filter (in steady state). The bounds on the a priori error covariance ($\Sigma$) ...
1
vote
0answers
33 views

Tight Bound via Chebychev Inequality

I am trying to compute a tight bound on a tail event. Let $(X_n, n \geq 1), (Y_n, n \geq 1)$ be two independent sequences of i.i.d.$\sim\mathcal{N}(0,1)$ random variables, and let $Z_n =\sum_{j=1}^n ...
3
votes
1answer
73 views

Bounds of double factorial

I am looking for bounds on the double factorial for even and odd $n \in \mathbb{N}$, defined as $$ n!! = n \cdot (n-2) \cdot (n-4) \dots $$ For example, $9!! = 9 \cdot 7 \cdot 5 \cdot 3 \cdot 1$ ...