Skip to main content
added 1408 characters in body
Source Link
Will Sawin
  • 148.7k
  • 9
  • 324
  • 563

For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ then this implies $X_m > g(n) (1-\epsilon) \geq g(2^{k+1} ) (1-\epsilon)$ for all $m \leq 2^k $ for infinitely many $k$. This is an event with probability $\approx e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ and it can only occur with positive probability for infinitely many $k$ if the sum of these probabilities $\sum_{k=1}^\infty e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ is positive (this direction of Borel-Cantelli not requiring independence).

So $\limsup Y_n/g(n)\geq 1$ with probability $0$ for $g(n) = C \log \log n/n$ as soon as $C>2$.

 

I suspect for some lesser value ofLet $C$ one can prove$A_n$ be the event that $\limsup Y_n/ (C \log \log n/n) \geq 1$ with probability$Y_{2^n} \geq C (\log n)/2^n$. Then $1$$\mathbb P(A_n) \approx n^{-C}$. For $n<m$, for example by the second moment methodintersection $A_n \cap A_m$ occurs when $X_k \geq C ( \log n)/2^n$ for $k\leq 2^n$ and $X_k \geq C (\log m)/2^m$ for $2^m < k \leq 2^n$ which has probability $$\approx e^{ - C ( \log n + \frac{2^m-2^n}{2^m} \log m )} = e^{ C 2^{n-m} \log m} e^{ - C \log n} e^{-C \log m}. $$

This is $(1+o(1) ) n^{-C} m^{-C}$ as long as $m-n > \log N$, isince $e^{ C 2^{ -\log_2 N } \log m } \leq e^{ C 2^{-\log N} \log N} = 1+o(1)$.e When $m$ is close to $n$, this probability is still bounded by $e^{- C\log n}$. This gives

$$\sum_{m,n \leq N} \mathbb P(A_n \cap A_m) \leq (1+o(1))\sum_{n,m\leq N} n^{-C} m^{-C} + \sum_{\substack{ n,m \leq N \\ |n-m| \leq \log \log N}}e^{ - C \log n} \approx (1+o(1)) ((1-C) N^{1-C})^2 + 2 (1-C) N^{1-C} \log N = (1+o(1)) ((1-C) N^{1-C})^2 $$ as long as $C<1$.

Now $\sum_{n=1}^N \mathbb P(A_n) \approx N^{1-C} / (1-C)$.

So the ratio$$ \frac{ (\sum_{n=1}^N \mathbb P(A_n) )^2}{ \sum_{m,n \leq N} \mathbb P(A_n \cap A_m) }$$ converges to $1$. By Kochen-Stone lemma, this implies that $A_n$ occurs infinitely often with probability $1$.

In other words, $\limsup Y_n / (\log \log n/n) \geq 1$ with probability $1$.


So $\limsup Y_n / (\log \log n/n) \in [1,2]$ with probability $1$. We cannot change the limsup by changing finitely many values of $X_n$ to something nonzero and so by Kolmogorov's zero-one law, there is a fixed deterministic value in $[1,2]$ that the limsup approaches. I am not sure if this is possible to compute.

For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ then this implies $X_m > g(n) (1-\epsilon) \geq g(2^{k+1} ) (1-\epsilon)$ for all $m \leq 2^k $ for infinitely many $k$. This is an event with probability $\approx e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ and it can only occur with positive probability for infinitely many $k$ if the sum of these probabilities $\sum_{k=1}^\infty e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ is positive (this direction of Borel-Cantelli not requiring independence).

So $\limsup Y_n/g(n)\geq 1$ with probability $0$ for $g(n) = C \log \log n/n$ as soon as $C>2$.

I suspect for some lesser value of $C$ one can prove that $\limsup Y_n/ (C \log \log n/n) \geq 1$ with probability $1$, for example by the second moment method, i.e. the Kochen-Stone lemma.

For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ then this implies $X_m > g(n) (1-\epsilon) \geq g(2^{k+1} ) (1-\epsilon)$ for all $m \leq 2^k $ for infinitely many $k$. This is an event with probability $\approx e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ and it can only occur with positive probability for infinitely many $k$ if the sum of these probabilities $\sum_{k=1}^\infty e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ is positive (this direction of Borel-Cantelli not requiring independence).

So $\limsup Y_n/g(n)\geq 1$ with probability $0$ for $g(n) = C \log \log n/n$ as soon as $C>2$.

 

Let $A_n$ be the event that $Y_{2^n} \geq C (\log n)/2^n$. Then $\mathbb P(A_n) \approx n^{-C}$. For $n<m$, the intersection $A_n \cap A_m$ occurs when $X_k \geq C ( \log n)/2^n$ for $k\leq 2^n$ and $X_k \geq C (\log m)/2^m$ for $2^m < k \leq 2^n$ which has probability $$\approx e^{ - C ( \log n + \frac{2^m-2^n}{2^m} \log m )} = e^{ C 2^{n-m} \log m} e^{ - C \log n} e^{-C \log m}. $$

This is $(1+o(1) ) n^{-C} m^{-C}$ as long as $m-n > \log N$, since $e^{ C 2^{ -\log_2 N } \log m } \leq e^{ C 2^{-\log N} \log N} = 1+o(1)$. When $m$ is close to $n$, this probability is still bounded by $e^{- C\log n}$. This gives

$$\sum_{m,n \leq N} \mathbb P(A_n \cap A_m) \leq (1+o(1))\sum_{n,m\leq N} n^{-C} m^{-C} + \sum_{\substack{ n,m \leq N \\ |n-m| \leq \log \log N}}e^{ - C \log n} \approx (1+o(1)) ((1-C) N^{1-C})^2 + 2 (1-C) N^{1-C} \log N = (1+o(1)) ((1-C) N^{1-C})^2 $$ as long as $C<1$.

Now $\sum_{n=1}^N \mathbb P(A_n) \approx N^{1-C} / (1-C)$.

So the ratio$$ \frac{ (\sum_{n=1}^N \mathbb P(A_n) )^2}{ \sum_{m,n \leq N} \mathbb P(A_n \cap A_m) }$$ converges to $1$. By Kochen-Stone, this implies that $A_n$ occurs infinitely often with probability $1$.

In other words, $\limsup Y_n / (\log \log n/n) \geq 1$ with probability $1$.


So $\limsup Y_n / (\log \log n/n) \in [1,2]$ with probability $1$. We cannot change the limsup by changing finitely many values of $X_n$ to something nonzero and so by Kolmogorov's zero-one law, there is a fixed deterministic value in $[1,2]$ that the limsup approaches. I am not sure if this is possible to compute.

deleted 899 characters in body
Source Link
Will Sawin
  • 148.7k
  • 9
  • 324
  • 563

For $g(n)$ a decreasing function, we have $\liminf Y_n/g(n) \leq 1$ if and only if $Y_n < g(n) (1+\epsilon)$ infinitely often for all $\epsilon$, which happens if and only if $X_n < g(n) (1+\epsilon)$ infinitely often for all $\epsilon$. This is because if $X_n$ satisfies that inequality then clearly $Y_n$ does, while if $Y_n$ satisfies the inequality then $X_m$ $X_m/ g(m) \leq X_m/g(n) = Y_n/g(n)$ for some $m \leq n$ but each $m$ can only satisfy $X_m=Y_n$ for finitely many $n$.

By Borel-Cantelli this happens if and only if $\sum_{n=1}^\infty g(n) $ is infinite.

In particular, if this is true for $g(n)$ then it is true for $\epsilon g(n)$ for all $\epsilon>0$, i.e. if the lim inf is ever $\leq 1$ then it is $0$.

So there is no analogue of the law of the iterated logarithm here, at least not for the lim inf - there is no one best sequence to divide the lim inf by.


For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ then this implies $X_m > g(n) (1-\epsilon) \geq g(2^{k+1} ) (1-\epsilon)$ for all $m \leq 2^k $ for infinitely many $k$. This is an event with probability $\approx e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ and it can only occur with positive probability for infinitely many $k$ if the sum of these probabilities $\sum_{k=1}^\infty e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ is positive (this direction of Borel-Cantelli not requiring independence).

So $\limsup Y_n/g(n)\geq 1$ with probability $0$ for $g(n) = C \log \log n/n$ as soon as $C>2$.

I suspect for some lesser value of $C$ one can prove that $\limsup Y_n/ (C \log \log n/n) \geq 1$ with probability $1$, for example by the second moment method, i.e. the Kochen-Stone lemma.

For $g(n)$ a decreasing function, we have $\liminf Y_n/g(n) \leq 1$ if and only if $Y_n < g(n) (1+\epsilon)$ infinitely often for all $\epsilon$, which happens if and only if $X_n < g(n) (1+\epsilon)$ infinitely often for all $\epsilon$. This is because if $X_n$ satisfies that inequality then clearly $Y_n$ does, while if $Y_n$ satisfies the inequality then $X_m$ $X_m/ g(m) \leq X_m/g(n) = Y_n/g(n)$ for some $m \leq n$ but each $m$ can only satisfy $X_m=Y_n$ for finitely many $n$.

By Borel-Cantelli this happens if and only if $\sum_{n=1}^\infty g(n) $ is infinite.

In particular, if this is true for $g(n)$ then it is true for $\epsilon g(n)$ for all $\epsilon>0$, i.e. if the lim inf is ever $\leq 1$ then it is $0$.

So there is no analogue of the law of the iterated logarithm here, at least not for the lim inf - there is no one best sequence to divide the lim inf by.


For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ then this implies $X_m > g(n) (1-\epsilon) \geq g(2^{k+1} ) (1-\epsilon)$ for all $m \leq 2^k $ for infinitely many $k$. This is an event with probability $\approx e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ and it can only occur with positive probability for infinitely many $k$ if the sum of these probabilities $\sum_{k=1}^\infty e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ is positive (this direction of Borel-Cantelli not requiring independence).

So $\limsup Y_n/g(n)\geq 1$ with probability $0$ for $g(n) = C \log \log n/n$ as soon as $C>2$.

I suspect for some lesser value of $C$ one can prove that $\limsup Y_n/ (C \log \log n/n) \geq 1$ with probability $1$, for example by the second moment method, i.e. the Kochen-Stone lemma.

For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ then this implies $X_m > g(n) (1-\epsilon) \geq g(2^{k+1} ) (1-\epsilon)$ for all $m \leq 2^k $ for infinitely many $k$. This is an event with probability $\approx e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ and it can only occur with positive probability for infinitely many $k$ if the sum of these probabilities $\sum_{k=1}^\infty e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ is positive (this direction of Borel-Cantelli not requiring independence).

So $\limsup Y_n/g(n)\geq 1$ with probability $0$ for $g(n) = C \log \log n/n$ as soon as $C>2$.

I suspect for some lesser value of $C$ one can prove that $\limsup Y_n/ (C \log \log n/n) \geq 1$ with probability $1$, for example by the second moment method, i.e. the Kochen-Stone lemma.

Source Link
Will Sawin
  • 148.7k
  • 9
  • 324
  • 563

For $g(n)$ a decreasing function, we have $\liminf Y_n/g(n) \leq 1$ if and only if $Y_n < g(n) (1+\epsilon)$ infinitely often for all $\epsilon$, which happens if and only if $X_n < g(n) (1+\epsilon)$ infinitely often for all $\epsilon$. This is because if $X_n$ satisfies that inequality then clearly $Y_n$ does, while if $Y_n$ satisfies the inequality then $X_m$ $X_m/ g(m) \leq X_m/g(n) = Y_n/g(n)$ for some $m \leq n$ but each $m$ can only satisfy $X_m=Y_n$ for finitely many $n$.

By Borel-Cantelli this happens if and only if $\sum_{n=1}^\infty g(n) $ is infinite.

In particular, if this is true for $g(n)$ then it is true for $\epsilon g(n)$ for all $\epsilon>0$, i.e. if the lim inf is ever $\leq 1$ then it is $0$.

So there is no analogue of the law of the iterated logarithm here, at least not for the lim inf - there is no one best sequence to divide the lim inf by.


For $g(n)$ a decreasing function, we have $\limsup Y_n/g(n)\geq 1$ if and only if $Y_n> g(n)(1-\epsilon)$ infinitely often. Based on an approach suggested by Aleksei Kulikov, if $n \in [2^k, 2^{k+1}]$ then this implies $X_m > g(n) (1-\epsilon) \geq g(2^{k+1} ) (1-\epsilon)$ for all $m \leq 2^k $ for infinitely many $k$. This is an event with probability $\approx e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ and it can only occur with positive probability for infinitely many $k$ if the sum of these probabilities $\sum_{k=1}^\infty e^{ - 2^k g(2^{k+1} ) (1-\epsilon)}$ is positive (this direction of Borel-Cantelli not requiring independence).

So $\limsup Y_n/g(n)\geq 1$ with probability $0$ for $g(n) = C \log \log n/n$ as soon as $C>2$.

I suspect for some lesser value of $C$ one can prove that $\limsup Y_n/ (C \log \log n/n) \geq 1$ with probability $1$, for example by the second moment method, i.e. the Kochen-Stone lemma.