0
$\begingroup$

There are N cars that are parked in N parking spots numbered from 1 to N. After the Nth parking spot, there are N more parking spots numbered from N+1 to 2N. At each step, a car is selected randomly and if the parking spot just ahead of it is empty, then it will move to the next parking spot with probability 1/2. What is the expected number of steps till all cars occupy the spots N+1 to 2N?

I tried using markov chains to solve this. Each state in the chain will be represented as (i,N-i), where i is the number of cars in the parking spots from 1 to N and n-i are the cars in the spots N+1 to 2N. State (0,N) will be the absorbing state. Using this I tried finding the expected number of steps to reach (0,N) from (N,0).

Improve this question
$\endgroup$
8
  • $\begingroup$ If you are looking for a purely mathematical approach, you may consider posting this on Maths.SE. Although it is not off-topic here. I expect 4*N^2 < E(nb_steps) < 2*N^3. $\endgroup$
    – Evargalo
    Commented Sep 8, 2023 at 13:45
  • 5
    $\begingroup$ Where is this problem from? $\endgroup$
    – ACB
    Commented Sep 8, 2023 at 13:46
  • $\begingroup$ From the description it sounds like a car in slot $i$ moves to slot $i+1$, but from your state space it sounds like a car in slot $i$ moves to slot $i+N$. In the latter interpretation, does "a car is selected randomly" mean from among all $N$ cars or just the ones that haven't yet moved? $\endgroup$
    – RobPratt
    Commented Sep 8, 2023 at 14:44
  • $\begingroup$ The state space is such that the state changes when a car moves from the Nth spot to the N+1th spot and also, any car can be selected from all the N cars $\endgroup$
    – 12HackingEarth
    Commented Sep 9, 2023 at 12:27
  • $\begingroup$ The states are such that each state (i,N-i) can transition to the state (i-1,n-i+1) or can remain in the same state. What i assumed, taking your example, the state(0,1,1,0) can transition to the state(0,0,1,1) only when the state's configuration changes to (0,1,0,1). This will be handled by transitioning to the same state. $\endgroup$
    – 12HackingEarth
    Commented Sep 9, 2023 at 12:42

2 Answers 2

Reset to default
3
$\begingroup$

Here are the first $10$ values, obtained via a Markov chain with $\binom{2N}{N}$ states, one for each placement of $N$ cars in $2N$ spots: \begin{matrix} N & \text{expected number} \\ \hline 1 & 2 \\ 2 & 14 \\ 3 & 39.125 \\ 4 & 78.178269319 \\ 5 & 131.55549073 \\ 6 & 199.50383036 \\ 7 & 282.19557982 \\ 8 & 379.75904678 \\ 9 & 492.29418149 \\ 10 & 619.88144334 \\ \end{matrix}

Improve this answer
$\endgroup$
2
  • $\begingroup$ I get the same values. $\endgroup$
    – loopy walt
    Commented Sep 9, 2023 at 15:39
  • $\begingroup$ I get the same with my simulation. $\endgroup$
    – Bob Bixler
    Commented Sep 10, 2023 at 14:13
1
$\begingroup$

Partial Answer - Simulation

Welcome to this site @12HackingEarth.

Those assumptions are made in the simulation (If I understood correctly your challenge):

  • Any car can be selected, independently of its position.
  • If a car that cannot move to their right is selected (ie. last slot, or adjacent slot occupied), a step is counted, but the state does not change.

The runnable code is here.

It computes expected values and standard deviation from N = 1 to 100 over 300 simulation for each N.

Here is an output of the simulation as csv you can play around.

First 10 values:

N,ExpectedValue,Standard Deviation
1, 2.07, 1.52
2, 14.3, 6.45
3, 39.58, 12.58
4, 78.98, 19.71
5, 130.85, 26.66
6, 200.25, 39.85
7, 280.22, 48.6
8, 379.94, 60.09
9, 493.68, 59.42
10, 615.67, 76.79

Improve this answer
$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.