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?

Improve this question
$\endgroup$
5
  • $\begingroup$ It is hard to answer without any context… $\endgroup$
    – Nathaniel
    Commented 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$
    – Jean Abou Samra
    Commented Mar 18 at 23:25
  • $\begingroup$ @JeanAbouSamra You should post it as an answer. $\endgroup$
    – Nathaniel
    Commented Mar 19 at 8:57
  • $\begingroup$ @JeanAbouSamra but here we only have 1 variable n $\endgroup$
    – L. breitman
    Commented Mar 19 at 10:42
  • 2
    $\begingroup$ @L.breitman Actually, there is also the variable $p$. $\endgroup$
    – Nathaniel
    Commented Mar 19 at 12:22

2 Answers 2

Reset to default
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)$$

Improve this answer
$\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 ♦
    Commented Mar 20 at 14:01
  • $\begingroup$ Thanks for the answer! $\endgroup$
    – L. breitman
    Commented 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$
Improve this answer
$\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
    Commented Mar 20 at 12:27
  • 1
    $\begingroup$ You are right. I corrected the answer. $\endgroup$
    – Subhankar Ghosal
    Commented 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.