What part of parking space is used, if cars park randomly?

Question

Cars park along a street. They do it randomly and uniformly in the space available, until parking becomes impossible. All the cars have the same length L.

How many cars are expected to park in a street of length N*L?
Assume that N is very large, and that a free space of length L is enough to park a car.

Cars park parallel to the street, and there is only one parking row. When a car parks, it occupies a space of length L. If N cars park tight to each other, they will occupy 100% of the street . If drivers have a non-cooperative attitude and park randomply, then some space will be waisted, because they will leave gaps G between cars of length 0
k*N, where 0

This is a tough problem. And I award everyone with a thumb for the effort.

Kaksi_Guy, this is a normal (although difficult) mathematical problem, not a puzzle. One needs to make idealized assumptions to make the problem tractable. Imagine that cars park along the curb, and they do not block the road. It is also assumed that cars are able to go in and out, even if there is a close to nil gap left with other parked cars.

I have a solution to this problem. I found it in the way, Ksoileau suggested. My answer looks cumbersome. I beleive it is correct, but I do not know the origin of this problem, and hence cannot compare it with the author's answer. Possibly, there is a shorter way and a more elegenat solution.

Jeredwn and Scythian1950 have reasonable arguments, but they are not applicable to this case. Duke's interpretation is correct. Randomly and uniformly means that we "drop" the coordinate of car's center on the line, until the car fits somewhere, without intersection with other cars. However, this does not mean that gaps between cars are distributed uniformly. The answer is not 2/3, neither 5/9 (Doctor D, I assume your answer 4/9 refers to gaps?). You can check it with Monte-Carlo.

Gentlemen, please, do not give thumbs down to each other.

Doctor D, how did you get 2/3 numerically? Did you use the assumption that coordinates of car centers are independent and uniformly distributed?
This is not correct. You need to model the whole parking process, like Duke described.

Duke, for clarification.
Each car continues trying to park until it fits. In your terms, we drop points on the line one by one. Distribution of x_i depends on distributions of x_j with j

*****************************************
Jeredwm, I can give an example of alternative qualitative approach. Suppose, that N/2 cars have parked, so that they have occupied half of all the space available. There are N/2+1 gaps between the cars. The total length of these gaps is N*L/2. The average gap length is L*(N/(N+2)), which is approximately L, since N is very large. We can expect that about half of the gaps are larger than L, and half of the gaps are smaller than L. The half of the larger gaps will be eventually occupied by cars. Then, we will have N/2 +(1/2)*N/2 = 3N/4 cars in total.
What do you think about this way of reasoning?

****************************************
Doctor D, the estimate which I give is 0.75N, not 0.84N. The only difference with your reasoning is that I consider the distribution of empty space after N/2 cars have parked, and not N like you do. Then I draw the median and assume that the number of gaps below the median is the same as the number of gaps above the median. Each gap above the median is enough for a car to park. This gives the estimate 3N/4=0.75N. By the way, 3N/4 is neither the correct answer, although it is quite close.

It's a misprint above: your reasoning refers not to the case where N cars have parked, but to the case where there is no more space available, which gives 2N/3. Try to apply the same reasoning after N/2 cars have parked, and you will get 3N/4.

In my example, it is assumed that mean and median are the same. I know that this is not correct. I also know what the answer should be. It is not 2N/3.

You can model the situation using recursion (see Ksoileau). Take a car of unit length and drop a car center on the street of length x = N. The car center should be randomly and uniformly distributed in the interval [0.5, x-0.5]. Suppose that the car center is dropped at point y. Then you get two substreets with lengths [0,y-0.5] and [y+0.5,x]. Drop a car center on each of two substreets. You will get four substreets. Continue dropping, until all the substreets have length less than 1. Count the resulting number of substreets M. Repeat this test from the beginning and find the average of M.

**********************************************

Genlemen, to give you some food for thought. Indeed, when your run a code you see a neat number 0.75. You start thinking about it, and come up with a convincing theory that the answer is exactly 3/4. Then you increase the accuracy of calculations, so that more digits are determined confidently, and ...

Ugly facts destroy the beautiful theory - the answer is not 3/4.

I reduced the answer to a reasonable form:

The number of cars f(x) with unit length, which can park on a street of length x, is described by the recursion:

f(x+1) = 1 +(2/x) ∫_{0}^{∞} f(y) dy.

Applying the Laplace transform, f(x) -> g(p), gives:

-exp(p) (d g/ dp + g) = 1/p^2 + 2g / p.

Since f -> k*x at x -> ∞, then g -> k/p^2 at p -> 0.
Solve equation, extract the asymptotic g -> k/p^2, and compactify the answer to get:

k = ∫_{0}^{∞} exp[ -2 (E_1 + γ + ln p) ] dp.

Here, γ = 0.57721566490... is the Euler constant, and E_1(p) = ∫_{p}^{∞} exp(-t) dt/ t is the exponential integral (E_1 is "expint" in MATLAB).

Numerical answer: k = 0.747597920...

Doctor D's numerical result is the most accurate - 4 correct digits. Remo Aviron got 3 digits right using a semi-quantitative approach.

Thank you, everyone, for fruitful discussion!

Answer 1

Here is how I would solve the problem:

Let the X be the number of Cars. Let the length of the Street be N*L -X*L = (N-X)*L (This is the length of street minus the cars)

Now let the cars be point size (no length). Distribute them randomly and uniformily over (N-X)*L.

**Note: The important thing is to forget about the length of the cars. It just mess up your thinking. So just make the street shorter and the cars points. Then it is easy to do a uniform random distribution of cars. If you ever want to go back to real life, you simply blow the cars back up to real size.

When the pobability is less then 1/X that any segment between two cars is greater then or equal to L, your problem is solved.

Simple, elegant. {Edit: And close, but not quite right}

I've modeled this out for some small numbers and it looks like the answer is X/N ~ 3/4. {Edit:} I ran several small trials and they were very much in accord with .75.

However, Zo Maar, I've seen your work and been impressed. You might be able to solve it directly from here. (I have too much to learn and relearn). ;-)

>>>>>>>>>>>>>>>>>>>>>>>>>>

12/11/07
Interesting. I ran a large trial of a my method out for a N=160,000 and I although there was a trend towards .75, there were a number of large open spaces that could fit more cars. I ended up manually filling some of these spots (using random methodolgy, similar to that advocated, above, by others), and this gave me a slightly greater than N/L= .75. A little troubling because I don't like the idea of manipulating data. Apparently, either my programing needs a tweak, or I need to add something to my idea.

>>>>>>>>>>>>>>>
Edit: Scythian1950

Before you get stuck on 2/3, try running the problem with some short segments such as 3L (my result, 1/3L) and 4L (my result, 7/18L). Or for that matter, simply sum the probablities of ultimate spacing if the first car is randomly placed anywhere between 0-2L behind the car in front (my result, 1/3L). When you plop a car down, you are just as likely to get this spacing between the car in front as you are to get <1L. And it is this segmentation problem that forces the packing to be <1/2L

>>>>>>>>>>>>>>>>>>>>>>

12/11/07 Part 2.

Alright, let's do the simple, and either right or right idea solution.

Assume that a car can land between 0-1 Length behind the car in front of it. Completely uniform and random. It can also land with equal probability 1-2 Lengths behind said car. For the first example, the average spacing will be .5 lengths. For the second example, another car will be added, and the spacing will vary between 0 -.5 Lengths, the average spacing will be .25 L AND there will be TWO such spacings.

This means the average spacing when a car lands between 0-2 lengths behind another car will be 1/3 length. Which implies a ratio of 3/4N. Problem solved. Now how do we extrapolate up? Can we assume that it does not matter how cars are placed until they get to within 2 lengths of another car? (The group was previously saying the we could extrapolate up from any placement within 1 length, so I'd be hesitant to say 1 is not OK, but 2 is OK).

Using the 0-2 L unit has some nice attributes. Not only does it get the solution correct, 1/3 spacing, but it should get the median right too. In other words, it has the same attributes of the overall answer.

>>>>>>>>>>>>>
Update 12/12/07

I agree with Zo Maar, the solution is not quite 3/4 (1/3rd spacing). But, I would not say its ugly, but instead "belle laide" meaning "beautiful-ugly"

The bottom line is although the solution trends to 3/4, it will never reach it. The small bits and pieces, such as lengths, 0-4L are average just a tad bit longer than 1/3L. This is because for these lengths the function asymetric.

(I've plotted these points out. The length function starts at zero, and rise linerally to 1L at 1, then drops to zero and rises linerally to 1/2 at 2, then it starts curving, droping to 1/3 at 2-1/3 and 13/48th at 2-1/2 before rising back to 1/3rd at 3 and continuing up. At 3L, the average spacing may be 1/3, but for the continuium from 0-3L, it is just a bit higher)

The solution for any random length 0-2 behind the car ahead of it is 1/3, exactly. However, the solution for any random length 2-3 is .34249. And the average for 0-3 is .33638, or alternatively, if you average .34249 with .33333, one gets .33791, or .74829 and .74743 N/L ratios respectively.

What is interesting is that these N/L ratios are in accord with the results Dr. D obtained. The implication is that it is not the big sections that are controlling, but the little sections, and they are what skew the average to just below .75 N/L ratio.

It is also true that the .75 N/L ratio is not accidental. At least over the section 0-3L, the function is exactly equal to 1/3 at 4 locations, which appear to be nodes: they are evenly spaced and the function passes through them. Specifically, 1/3, 1 (I know, it is a step function, and 1/3 is on the step), 1-2/3, 2-1/3 and 3.

In sum, since the larger problem, as you add cars, ultimately breaks down into a series of these smaller problems, the answer of 3/4 will never be reached, even at infinity, but it will be close.

>>>>>>>>>>>>>>>>>

Edit: Dr. D
[12/13/07, 1:00 pm pst]

We are thinking alike, read my above. But when you integrated from 2-3, you forgot that if you have 1 car, you will get 2 spaces, but if you have 2 cars, you will get 3 spaces. As stated above, I believe the correct number to be 0.34249. Your number is high because you did not account for this differential. ;-)

Answer 2

Consider the parking space after it has become impossible to park. I'll just take L = 1. There are n cars, where xi is the empty space before the ith car.
Clearly 0 ≤ xi < 1 for all i
The sum of all the empty spaces + filled space = N
i.e. n + ∑ xi = N ...(1)

Now, all the xi 's are independent EXCEPT the n+1 th, because ∑ xi must be an integer.
Each xi belongs to a continuous uniform distribution where
E(xi) = 1/2, Var(xi) = 1/12
Let X = sum of the first n xi's = (∑xi) - x_n+1 ...(2)

x_n+1 is the fraction necessary to round ∑ xi up to the nearest integer. Thus if there are n cars in the lot, then X may range from:
N-n-1 < X ≤ N-n

The possible values of n are:
(N+1)/2 < n ≤ N

E(X) = n/2, Var(X) = n/12
Since N is large, we can use a normal approximation for the distribution of X, i.e.
X ~ N(n/2, n/12)
So P(n) = prob that there are n cars in the lot
= P(N-n-1 < X ≤ N-n)

The expected value of n, E(n) = ∑ n*P(n)

To evaluate those probabilities, we may use the density function for the normal distribution:
f(X) = 1/σ√(2π) *exp[-(x-μ)^2 /2σ^2]
2*P(a < X < b) = erf[(b-μ)/σ√2] - erf[(a-μ)/σ√2]

Applying this to our problem and simplifying:
2*P(n) = erf[(N - 3n/2)*√(6/n)] - erf[(N - 1 - 3n/2)*√(6/n)]
E(n) = ∑{n=(N-1)/2 to N} n*P(n)
Numerically this approximates to
E(n) = 2/3 or (2/3)*N


*EDIT* Simpler analysis.
From eqns 1 and 2 above we obtain (my definitions)
n + X + x_n+1 = N
Taking the expectation
E(n) + E(X) + E(x_n+1) = E(N)
If you reverse the direction, you see that x_n+1 is uniform (0,1).
So E(n) + n/2 + 1/2 = N
Take the expectation again,
E(n) + 1/2 E(n) = N - 1/2
E(n) = (2/3) N - 1/3
As N --> ∞, E(n) --> (2/3)*N



*EDIT Zo Maar*
Yes the 2/3 was based on the assumption that the empty space was uniformly distributed.
Clarify something for me. You're saying that 0.75 is close to the mean or the median?

*EDIT*
OK I wrote the program to fill up the space (the way you suggested) and I'm getting (for N = 10,000) approximately
n = 0.74761*N ± 0.1%

Of course with numerical techniques, you can't get a rational expression. The program was fairly simple to write, but I figure any formal mathematical method would be really drawn out. This is why engineers prefer numerical techniques.


****************
A possible analytical approach

Zo Maar, you mentioned that you have a solution, but it looks cumbersome, and you're looking for a more elegant method. I don't know if such a method exists, but here is something that might be worth trying.

The idea is to start with a small space, find the expected number of cars, and then increase the space to see if a pattern develops. Let L=1 and a vacant space have length Y.

Case 1: If 0 < Y < 1, no cars can fit into that space
E(01) = 0

Case 2: If 1 < Y < 2, only 1 car can fit.
E(12) = 1

Case 3: If 2 < Y < 3, 1 or 2 cars can fit.
Only 1 car will fit if the car divides the space into two 0-1 spaces. This probability can be shown to be
(3-Y)/(Y-1)
2 cars will fit if the first car divides the space into one 0-1 and one 1-2 space. This probability is
(2Y-4)/(Y-1)
E(23) = 1 + (3-Y)/(Y-1)*E(01) + (2Y-4)/(Y-1)*[E(01) + E(12)]
= 1 + E(01) + (2Y-4)/(Y-1)*E(12)

It gets really tedious after this, but if you can find a pattern, bingo.

*EDIT* Remo, yes I saw the earlier error. I amended the approach slightly.

Answer 3

We know that if drivers deliberately park their cars "wastefully", they can do it with a minimum of (1/2)N + 1 cars, leaving gaps which are just under the size of one car. A quickie but not necessarily correct way to look at this problem, then, is to imagine drivers parking behind each other one at a time, but parking at randomly with gap lengths of 0 to L. The average gap length would then be (1/2)L, so that the answer to your question would be (2/3)N, approximately, being that each car would take up (3/2)L. I'll have to think about whether this works in real life.

jeredwm appears to have thought the same.

Addendum: I absolutely agree that I wouldn't go with (23/)N as definitive. It was just an approximation. Go for it, (Ω)kaksi_guy, I'm curious to find out what the Monte Carlo way says.

Addendum: Okay, I'm getting back into this problem, since there seems to be a lot of interest in it. The easiest way to analyze this problem is to look at the the first gap at the end of the row of parked cars. We know that the size of the gap varies from 0 to L, but what's it's likely size? All the gaps have the same probability distribution of sizes, so the problem is finding out that average size. If I begin with a length N*L, I can successively choose a L spot at random, and always pick the left (or right) segment, and repeat until I'm left with a gap < L. It seems to me that when the gap is > L and < 2L, it would be equally likely between the two extremes, and therefore it would mean that the final gap would have an average size of (1/2)L, so that each car on average would take up (3/2)L.

Why should the average size of the gap be 1/2? Consider N*L for a very large N. Let L = 1. After the first car parks, the size of either remaining space can be expressed as an integer plus some fraction, like 398.820349398... The fraction can be anywhere from 0 to 1 with equal chance. Every time another car parks, we end up with another such number, with the fraction being equally likely from 0 to 1. Finally we're left with a fraction between 0 and 1, all equally likely, so that the average size of the gap would be 1/2.

ADDENDUM: All right, I ran a Monte Carlo on this, and I, too, have been getting an average gap size of (1/3)L. Whenever I see a neat number like that, I suspect that there's probably a simple way to show why it is, but I just can't see it yet.

I give this one a star because this one threw me a curve. Interesting.

Answer 4

Not sure, but I think infinitely many.

Length L has no size, so if a car fits into nothing, you can fit infinitely many cars into nothing.

If this is thought of by using division:
N * L, divide by L, and you get N cars to fit inside length L.
-----
EDIT: By free space, do you mean the type of space that isn't actually real or do you literally mean FREE space.
-----
EDIT: Lol, I'm not a probability person, I'll research on this one. And what if they are cooperative?
-----
EDIT: Okay, so I guess this isn't actually a probability question and we have to expect that they will not be cooperative.

Let's hope I did this correctly =D!

0 < G < L

The gap length is between 0 and L, so let's say it's very close to L. G ~ L. This will make G our largest gap.

N/G = number of gaps in the entire parking space.
k * N = number of cars in the parking space
N - gaps total length
N - N = k * N
N = 0

G ~ 0
If G is almost 0, the expected number of cars is Perfect!
K < L

Lol, I think did this wrong... I'll try harder.
-----
EDIT: Wow, I got thumbs up for giving the wrong answer. I like it though :) !

Answer 5

I wouldn't agree with both above answers 2N/3 so readily.
Without losing generality we can assume L=1 (car length) and the street length N. Then I need to know what "They do it randomly and uniformly" exactly means. I assume the following interpretation: imagine k cars as k unit segments /k=1,2,..,N/, let x_i is the midpoint of ith segment, x_i is a random point with uniform distribution in [0, N]. Each possible car park can be represented by a vector (x_1, x_2, . . , x_k), where
x_i ≥ 1/2; x_i ≤ N - 1/2; | x_i - x_j | ≥ 1; i,,j = 1,2,..,k, i≠j
/thus the "cars" will fit into [0, N], any 2 of them without intersecting in a segment/.

Is this interpretation of random parking correct? If not, disregard the following.

. . . /as it turned out having read the author's clarification, I have tried entirely different problem - initial text deleted/ . . .

EDIT The time is about to expire, I have no solution yet, but some considerations (if we drop a random point on [0,1], dividing it into a short and a long segments, the expectations of their lengths are 1/4 and 3/4) make me think, that the expected number E(x) for a street with length x, car length L=1, for x - large enough, should satisfy the functional equation:
E(x+1) = 1 + E(x/4) + E(3x/4)
It has a solution E(x) = cx + c -1 with constant c satisfying
lim[x→∞] E(x)/x = 3/4, so I only suppose for N - large enough:
E(N) = 3N/4 - 1/4

Answer 6

Let's see... The amount of free space F between each car is clearly subject to 0 <= F < L. Unless there's something fancy distribution thing going on here that I'm missing, the average value of F should be L/2.

This means that 2/3 of the space should be occupied by cars (L car to every L/2 of free space). Thus the total space occupied by cars is 2/3(NL), so 2N/3 cars of length L should fit on average.

[EDIT - UPDATE 12/09/07]

I appreciate all of the more sophisticated analyses; as I said above, my premise was "unless there's some fancy distribution going on."

That being said, I think that there are essentially two ways to approach this problem: the hard way and the easy way.

The hard way is to consider the parking as an iterated process: the first car parks, the second car parks in some available space (if any), and so on until all space is used. Only after this iteration do you look at the space used. This is the approach taken by all of the more sophisticated answers here.

The easy way is to take the parking process as a "black box," and look only at the resulting parking pattern. This is, obviously, the approach that I took above. This analysis requires ONLY the assumption that the distribution of unparked space is symmetric, and hence has a mean of L/2. I am thus far unmoved by claims that a random parking (taken from the iterated perspective) will lead to a skewed (asymmetrical) distribution of unparked space lengths over the interval [0,L].

I'd be interested in hearing from those who think that 2/3N is NOT the correct answer why they believe that the unparked space holds a skewed distribution--in particular, in which direction should the distribution skew, and WHY? Qualitative reasoning is perfectly okay with me! Then I'll worry about what the particular value is. But, as I said, I'm as yet completely unconvinced of any reason that the distribution should be asymmetrical.

[EDIT 12/09/07 pm]

A) Zo: Your reasoning is bad, because it's NOT the case that half will be larger than L and half smaller, but that the AVERAGE is L. You're confusing mean with median. In fact, what you'll likely have is a few comparatively large gaps (say, >3L) and many smaller gaps (
B) In General: Here's a slightly more rigorous version of my argument, which doesn't rely on letting N be large.

Let k be the number of cars (of length 1) that park up a road of length N. Note that there will be k+1 gaps: one in front of each car, plus one behind the first car. Thus, maintaining my assertion that the mean length of a gap is 1/2 (see part C below), we can write an equation for total space by

space(cars) + space(gaps) = k(1) + (k+1)(1/2) = N.
Solving in terms of k gives that k = 2N/3 -1/3, precisely the same result Dr. D got using other methods!

C) One more crack at the "gap theory."
Consider the final parking distribution. Again, as noted before, each gap has length between 0 and 1 (taking L=1 as has become standard). We may think of each gap length as being drawn from some probability density function p(x) over [0,1].

Now, I would consider it quite surprising if p(x) were non-constant, and if you think about it, I think you should, too! After all, where in the problem would a bias of one gap length over another be introduced? I can come up with no reasonable explanation.

But, that's not even necessary. I would consider it downright ASTONISHING if p(x) were not symmetric (about x=1/2), which is all that is necessary to guarantee that the mean value is 1/2. THAT would mean that there is some reason to expect more "small" gaps than "large" ones (or vice versa). Again, there's nothing I see in the scenario that would account for such a bias.

There certainly are many common distributions one encounters that are skewed. But there is a reason the normal curve is called "normal"; symmetry is "normal"! If symmetry is going to break, there is a factor that breaks it. (Usually this is unusual activity at or near one end, such as an artificial endpoint as in the Chi-square distribution, different mechanics on one end versus the other, etc.) Again, I just don't see it here.

[EDIT - 12/10/07]

Okay, okay, consider me astounded!! :-)

I've written a MATLAB script to monte-carlo this (available at http://www.photobyj.com/parking_problem/parkfiles.htm ), and the values trend toward 3N/4 from below.

Very interesting!

Answer 7

Interesting. One thought is the following:
If we let f(y)=the expected number of cars of length L parked in a full street of length y, then
f(y)
=1+(int(f(x)+f(y-x-L),
x=0..y-L))
/(y-L)
for L f(L)=1,
and of course f(y)=0 for y To see this, notice that when the first car is randomly parked on an empty street of length y, it takes up a space of length L and divides the street into two "substreets" of lengths x and y-L-x, where x is the position of the front of the car as measured from the beginning of the street. This formula recursively determines f(y) for all y>=L, in particular implies that f(N*L)
=1+(int(f(x)
+f(N*L-x-L),
x=0..N*L-L))
/(y-L).

Answer 8

♦ is the street blind?
♦ you do not mention how wide it is; is it wide enough to get out of there if the row is jammed?
♦ Moreover you have no way to get out if there’s a close to nil gap left for your car; are other drivers aware of the fact?
♦ in the worst situation I’d block the whole street be I the next one to park!
Thus my answer is 1 car only;
▬
OK! Do not close your question! I’m going to write a prog and play it; so we could have a numeric answer; then our men would try to prove it formally; agreed?
▬
Setup: street length S=40000 to 60000 cm; car1 L=128cm; car2 L=256cm; distances between adjacent cars are 0 <= d Average fill ratio r1=0.668 for L1, r2=0.667 for L2;
▬ this is tremendous! the scenario above:
I’m stacking them one after another into the street and get r=2/3;
Now I’m scattering them at random until the street is jammed and get r=3/4;
▬ (dec/12, 11:20GMT)
to Zo; “Ugly facts destroy the beautiful theory - the answer is not 3/4.”
Yes, LoooooL! But since clever jeredwm got a ¾-δ, and less clever kaksi got a ¾+δ, I indulged myself reasonably to somewhat “round” the answer to ¾ without δ! Moreover I also get a ¾-δ at some quite tiny detail in my prog, and I cannot account it for so far!
To Ksoi and Remo; can you men be more definite with final numbers?
▬ (dec/12, 16:10GMT)
I’m sure now the answer is r=3/4; the longer the street the closer it CONverges to ¾ from below, discrepancies are likely being due to effects of street ends and quantizing by 1cm;

Answer 9

What about higher dimensions? Consider for example square-shaped helicopters landing randomly on a large field in the two-dimensional case. For higher dimensions than 2, there may not be a nice "parking" analogy, but the problem is easily translated.

Is it true that the "volume ratio" for dimension n will be close to (3/4)^n. (Rough initial intuition.) Can anyone produce efficient code to run Monte Carlo for some higher-dimensional case?