# Discrete Random Walk

Consider a discrete random walk.

Let $X_t = X_{t+1} + \epsilon_t$, with $p(\epsilon_t = 1) = 0.5$ and $p(\epsilon_t = -1) = 0.5$ be the stepwise random walk. Each possible arrival point $(t,X_{t})$ of the random walk is reached through a unique number of upsteps and downsteps, but the sequence of upsteps and downsteps does not matter, so that there may be many different paths. Since up-steps and down-steps are equally likely, the probability of any path of length $t$, corresponding to a specific sequence of innovations $\{\epsilon_t\}$, is $p(\{\epsilon_t\}) = \frac{1}{2^t}$. The point $(t,X_t)$ can be expressed in terms of the number of upsteps ($y$) and downsteps ($x$) (which amounts to a $45\deg$ coordinate rotation). 

\begin{equation}
X_t = y-x\\
t = y+x
\end{equation}

From which follows:
\begin{equation}
x = \frac{t-X_t}{2}\\
y = \frac{t+X_t}{2}
\end{equation}

The total amount of paths that lead from $(0,0)$ to $(t,X_t)$ are given by all possible sequences of $x$ downsteps and $y$ upsteps. 

\begin{equation}
n(t,X_t) = \left(\begin{array}{c}x+y\\x\end{array}\right) = \left(\begin{array}{c}x+y\\y\end{array}\right) =  \left(\begin{array}{c}t\\\frac{t+X_t}{2}\end{array}\right) = \left(\begin{array}{c}t\\\frac{t-X_t}{2}\end{array}\right)
\end{equation}

If $\frac{t\pm X_t}{2}$ are integer and 0 otherwise. 

Given that $X_t = \sum^t_i \epsilon_t$, the probability $p(X_t = s)$ is:

\begin{equation}
p(X_t = s) = \sum^t_{\{\epsilon_t\}}\prod^t_ip(\epsilon_i)
\end{equation}

Where the sum is over all sequences of $\{\epsilon_t\}$ so that $\sum^t_i \epsilon_t = s$, and it follows:

\begin{equation}
p(s) = \left(\begin{array}{c}t\\\frac{t-X_t}{2} \end{array}\right)\frac{1}{2^t}
\end{equation}


```python
import numpy as np
from numpy import random as rnd
import matplotlib.pyplot as plt

def random_walk(t):
    """
    returns a single random walk
    """
    return np.cumsum([0]+[rnd.choice([-1,1]) for i in range(t)])
    
    

def factorial(x):
    if x == 0:
        return 1
    else:
        res = 1
        for i in range(1,x+1):
            res *= i
        return int(res)
    
def binomial(n,k):
    if k >= 0 and n >= 0 and k <= n:
        return int(factorial(n)/(factorial(n-k)*factorial(k)))
    else:
        return 0


def p_s(s,t):

    """
    Probability of a path reaching t,s
    """
    
    x = (t - s)/2
    
    if x % 1 != 0:
        return 0
    else:
        return binomial(int(t),int(x))/(2**t)
    
    
tt = [int(10*i) for i in range(11)]
ss = [int(i) for i in range(-int(max(tt)/1.5),int(max(tt)/1.5)+1)]


plt.figure(figsize=(12,8))
for t in tt:
    
    ps = [p_s(s,t) for s in ss]
    
    plt.plot(ss,ps,'.-',alpha=0.7)
    
plt.legend(['t=%i' % i for i in tt])
plt.title("p(X_t=s)")
```


```python
for t in [50]:
    X_t = []
    for i in range(2000):
        walk = random_walk(50)
        X_t += [walk[-1]]


    bins = [i for i in range(-int(t/1.5),int(t/1.5))]
    plt.hist(X_t,density=True,bins=bins,align='left')
    ps = [p_s(s,t) for s in bins]
    plt.plot(bins,ps,'.',markersize=15)

    plt.legend(['simulated','analytical'])
```

# Counting Paths - Imbalanced Dyck Paths

As an example for calculating the probability of a certain type of path, I will look into the probability that a point $X_t,t$ is reached by a path that never dips below 0. This is similar to looking at Dyck Words, in that they are sequences where there are always at least as many "+1" steps as there are "-1" steps. Dyck Words are normally balanced, in that they contain the same number of "+1" and "-1", meaning that they correspond to paths that return to 0 without ever going negative. The number of Dyck paths with length 2n is given by the Catalan number $C_n$, so in that case the answer is known. Instead I will look at what I'll call "Imbalanced Dyck Paths", which are paths that never dip below zero but don't necessarily return to 0 at their end point. 

Below is a plot of a few random walks, with those who qualify as Imbalanced Dyck Paths shown in red:


```python
def is_dyck(walk):
    """
    check whether the walk is an imbalanced dyck path, i.e. it never goes below the horizon
    """
    if any(walk < 0):
        return False
    else:
        return True
    
    
color_code = {True: 'red', False: 'royalblue'}

plt.figure(figsize=(16,8))

total = 0
dyck_words = 0
for i in range(1000):
    walk = random_walk(1000)
    
    cc = False
    total += 1
    if is_dyck(walk):
        dyck_words += 1
        cc = True
        
    plt.plot(walk,color = color_code[cc],alpha=0.2)
    
plt.title('%i paths, %i above horizon (%1.1f%%)' % (total,dyck_words,100*dyck_words/total))
```

In the ``Counting Paths - Catalan Numbers and Dyck Words`` notebook, I came up with the formula:

\begin{equation}
f(x,y) = \sum^y_{k=x}f(x-1,k)\\
\forall x>0,\ y\geq x
\end{equation}

With boundary condition:

\begin{equation}
f(y,0) = 1\\ \forall y\geq 0
\end{equation}

To describe the amount of imbalanced Dyke paths that reach a certain point $x$,$y$. (Proper Dyke Paths of length 2n correspond to $f(n,n)$). Here I exchanged x and y as compared to the other notebook, because in this problem I calculated so that $y\geq x$ and not the other way around.

Given the number of paths, and considering all paths in this example have probability $\frac{1}{2^t}$, the probability distribution for Dyck paths can be found as:

\begin{equation}
p_D(x,y) = \frac{1}{2^{x+y}}f(x,y) = \frac{1}{2^{x+y}}\sum^y_{k=x}f(x-1,k) = \frac{1}{2^{y-x+1}}\sum_{n=0}^{y-x}p_D(x-1,x+n)
\end{equation}

Changing variables:
\begin{equation}
p_D(X_t=s) = p_D(s,t) = \frac{1}{2^{s+1}}\sum_{n=0}^s 2^n 
p_D(s'=n+1,t'=t-(s+1)+n)
\end{equation}
for $t>s>0$, 
\begin{equation}
p_D(s,s) = \frac{1}{2^t} \\
\forall s\leq t\\
\end{equation}
whenever $s=t$, and

\begin{equation}
p_D(s,t) = 0\\
\forall s > t,\ \forall s < 0,\ \forall t < 0
\end{equation}

for the remaining cases.


```python
class Dyke_Path(object):
    """
    Class to calculate Dyke Path probabilities with Memoization. (Much faster) 
    """
    
    def __init__(self):
        
        self.archive = {}
        
        pass 

    def proba(self,s,t):
        """
        Probability of a point s,t being reached with a Dyck Path
        """
        
        if (s,t) in self.archive:
            return self.archive[(s,t)]
        
        elif s > t:
            return 0
        elif t < 0:
            return 0
        elif s < 0:
            return 0

        elif s == t:
            return 1/(2**s)
        else:
            
            p = 1/2**(s+1) * np.sum([2**n * self.proba(n+1,t-(s+1)+n) for n in range(s+1)])
            self.archive[(s,t)] = p
            
            return p
    

PD = Dyke_Path()

t_max = 22
tt = list(range(t_max))
ss = list(range(-2,t_max))[::-1]

P = np.zeros([len(ss),len(tt)])

for i in range(len(ss)):
    for j in range(len(tt)):
        P[i,j] = PD.proba(ss[i],tt[j])
        

print("Dyck Path Probabilities (log2, rounded)")
f = lambda s: str(int(int(1*np.log2(s))/1)).zfill(4) if s > 0 else ' -  '        
for p,s in zip(P,ss):
    print('s=%i\t' % s,s,t_max*'%s  ' % tuple([f(i) for i in p]))
plt.figure(figsize=(12,8))


P[P == 0] = np.nan
plt.imshow(np.log2(P))
plt.colorbar()
```

### Probability of an Imbalanced Dyck Paths surviving until time T

There's probably a closed form solution, but I will just clumsily integrate the recursion equation I derived above. 


```python
N = 1000
t_max = 50

dyck_prob_sim = []
dyck_prob = []
for t in range(t_max+1):
    d_count = 0
    for i in range(N):
        walk = random_walk(t)
        if is_dyck(walk):
            d_count += 1
            
    dyck_prob_sim += [d_count/N]
    
    d_prob = 0
    for s in range(t+1):
        d_prob += PD.proba(s,t)
        
    dyck_prob += [d_prob] 
       

plt.figure(figsize=(12,8))
plt.plot(dyck_prob,'d-')
plt.plot(dyck_prob_sim,'o-')
plt.title('Probability of a Dyck Path')
plt.legend(['analytical','simulated'])
```

d3c1101eb68237d56c3bf1af9d156e778f9cc6bc
ipynb
Jupyter Notebook
Combinatorics - Counting Paths, Discrete Random Walk.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Combinatorics - Counting Paths, Discrete Random Walk.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Combinatorics - Counting Paths, Discrete Random Walk.ipynb
jpbm/probabilism
a2f5c1595aed616236b2b889195604f365175899
MIT
Qwen/Qwen-72B
1. YES
2. YES