1

$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...

Adam Rubinson
  • 20,052
  • Basically each point is performing an "almost" independent random walk. It is not a perfect one, because the sum is always exactly zero, however, for a large n this correlation is negligible, so you may solve by asking what the probability of at least one out of n rw reach the threshold. – user619894 Mar 10 '21 at 21:52
  • Please can you explain why each point is performing an almost random walk? I don’t see why this should be the case. – Adam Rubinson Mar 11 '21 at 09:15
  • suppose you had $n=10000$, the correlation between any 2 walkers would be $O(1/10000)$, so the probablility of walker $a$ to reach the target is practically independent of the probability of walker $b$ to reach the target. – user619894 Mar 11 '21 at 09:29
  • I am not convinced, but probably it's due to my lack of knowledge on the maths behind random walks. But that's partly the reason I ask this question: because I want to gain that knowledge. I think this is an example of what I shouldn't do: post a question when I doubt I will be able to comprehend the answer any time soon. – Adam Rubinson Mar 11 '21 at 11:26
  • I will try and flesh out a more convincing approach (I believe that an exact solution is possible as well). – user619894 Mar 11 '21 at 11:42

0 Answers0