1
$\begingroup$

Consider a sequence $(X_i)_{i = 1}^{\infty}$ which every $X_i$ is $-1$, $0$ or $+1$ and lets define $Y_n = X_1+ \cdots + X_n$. We say the sequence $(X_i)_{i = 1}^{\infty}$ a Good Sequence if $Y_n \neq O( n^{\frac{1}{2} } )$ but for every positive real $\epsilon$, $Y_n = O( n^{\frac{1}{2} + \epsilon} )$.

My question:

  • Do you know a good sequence which can be described with an explicit formula?

Notes:

  • It's not so hard to create a good sequence but I mean, that I want one of them which can be described with an explicit formula (algebraic formula or ... ).

  • A candidate is the Möbius function. But the proof of that which $(\mu(n))_{n = 1}^{\infty}$ is good is equivalent with Riemann-hypothesis.

  • Almost surely every random walk (of usual ones) is a good sequence.

  • (This note added after the first comment which solved the problem and I found which there are some solutions which are different from that which is in my mind and in this comment I've tried to draw the thing which I want a solution to be that) Mainly, I want a deterministic and explicitly described walk which is like random walks, and in other terms I want a deterministic and explicitly described walk which its graph is like the graph of random walks (The below image is from Wikipedia.org).

enter image description here

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Would you consider $X_n=\lfloor\sqrt{n+1}\ln(n+1)\rfloor-\lfloor \sqrt{n}\ln n\rceil$ (perhaps for $n>100$...) to be good enough? Or you need $Y_n$ also to oscillate? $\endgroup$
    – Ilya Bogdanov
    Commented Sep 16, 2015 at 19:24
  • $\begingroup$ Thanks, You've answered my stated question; But the thing which I had in my mind was a walk in which $Y_n$ oscillates like a random walk. Do you have any idea for this case? $\endgroup$
    – Mohammad Ghiasi
    Commented Sep 16, 2015 at 19:34
  • $\begingroup$ Well, one may also multiply $\sqrt n\ln n$ by $\sin(\root3\of n$... I assume this is also not what was needed? After that, one may also add something which looks more randomly, but whose sums are much smaller, if you wish. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 16, 2015 at 20:19
  • 3
    $\begingroup$ So, the real question is: May you tell ALL properties of random walks you wish to preserve? Otherwise it may long forever. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 16, 2015 at 20:20
  • $\begingroup$ How about $X_n = \left( \lfloor 3^n \sqrt{2} \rfloor \bmod 3 \right) - 1$? $\endgroup$
    – Qiaochu Yuan
    Commented Sep 16, 2015 at 20:37

1 Answer 1

Reset to default
1
$\begingroup$

While I cannot prove anything, I strongly suspect that the fractional part of $e^i$ massaged to the right values has the properties you want. In other words:

$$X_i = \left\lfloor 3\left(e^i-\lfloor e^i \rfloor\right)\right\rfloor-1$$

Of course, there really no reason to use $e$ here, you could use $\pi$ or any other properly "random" number.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .