3
$\begingroup$

If we know

$$ E(Z_i) = H_i + H_{n - i + 1} - 2 $$

and $i \sim \sqrt n$.

Can we write:

\begin{align*} E(Z_i) & = H_i + H_{n-i+1} - 2 \\ & \sim \log i + \log (n-i+1) \\ & \sim \log \sqrt n + \log n \\ & \sim \frac 3 2 \log n \end{align*}

$H_n$ is Harmonic number.

(The original question is "How does $E(Z_i)$ vary when $i \sim \sqrt n$")

  • 0
    What does $\sim$ mean for you? A standard convention is that $f(n) \sim g(n)$ iff $f(n)/g(n) = 1 + o(1)$. Under *that* convention, this is correct.2011-09-17
  • 0
    My book doesn't specify the definition of $\sim$, so I guess it's defined in the conventional way. But can we derive the result from the definition of $\sim$?2011-09-17
  • 0
    The trouble is: "the conventional way" differs from one branch of mathematics to another. So (unless you know what it is in THIS branch) you should ask.2011-09-17
  • 0
    I agree with @GEdgar in that this is used in multiple senses (and one should be careful while consulting a paper or book). That's why even my answer starts with "One fairly standard...". I *guess* that this question/doubt must have figured in some combinatorics/discrete math/algorithms context, and my answer implicitly assumes that. I will make this explicit in the beginning of my answer.2011-09-17
  • 0
    So note: you are using $f(n) \sim g(n)$ implies $\log f(n) \sim \log g(n)$, which is OK when they go to infinity. But some similar things don't work. $f(n) \sim g(n)$ need not imply $e^{f(n)} \sim e^{g(n)}$, for example.2011-09-17
  • 0
    @GEdgar I am not sure if that comment is for me for the OP :-). If it is for me, I am actually not using that first fact *explicitly*. I kind of derived it on the way.2011-09-17
  • 0
    @GEdgar Actually, another similar thing to watch out for. $f_1 \sim g_1$ and $f_2 \sim g_2$ does not imply $f_1 - f_2 \sim g_1 - g_2$.2011-09-17
  • 0
    Also note: if $f(n)$ and $g(n)$ both approach $1$, then $f(n) \sim g(n)$ but the "consequence" $\log f(n) \sim \log g(n)$ could well fail.2011-09-17
  • 0
    Oh, this is more complicate than I thought. I'm studying probabilistic analysis of algorithm.2011-09-17

1 Answers 1

1

Added: As GEdgar points out in a comment, what the symbol $\sim$ means depends a lot on the branch of mathematics. From the overall question, I am guessing that the branch in this case is either combinatorics or discrete mathematics or algorithms. I think my definition below agrees with popular usage of $\sim$ in these areas. See this page for further details.


One fairly standard convention is that for nonnegative eventually positive1 functions $f(n)$ and $g(n)$ $$ f(n) \sim g(n) \stackrel{\text{def}}{\iff} \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 \iff \frac{f(n)}{g(n)} = 1 + o(1) \iff f(n) = g(n) + o(g(n)), $$ where "def" means that we are defining $\sim$ this way.

1Added: I made the functions eventually positive. If $g(n)$ is zero infinitely often, then the limit does not exist. This is not the most general way to define asymptotic notation, but I find the restriction convenient.

I first state a basic fact about this asymptotic notation: if $f_1(n) \sim g_1(n)$ and $f_2(n) \sim g_2(n)$, then
$$ f_1(n) + f_2(n) = g_1(n) + o(g_1(n))+ g_2(n) + o(g_2(n)) = g_1(n)+g_2(n) + o(g_1(n) + g_2(n)), $$ so that $f_1(n) + f_2(n) \sim g_1(n) + g_2(n)$.


Coming to your question, we need the additional two facts:

  1. If $n$ is large, then $H_n \sim \log n$, which comes the estimate $$ H_n = \log n + \gamma + O(1/n) = \log n + O(1) = \log n + o(\log n). $$
  2. If $i \sim \sqrt{n}$, then $$ \log i = \log \sqrt{n} + \log \left(\frac{i}{\sqrt{n}} \right) = \log \sqrt{n} + \log (1+o(1)) = \log \sqrt{n} + o(1); $$ $$ \log(n-i+1) = \log n + \log \left( 1 - \frac{i-1}{n} \right) = \log n + \log (1 - o(1)) = \log n + o(1). $$ Hence certainly $\log i = (1 + o(1)) \log \sqrt{n}$ and $\log (n-i+1) = (1+ o(1)) \log n$.

Applying the above facts, you can see that the above asymptotic analysis is sound.

  • 0
    In your definition you say "nonnegative" but I would require that $g$ is eventually positive.2011-09-17
  • 0
    @GEdgar Yes, thanks for the catch. I will make the functions positive, at least eventually.2011-09-17