4
$\begingroup$

I'm trying to read the following article, and in the abstract they write: Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M_n(\xi)$ denote a $n\times n$ random matrix with entries that are independent copies of $\xi$. For $\xi$ which is not uniform on its support, we show that: $Pr[M_n(\xi) \text{ is singular}] = Pr[\text{zero row or column}]+ (1+o_n(1))Pr[\text{two equal (up to sign) rows or columns}]$.

What does $o_n(1)$ mean here?

$\endgroup$
5
  • $\begingroup$ It is hard to answer without any context… $\endgroup$
    – Nathaniel
    Mar 18 at 21:32
  • 5
    $\begingroup$ My guess is that they mean $o(1)$ in the normal sense (Landau notation), but since they are working with several variables, they add $n$ as subscript to mean "as $n$ goes to infinity". $\endgroup$ Mar 18 at 23:25
  • $\begingroup$ @JeanAbouSamra You should post it as an answer. $\endgroup$
    – Nathaniel
    Mar 19 at 8:57
  • $\begingroup$ @JeanAbouSamra but here we only have 1 variable n $\endgroup$ Mar 19 at 10:42
  • 2
    $\begingroup$ @L.breitman Actually, there is also the variable $p$. $\endgroup$
    – Nathaniel
    Mar 19 at 12:22

2 Answers 2

3
$\begingroup$

As I understand it, this $o_n(1)$ is meant as the standard “little o” notation (when $v_n$ takes non-zero values, $u_n = o(v_n)$ means $\frac{u_n}{v_n} → 0$), except that because several variables are involved ($n$, $ξ$, $p$), they added the $n$ subscript to clarify that the limit is as $n$ goes to infinity, for fixed values of the other variables. A perhaps more standard notation for what they write as $$x = o_n(y)$$ would be $$x \underset{n→+∞}{=} o(y)$$

$\endgroup$
2
  • 2
    $\begingroup$ This is consistent with the definition of $O_\alpha, \Omega_\alpha, \Theta_\alpha$ in the "Notation" section of the paper, although strangely they omit defining $o_\alpha$. $\endgroup$
    – Discrete lizard
    Mar 20 at 14:01
  • $\begingroup$ Thanks for the answer! $\endgroup$ Mar 21 at 14:15
0
$\begingroup$

Given functions $f(n)$ and $G(n)$, from $[0,\infty)\rightarrow [0,\infty) $ we can define

Operands Meaning
$f(n) = O_n(G(n))$ $\displaystyle \lim_{n\rightarrow \infty} \inf \frac{G(n)}{f(n)} > 0$
$f(n) = o_n(G(n))$ $\displaystyle \lim_{n\rightarrow \infty} \frac{G(n)}{f(n)} = 0$
$f(n) = \Theta_n(G(n))$ $f(n) = O(G(n)) \;\&\; G(n) = O(f(n))$
$f(n) \sim_{n} G(n)$ $\displaystyle \lim_{n\rightarrow \infty} \frac{G(n)}{f(n)} = 1$
$\endgroup$
2
  • 3
    $\begingroup$ The first one is incorrect. E.g. $1 + \sin(n) = O(1)$ but $\lim 1/(1 + \sin(n))$ does not exist. You can replace the limit by $\lim\inf$. $\endgroup$
    – Neal Young
    Mar 20 at 12:27
  • 1
    $\begingroup$ You are right. I corrected the answer. $\endgroup$ Mar 28 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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