I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values).

Suppose that the two variables can have different distributions with values chosen from $[1, n]$. But $X$ is always upper bounded by $Y \cdot c\log{n}$ for some constant $c$. Can I write this as $X = O(Y\log{n})$ (if I care about the behavior for large $n$). I'm not sure what is the convention wrt to random variables and asymptotic notation.

  • $\begingroup$ "$X$ is always upper bounded by $Y⋅\log n$." You write that as $X\le Y\log n$. What is the problem with that? Do you have a different relation between $X$ and $Y$? $\endgroup$ – John L. Jul 7 '19 at 8:05
  • $\begingroup$ sorry, I forgot to add the constant for the upper bound. There exists a constant $c$ for large $n$ such that the bound holds, so I want to write this in asymptotic notation. $\endgroup$ – user1246462 Jul 7 '19 at 15:00

On first look, the notation $X = O(Y\,\log{n})$ seems intuitively reasonable since $X$ is always upper bounded by $c (Y\,\log n)$ for some constant $c$. ($c$ must be positive since $X,Y\ge1$).

Can we formalize the exact meaning of that notation?

Here is one natural definition.

Let $(\Omega,S,T)$ represents a set of 2-dimensional random vectors on $\Omega$ parameterized by $n$, i.e., for all $n$, $(S_n, T_n)$ is a random vector from $\Omega_n$ (which is a set of possible outcomes) to ${\Bbb R}^2$. We write

$$S=O(T){\text{ as }}n\to \infty $$ if and only if there is a positive constant $c$ such that for all sufficiently large values of $n$, for all $\omega\in\Omega_n$, the absolute value of $S_n(w)$ is at most $c\,T_n(w)$.

We can apply the above definition to $(I, X, Y\,\log n)$ where $I_n=[1,n]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.