$n$ points going for a random walk on $\mathbb{Z}$ with condition

64 Views Asked by At

$n$ points start at $0,$ where $n$ is some positive even integer.

Each "round", $\frac{n}{2}\ $ points take one step forward; the remaining $\frac{n}{2}\ $ points take one step backwards.

It is completely random which points move forward each round (they can be thought of as being "chosen at random").

What is the expected number of rounds until one of the points reaches the number $10$?

I guess for $n=2$ this reduces to the problem: "a point goes on a random walk on $\mathbb{Z},\ $ starting at $0.$ What is the expected number of steps until it reaches either $-10$ or $10$?" which is "easier" than the main question, although I don't know the answer to this either. But clearly the question gets even more difficult for $n\geq 4.$

I ran a Python script and found that for $n=4,\ $ Exp $\ \sim 54;\ $ for $n=6,\ $ Exp $\ \sim 41.$ Here is my code for $n=6.$

import random 
resultsList=[]
for j in range(100):
    selectedThisRound, not_seletedThisRound = -1, -1
    iters=0
    #define or reset the n_k
    n_0,n_1,n_2,n_3,n_4,n_5=0,0,0,0,0,0
    #define or reset WalkStatus
    walkStatus=[0,0,0,0,0,0]
    while n_0 != 10 and n_1 != 10 and n_2 != 10 and n_3 != 10 and n_4 != 10 and n_5 != 10:
        walkStatus=[n_0,n_1,n_2,n_3,n_4,n_5]
        print("walkStatus= ",walkStatus)
        iters +=1 
        if iters > 1000:
            print("too many loops")
            break    
        list1 = [0,1,2,3,4,5]
        not_seletedThisRound=-1
        for i in range(6):
            if i<=2:
                selectedThisRound = list1.pop(random.randint(0,5-i))
                m=1    
            else:#if i>=3
                not_seletedThisRound = list1.pop()
                m=-1
            if selectedThisRound==0 or not_seletedThisRound==0:
                n_0+=m
            elif selectedThisRound==1 or not_seletedThisRound==1:
                n_1+=m
            elif selectedThisRound==2 or not_seletedThisRound==2:
                n_2+=m
            elif selectedThisRound==3 or not_seletedThisRound==3:
                n_3+=m
            elif selectedThisRound==4 or not_seletedThisRound==4:
                n_4+=m
            elif selectedThisRound==5 or not_seletedThisRound==5:
                n_5+=m
            else:
                print("removal error")
                break
            if i==2:
                #reset a variable
                selectedThisRound = -1
        if list1 != []:
            print("error: list not empty. iters =", iters)
            break
    print("iters=",iters)    
    resultsList.append(iters)

print("resultsList=", resultsList)
print("average value for 100 simulations = ", sum(resultsList)/100)

No doubt it's pretty bad because I haven't coded in ages so don't judge me, but I believe it works. And I think you have to change the code for each $n$, because in python there wasn't an automatic way of introducing new variables, but I'm sure there's a better way to write the code than I have where you can automate this...