6
$\begingroup$

This is a question I thought of recently: (Based on some set of initial conditions, i.e. initial positions and movement probabilities , and the current time and positions) When and Where will 2 Random Walks Meet for the First Time? Is there a joint probability function?

I found the following questions that discuss related topics, but not something that directly relates to this question :

As an example, consider the following two Random Walks (Here, $X(t)$ represents the position of the first Random Walk at time $t$ and $Y(t)$ represents the position of the second Random Walk at time $t$. $S_x(t)$ and $S_y(t)$ represent the random movement, i.e. outcomes at each point $t$):

$$ X(t) = \begin{cases} x_0 & \text{if } t = 0 \\ X(t-1) + S_x(t) & \text{if } t > 0 \end{cases} $$

$$ Y(t) = \begin{cases} y_0 & \text{if } t = 0 \\ Y(t-1) + S_y(t) & \text{if } t > 0 \end{cases} $$

$$ x_0, y_0, X(t), Y(t) \in \mathbb{Z} \quad \forall t $$

$$ S_x(t) = \begin{cases} +1 & \text{with probability } p= p_1 \\ -1 & \text{with probability } p= 1- p_1 \end{cases} $$

$$ S_y(t) = \begin{cases} +1 & \text{with probability } p= p_2 \\ -1 & \text{with probability } p= 1- p_2 \end{cases} $$

Thus, is it possible to derive a probability distribution capable of describing the distribution for the "number of steps" (time) and "position" where these two Random Walks will intersect based on their initial conditions and current conditions? Can a joint probability distribution function be written?

I have watched videos (e.g. https://www.youtube.com/watch?v=iH2kATv49rc) where they explain that a Random Walk in 1 Dimension (like my question) and 2 Dimensions is guaranteed to visit each possible point (however, this is not true for Random Walks in more than 2 Dimensions). Thus, I would informally conclude that since both Random Walks can occupy any point in the same domain (i.e. set of all integers), it is reasonable to believe that their intersection is theoretically possible. However, just because they have the ability to occupy and point in the same domain, I am not sure that this theoretically guarantees their intersection.

For example, suppose both Random Walks start very far from each other, and one of them has higher probability to move left and the other has higher probability move right. In this situation, it seems logical to believe that it will take more time and more steps for these two Random Walks to intersect ... compared to a situation where these two Random Walks started at positions closer to each other and had higher probabilities of moving in the same direction.

I also understand that conditional on the current positions of both Random Walks, some intersection times are not possible. For example, if both Random Walks are currently situated very far from each other, an intersection will not be possible in the next time point (a certain minimum amount of time is logically required). I think this will affect the "Support" of these intersection distributions.

I tried to run multiple simulations in R corresponding to this situation (note: if a given simulation takes more than 100,000 turns, I terminate the simulation. I record the time taken as 100,000 on the time graph, but I don't record the position on the position graph).

library(data.table)
library(ggplot2)
library(gridExtra)

x0 <- -2
y0 <- 2

meeting_times <- integer()
meeting_positions <- integer()

for (i in 1:1000) {
    X <- x0
    Y <- y0
    
    t <- 0
    
    while (X != Y && t < 100000) {
        step_X <- sample(c(-1, 1), 1)
        step_Y <- sample(c(-1, 1), 1)
        
    
        X <- X + step_X
        Y <- Y + step_Y
        
        
        t <- t + 1
    }
    

    if (t >= 100000) {
        t <- 100000
    } else {
     
        meeting_positions <- c(meeting_positions, X)
    }
    
 
    meeting_times <- c(meeting_times, t)
}

df_times <- data.table(time = meeting_times)

p1 <- ggplot(df_times, aes(x = time)) +
    geom_density(fill = "black", color = "black") +
    ggtitle(paste("Distribution of Time Needed for Random Walks to Meet\nAverage Time =", round(mean(meeting_times), 2),
                  "\nAverage Time =", mean(meeting_times),
                  "\nNumber of Simulations = 1000",
                  "\nStarting Points: X0 =", x0, ", Y0 =", y0,
                  "\nProbabilities: P(X step) = 0.5, P(Y step) = 0.5")) +
    theme_bw()


df_positions <- data.table(position = meeting_positions)

p2 <- ggplot(df_positions, aes(x = position)) +
    geom_density(fill = "black", color = "black") +
    ggtitle(paste("Distribution of Meeting Positions for Random Walks\nAverage Position =", round(mean(meeting_positions), 2),
                  "\nNumber of Simulations = 1000",
                  "\nStarting Points: X0 =", x0, ", Y0 =", y0,
                  "\nProbabilities: P(X step) = 0.5, P(Y step) = 0.5")) +
    theme_bw()

The outputs of the simulation look like this:

enter image description here

And just as an example, I showed an example of the trajectory taken by a given simulation until the intersection occurs:

x0 <- -2
y0 <- 2

path_X <- integer()
path_Y <- integer()

X <- x0
Y <- y0

t <- 0

while (X != Y && t < 100000) {

    step_X <- sample(c(-1, 1), 1)
    step_Y <- sample(c(-1, 1), 1)
    
    X <- X + step_X
    Y <- Y + step_Y
    

    path_X <- c(path_X, X)
    path_Y <- c(path_Y, Y)
    

    t <- t + 1
}


df_paths <- data.frame(time = 1:length(path_X), X = path_X, Y = path_Y)

ggplot(df_paths, aes(x = time)) +
    geom_line(aes(y = X, color = "red")) +
    geom_line(aes(y = Y, color = "blue")) +
    scale_color_manual(values = c("red" = "red", "blue" = "blue")) +
    labs(color = "Random Walk", x = "Time", y = "Position") +
    ggtitle("Paths of Two Random Walks") +
    theme_bw()

enter image description here

And here is the same plot for 1000 simulations:

x0 <- -2
y0 <- 2


df_paths <- data.frame()


for (i in 1:1000) {
    path_X <- integer()
    path_Y <- integer()
    print(i)
   
    X <- x0
    Y <- y0
    
    
    t <- 0
    

    while (X != Y && t < 100000) {
       
        step_X <- sample(c(-1, 1), 1)
        step_Y <- sample(c(-1, 1), 1)
        
        
        X <- X + step_X
        Y <- Y + step_Y
        
       
        path_X <- c(path_X, X)
        path_Y <- c(path_Y, Y)
        
        t <- t + 1
    }
    

    df_paths_i <- data.frame(time = 1:length(path_X), X = path_X, Y = path_Y, simulation = rep(i, length(path_X)))
    
  
    df_paths <- rbind(df_paths, df_paths_i)
}

ggplot(df_paths, aes(x = time)) +
    geom_line(aes(y = X, color = "red"), alpha = 0.1) +
    geom_line(aes(y = Y, color = "blue"), alpha = 0.1) +
    scale_color_manual(values = c("red" = "red", "blue" = "blue")) +
    labs(color = "Random Walk", x = "Time", y = "Position") +
    ggtitle("Paths of Two Random Walks for 100 Simulations") +
    theme_bw()

enter image description here

But going back to my question: Based on some set of initial conditions $x_0$, $y_0$ $p_1$ and $p_2$ and their current positions, is it possible to derive probability distributions which describe the number of steps and the time required for intersection? Can a Joint Probability Distribution Function be derived?

$$ G : P(T=t | x_0, y_0, p_1, p_2, T-1 = t-1) \sim ??? $$ $$ H: P(X(t) = Y(t) | x_0, y_0, p_1, p_2, X(t-1) = x(t-1), Y(t-1) = y(t-1) ) \sim ??? $$

$$ \text{Joint Probability Distribution Function of Intersection Time and Intersection Position: } P(G,H) \sim ??? $$ Thanks!

Note: In the above distributions

  • $T=t$ is a random variable representing the intersection time
  • $X(t-1) = x(t-1)$ and $Y(t-1) = y(t-1)$ are random variables representing the position of both Random Walks at the most recent time
$\endgroup$
6
  • 2
    $\begingroup$ Normally, I would criticize your posting for including computer code, since MathSE reviewers don't normally inspect/critique code. Further, it wouldn't be that difficult for you to replace all computer code in your simulation with pseudocode, where you give a logical description of each code excerpt. However, because your posting is so thorough, my main reaction to your posting is +1; I upvoted. $\endgroup$ Commented Apr 20 at 16:48
  • 6
    $\begingroup$ Note that $Z_t := X_t - Y_t$ is yet another random walk, with a different step distribution. You start $Z_t$ at $x_0 - y_0$, and are asking if and when it will hit $0$. The techniques you looked at in the videos that you mentioned should be applicable to this. $\endgroup$ Commented Apr 20 at 16:51
  • 1
    $\begingroup$ If they have the same probabilities of moving left or right as each other then the expected time until they meet or pass each other is infinite. $\endgroup$
    – Henry
    Commented Apr 20 at 17:39
  • $\begingroup$ @user2661923: thank you for your feedback! I like to make my questions reproducible so that people in the future can read my questions and walk through them step by step $\endgroup$
    – stats_noob
    Commented Apr 21 at 2:27
  • $\begingroup$ @ stochasticboy321: thank for your reply! if you have time, can you please show me how to write an answer for this? $\endgroup$
    – stats_noob
    Commented Apr 21 at 2:28

0

You must log in to answer this question.

Browse other questions tagged .