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
0
votes
0 answers

Understanding upper and lower bounds

The following website explains that an upper bound of the interval $[0, 1, 2, 3, 4, 5, 6]$ are numbers $1, 2, 3, 4, 5, 6$. I though an upper bound was a number that is greater or equal to every number in that set so $6,7,8$ etc. Is the website…
0
votes
1 answer

Greatest lower bound

All I have to do is show from definition that $A$ must have at most one greatest lower bound if $A$ is a subset of $\mathbb{R}$ and is not empty. My thoughts are if $A$ is not bounded below, then it has no lower bound so no greatest lower bound by…
0
votes
2 answers

lower bound and upper bound of expression ($1-\frac{1}{n})^{\log n}$

Let's say that $f(n)=\bigl(\frac{n-1}{n}\bigr)^{\log n}$ ( I know bounds of $\bigl(\frac{n-1}{n}\bigr)^{n}$ ). Is there any way I can get good upper bound of $f(n)$ when n is positive? Thanks in advance
manifold
  • 1,485
0
votes
2 answers

Is $2^n + n < 2^{(n+1)}$?

Is $ 2^n + n < 2^{(n+1)}$ when $ n > 2 $ How can I prove this? I need it in order to prove a language is context free
Flama
  • 111
0
votes
1 answer

Proposition to be easily understood

I try to understand a proposition on this. I restate the proposition below : Is there other way to prove this proposition to be easily understood ? or is there another example for this proposition ?
0
votes
1 answer

Specifying an Upper Bound for a Monotonically Increasing Sequence

I would like to specify an upper bound of a sequence where $a_1=\sqrt2$ and each subsequent term is given by $a_{n}=\sqrt{2+ a_{n-1}}$ I know this sequence converges to 2 from a separate proof and also that it is monotonically increasing (one can…
EDS
  • 592
0
votes
1 answer

Maximum of minimum Hamming distance between $2$ of $N$ unique binary strings of length $L$

So we have $L$ bits, which gives us a binary string of length $L$. We have $N$ of these, all different. If we take $2$ and the $XOR$ gate, then count the number of $1$'s, this is the Hamming distance. In other words, the number of bits that are…
EPICI
  • 355
0
votes
1 answer

Finding upper bound on x and y

I want to find upper bound on following i equality without calculator. $${x^2}{y^5} \gt {2^x}{5^y} $$ How can I get this done?
0
votes
1 answer

Finding the error interpolating function.

While looking at the video I've linked at the end of this question about the error formula for interpolating functions, I got confused at the following example $$if n=1, x_0 =a, x_1 =b , b>a $$ find an upper bound for the error. Recall $ e(x) =…
-1
votes
1 answer

upper bound on weighted sum

Consider the weighted sum $S = \sum\limits_{i=1}^N p_i f(x_i), $ where $p_i \in [0, 1]$ and $f(x_i) \geq 0$. Also $f(x_i)$ is concave in $x_i$. I am wondering if $\frac{\sum\limits_{i=1}^N p_i}{N} \sum\limits_{i=1}^N f(x_i)$ is a upper bound on $S$.
one user
  • 534
-1
votes
1 answer

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" and the upper limitation as "The smallest union while…
P. Scotty
  • 115
-2
votes
1 answer

$\frac 1 {1 + \epsilon} \le 1 - \frac \epsilon 2$ for $\epsilon \in (0, \frac 1 2)$

How can we show that the following holds for $\epsilon \in (0, \frac 1 2)$? $$ \frac 1 {1 + \epsilon} \le 1 - \frac \epsilon 2 $$ I thought, maybe it would be more convenient to try to show somehow that $\frac 1 {1 + \epsilon} + \frac \epsilon 2 \le…
1 2 3
4