Questions tagged [upper-lower-bounds]

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

Definitions

Given a function $f$ with domain $D$ and a partially ordered set $(K, \le)$ as codomain, an element $y \in K$ is an upper bound of $f$ if $f(x) \le y$ for each $x \in D$. The upper bound is called sharp if equality holds for at least one value of $x \in D$.

Function $g$ defined on domain $D$ and having the same codomain $(K, \le)$ is an upper bound of $f$ if $f(x) \le g(x)$ for each $x \in D$.

Function $g$ is further said to be an upper bound of a set of functions if it is an upper bound of each function in that set.

The notion of lower bound for (sets of) functions is defined analogously, with $\ge$ replacing $\le$.

An upper bound is said to be a tight upper bound, a least upper bound, or a supremum if no smaller value is an upper bound. Similarly, a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum if no greater value is a lower bound.

Source: Wikipedia

Examples

  1. For a random variable $X$ and $a > 0$: $$\Bbb{P}(X \ge a) \le \dfrac{\Bbb{E}(X)}{a}$$

    This inequality is called Markov's inequality and provides an upper bound for the probability that the value of $X$ exceeds $a$.

  2. For any real $x \ge 0 $: $$1 - e^{-x} \le x$$ So $x$ is an upper bound for $1-e^{-x}$, and vise versa, $1-e^{-x}$ is a lower bound in $[0; +\infty)$.

2313 questions
1
vote
2 answers

Question regarding big O notation.

Let $z\in \mathbb{C}$. I want to show that $\frac{1}{z+n}+\frac{1}{z-n}=O(\frac{1}{n^2})$. By definition, I need to show that for some constant $M$ and $N$, we have $\mid\frac{1}{z+n}+\frac{1}{z-n}\mid=\mid\frac{2z}{z^2-n^2}\mid\leq \frac{M}{n^2}$…
able20
  • 1,023
1
vote
2 answers

Upper bound for the sum of the nth powers of a digit

I am doing Project Euler # $30$. I currently want to find all the numbers that can be written as the sum of fifth powers of their digits. I solved this using a generic upper bound of a million. However, this isn't very precise and so I want to find…
1
vote
2 answers

Prove that $f: [0, \infty) \to \mathbb{R}$ given by $f(x) = \frac{1+2^x+x^3}{4+5e^x}$ is bounded.

Prove that $f: [0, \infty) \to \mathbb{R}$ given by $f(x) = \frac{1+2^x+x^3}{4+5e^x}$ is bounded. Is it enough to just prove that the limit is $0$ as x approaches infinity? I'm thinking not but don't know how to approach the problem.
kt046172
  • 545
1
vote
1 answer

How to prove that the number of ways that set[n] can be partitioned into disjoint non-empty subsets for even integers is between (n/2)^(n/2) and n^n

For any integer n ≥ 1, let r(n) denote the number of different ways that the set [n] := {1, . . . , n} can be partitioned into disjoint non-empty subsets, the union of which is the entire set [n]. I need to first find r(3) and list all the ways it…
1
vote
2 answers

Bound for Expression

Let $x,y\in\mathbb{R^n}$ and $K>0$ prove that $$ \frac{2K||x-y||_2^2}{ (1+K||x||_2^2)(1+K||y||_2^2) } <2 $$ What I've achieved so far is: $$ =\frac{8K||x||_2^2}{(1+K||y||_2^2)^2} $$ I've tried several things like doing a case-distinction on $K$,…
ndrizza
  • 1,348
1
vote
3 answers

Finding bounds of the set: $ A = \{ \frac{m\cdot n}{m+n}: m,n \in \mathbb N \} $

I'm having some problems with this. I know that lower bound will be $\dfrac{1}{2}$. Should I just find $m,n$ for which $\dfrac{m\cdot n}{m+n} \lt \dfrac{1}{2} + \epsilon $? Also I'm not sure how to prove that it's the best possible lower…
1
vote
1 answer

Upper and lower bound for fraction function : $ \sum_{n=0}^{N-1}(-1)^n\binom{N-1}{n}\frac{1}{(n+1)*cx} $

Let $c$ and $N$ be two positive real number with $c>0$, and $x$ very high number. The number $c$ have two cases $c<1$ and $c\geq 1$. if ther is any upper bound and lower bound for the following…
Mokhtar
  • 99
1
vote
1 answer

Prove that $\underline\int_{a}^bf\ge0$ when $f(x)\ge 0$

My question is: Suppose that the bounded function $f:[a,b]\rightarrow \Bbb R$ has the property $f(x)\ge 0$ for all $x$ in $[a,b]$. Prove that $\underline\int_{a}^bf\ge0$. I am just confused on where to start. I would think you have to use the…
1
vote
1 answer

Reproducible rounding up with hidden constant and known maximum deviation

I am running a system with an unknown constant X and a known boundary B over several iterations. N is the value I get, which is X + (0...B). Here is an example of several runs of this system where B = 5: N = 10 N = 13 N = 12 N = 14 N = 12 N =…
1
vote
1 answer

Upper/lower bounds for an unusual function

How can I obtain some good upper/lower bounds on the function $$ f(k)= \frac{-p}{\log_2{\left( 1-2^{-k} \right)}}$$ for $0
1
vote
2 answers

Are GCSE upper bounds correct?

Is the upper bound of 10 to 1sf really 15, or is it 14.98 recurring? If so, am I being taught incorrect information? For example if a box can take 70g (accurate to 1sf), what is the maximum number of exact 1.5g masses could I place into it? I have…
0
votes
0 answers

Why is the upper bound of the maximum product of spacings function $-\log(n+1)$?

Maximum product of spacings estimation involves maximizing this function: $$ S_n(\theta) = \frac1{n+1}\sum_{i=1}^{n+1} \log D_i(\theta),\quad D_i(\theta) = F(x_{(i)};\theta) - F(x_{(i-1)};\theta) $$ Here, $F(x;\theta)\in[0,1]$ is a cumulative…
ForceBru
  • 101
0
votes
0 answers

Upper bound of the difference between two weighted sum

For $a_i \in \mathbb{R}$ and $X_i, Y_i \in \mathbb{R}^+$, Is there any upper bound of the difference between two weighted sums, which looks like below? $ \sum_i a_i X_i - \sum_i a_i Y_i <= |\sum_i X_i - \sum_i Y_i| * const $ the const may be any…
0
votes
0 answers

Monotonic $C_\infty$ bounds on the sinc function

The sinc function ($\sin(x)/x$ with a value of $1$ at $x=0$) is bound between $-1/x$ and $1/x$, but these are not the tightest bounds at any point, in fact, it is quite clear that there are even other monotonic functions that would be more tight.…
Lucas
  • 1,469
0
votes
0 answers

The set S is also bounded above by y/x, so it has a least upper bound α in the real numbers.

Given x = 2 and y = 5, let S be the set of all integers k such that 2k ≤ 5, i.e., S = {0, 1, 2}. Then the upper bound of S is y/x = 5/2, i.e., for any number greater than or equal to 5/2, it is greater than or equal to any element of S. Also, the…