Bernoulli Trials with Small Dependencies – Asymptotics

brownian motionpr.probabilityprobability distributionsrandom walksstochastic-processes

Let $\{X_k\}$ be a sequence of random variables, with $X_k\in\{+1, -1\}$ for $k>0$, generated as follows.
First, define $S_n=X_1+\dots +X_n$, with $X_0=S_0=0$, and let $0<\beta<\frac{1}{2}$.

Then, if $|S_n|<n^\beta$, let
$P[X_{n+1}=1]= P[X_{n+1}=-1]=\frac{1}{2}$. Otherwise:

  • If $S_n> n^\beta$, then $P[X_{n+1}=1]= \frac{1}{2}-\epsilon,
    P[X_{n+1}=-1]=\frac{1}{2}+\epsilon$
  • If $S_n< -n^\beta$, then $P[X_{n+1}=1]= \frac{1}{2}+\epsilon,
    P[X_{n+1}=-1]=\frac{1}{2}-\epsilon$

Here $0\leq\epsilon<\frac{1}{2}$. If $\epsilon=0$, then regardless of $\beta$, this is your typical iid Bernouilli trials. I am interested in the asymptotics related to this sequence, when $\epsilon>0$ and $\beta<\frac{1}{2}$. In particular do we have a result, a modified version of the central limit theorem, that would state something like this: $S/n^\gamma$ is normally distributed (asymptotically) with finite variance $>0$. Or something else? I have no idea what $\gamma$ might be, I am curious to know.

The goal, in the end, is to produce random sequences that are random enough to fool all known tests of randomness, yet not truly random. Or to put it in other words, to benchmark tests of randomness for pseudo-random number generators. Clearly, my sequence violates the law of the iterated logarithm, and was designed for that very purpose.

Note that $S_n$, when properly rescaled, gives rise to a sequence that behaves like a Brownian motion, but is obviously non-Brownian since its variance is an order of magnitude smaller than that of a Brownian motion (my guess).

Update

A related type of sequence is investigated by Drezner & Farnum (1993). See more recent version here. I was unable to have my sequence fit in that framework, I don't think it does.

That said, let $p_n(m)=P(S_n=m)$, with $-n\leq m \leq n$. Also, let $S_0=0$ and $p_0(0)=1$. Then $p_n(m)$ can be recursively computed using some modified version of the Pascal triangle recursion:
$$
p_{n+1}(m)=\Big[\frac{1}{2}+\epsilon \cdot A_n(m-1)\Big]p_n(m-1)+\Big[\frac{1}{2}-\epsilon\cdot A_n(m+1)\Big]p_n(m+1),
$$
with
$$
A_n(m)=\chi(m<-n^\beta)-\chi(m>n^\beta).
$$
Here $\chi$ is the indicator function. It should be easy to prove that
$\text{E}[S_n]=0$ due to symmetry. Also, when $\epsilon=0.05$ and $\beta=0.45$ I get the almost perfect fit
$\sqrt{\text{Var}[S_n]}\approx 1.39 \cdot n^{0.35}$. Below is the Python code, just in case there's a typo in my formula (the Python code is correct).

import random
import math

random.seed(1) 

epsilon=0.05 
beta=0.45 
Prob={}
Prob[(0,0)]=1
nMax=2001

def psi(n,m):
  p=0.0
  if m>n**beta:
    p=-1
  if m<-n**beta:
    p=1
  return(p)

OUT=open("rndproba.txt","w")
for n in range(1,nMax):
  Exp=0
  Var=0
  for m in range(-n,n+1,2):
    if m+1>n:
      Prob[(n-1,m+1)]=0
    if m-1<-n:
      Prob[(n-1,m-1)]=0
    Prob[(n,m)]=(0.5+epsilon*psi(n-1,m-1))*Prob[(n-1,m-1)]+(0.5-epsilon*psi(n-1,m+1))*Prob[(n-1,m+1)]
    Exp=Exp+m*Prob[(n,m)]
    Var=Var+m*m*Prob[(n,m)]
  Var=Var**0.5
  line=str(n)+"\t"+str(beta)+"\t"+str(epsilon)+"\t"+str(Exp)+"\t"+str(Var)+"\n"
  print("**",n,Exp,Var)
  OUT.write(line)   
OUT.close()

Formula for the variance

Taking advantages of symmetries, we have for $n\geq 0$:

$$
\text{Var}[S_{n+1}]=\text{Var}[S_n]+1-\delta_n, \quad \text{with }\delta_n=8\epsilon\cdot \sum_{m>n^\beta} m \cdot p_n(m).
$$
The sum for $\delta_n$ is finite since $p_n(m)=0$ if $m>n$. This is an exact formula. Of course,
$\text{Var}[S_0]=0$. Also, if $\epsilon=0$, the sequence is perfectly random and $\delta_n=0$

Best Answer

For $0<\beta \le 1/2$, any limiting distribution of the rescaled process $S_n/n^\beta$ will be fully supported in $[-1,1]$, so it will not be normal.

The downward drift will imply (using Hoeffding's inequality and a union bound over the largest $m<n$ such that $S_m<m^\beta$) that $P(S_n>n^\beta+k) \le Ce^{-c_\epsilon k}$.

I expect that for $ 0<\beta < 1/2$, the limiting distribution of process $S_n/n^\beta$ will be uniform in $[-1,1]$, while for $\beta=1/2$, it will be a truncated normal distribution, i.e., it will have the normal density restricted to $[-1,1]$ and normalized to have integral 1.

Related Question