Expected time for $N$ cars to move $N$ spaces without overtaking

Question

I was asked this problem at an interview, I had no clue of how to solve it, can someone help?

Suppose that we have $N$ cars parked in a line occupying spaces $1$ to $N$. Spaces $N+1$ to $2N$ are empty. Every minute, a car is considered eligible to move forward one space if:

a) the space in front of them (space $i+1$) is empty, and

b) its space number, $i$, is less than $2N$.

Suppose that every minute, if a car is eligible to move, then it has a $1/2$ chance of moving forward by one space. What is the expected number of minutes before the cars occupy squares $N+1$ to $2N$?

Answer 1

The problem is more complicated than I thought in the first place. All I could manage is to produce this picture (every column is one configuration of parking, black dots are the cars, white spots are empty lots, there are N=20 cars).

It is quite clear, that $N-1$ is the minimum number of parking configurations one has to go through. However, allowing the advancement of a car only with probability $p=1/2$ implies that the first car, which is never blocked by another car, arrives parking spot $2N$ after a negative binomial time (parameters N and 1/2). That gives an average $2N$ for the time until the first car hits parking slot $2N$.

For the other cars it is more complicated. They block each other sometimes. The simulation shows how that slows down the other cars.

Searching on a famous search engine, i could find only similar problems that are called "parking functions". There are a number of papers on that topic, beginning from the 60s, but is not the same setup as here. But maybe there are some references somewhere in there.

I cannot imagine this to be an interview question. Either there is a trivial answer that I do not see. Or, it is an open problem and the interviewer wanted to see your reaction on non-trivial, hard problems. Sorry, I cannot provide any answers. But the simulation shows at least, that $N^2/2$ is not the answer (for the simulation above, i got 180.9 as an average after 20 runs).

Either way, it is an interesting question!

Answer 2

Ran a simulation for cars ranging from $1\ldots M$, doing 10 runs per number of cars. These are the results I got (see pics). I've also attached the source code in case my way of simulating is wrong.

It looks like it's almost perfectly linear as a function of M (haven't tested really large values yet)

EV parking from $N$ in $1$ to $100$, $10$ per $N$:

src code 1

src code 2

EDIT: I realized I forgot to remove the upper bound of $1000$ on the minutes. Haven't updated the pictures but for those who want to run the script, just remove that as a condition checked in the while loop

EDIT 2: src code as text as requested:

import random
import time
import sys
import matplotlib.pyplot as plt
import numpy as np

# check whether all of the cars
# are in their required positions
def match_positions(pos):
    N = len(los)//2
    M = len(pos)
    for i in range(N, M):
        if pos[i] == 0:
            return False

    return True

def run(N):
    minutes = 0

    # this represents the
    # occupied positions
    # pos[i] = 1 --> ith car park space is filled

    pos = []
    # represents the positions
    # of ith car
    car_pos = []
    for i in range(N):
        pos.append(1)
        car_pos.append(i)
    for _ in range(N):
        pos.append(0)

    can_move = [0]*N

    while not match_positions(pos):
        for i in range(N):
            # simulate by a coin toss with whether
            # or not the ith car can move
            # that is, if can_move[i] = 1 then ith car
            # tries to move 1 step up
            can_move[i] = random.randint(0, 1)

        for i in range(N):
            if can_move[i] == 1:
                prev_pos = car_pos[i]

                inc = prev_pos + 1
                # if ith car can move and it's not blocked up ahead
                # it moves up 1 step from its previous pos 
                if inc < 2*N and pos[inc] != 1:
                    # incremented car park position gets occupied. previous is 0
                    pos[inc] = 1
                    pos[prev_pos] = 0

        minutes += 1 # increment time-step

    return minutes

if __name__ == "__main__":

    # repeat experiment for 1..N cars
    N = int(input("Enter the range of N: "))
    # for k cars, run experiment M times
    M = int(input("Enter M: "))
    averages = []
    for k in range(1, N+1):
        times = []
        for _ in range(M):
            times.append(run(k))
        mean = sum(times)/len(times)
        averages.append(mean)


    plt.plot(averages)
    plt.show()

    # sample correlation coeff against the number of cars
    n_cars = [ k for k in range(1, N+1) ]
    coeff = np.corrcoeff(n_cars, averages)[0, 1]
    print(coeff)

As a follow-on, using the linearity of expectation I get $O(N)$ behaviour. Can anyone confirm this?