Parking lot random variable problem.

[pdrjuarez]

Homework Statement

There is a parking lot outside a building with n evenly spaced parking spaces that are numbered 1 through N with parking space #1 being closest to the entrance of the building, and parking space #n being the furthest away from the entrance to the building. A driver enters the parking lot, starting at parking space N, moving his way through to parking space #1. His goal is to park as close to the entrance of the building possible, but there's a few restrictions:

1) He knows nothing at all about the arrangement of the cars inside the parking lot (This means that all possible arrangements of cars are possible; there may be 0 cars inside the parking lot, there may be n cars, or anything in between, in any order) 2^n arrangements in total

2) He will drive all the way from parking space n to parking space k, with k in between 1 and n. Once he's reached the k'th spot, he will take the k'th spot (if available). Otherwise, he will take the next available parking space after k (could be k-1, k-2 etc)

3) he can't see spaces that are ahead of him. If he is at spot k, he can't see the k-1th spot

4) If he reaches spot #1 and still hasn't parked, he must park outside the parking lot (which I labeled as the n+1 spot, since its farther away than the n'th spot

Q 1: How close to the entrance of the building can he expect to be, on average? (in other words, what's his expected value. this is a function of which spot, k, he chooses)

Q 2: For a parking lot that is n spaces big, what is the optimal K value? (Which value of k will make the average distance from Q1 the smallest?)

Homework Equations

The Attempt at a Solution

If he picks spot #k, he has exactly k chances to park before he is sent outside the building.
The chance of him parking exactly at k is 1/2 (since it's completely random),
the chance of him parking exactly at k-1 is 1/4 (Since spot k had to be filled, and k-1 must be empty
The chance of him parking exactly at k-2 is 1/8 (Since spot k and k-1 had to be filled, and k-2 had to be empty

etc etc

So, the expected value came out to be something of this nature

(k/2)+ (k-1)/2² +(k-2)/2³ etc etc
Which can be written as
Expected value = Sum from i=0 to k-1 of ((k-i)/(2ⁱ⁺¹)

We also have to consider the possibility that there are absolutely no parking spaces available from the k'th spot, which would put him at the n+1th spot. There's a 1/2^k chance of this happening, since ALL k spots from k to 1 have to be taken. I added that to my expected value

Expected value= Sum from i=0 to k-1 of ((k-i)/(2ⁱ⁺¹)) + (n+1)/2^k

So, that's question #1

For question #2, I tried taking the derivative with respect to K of this really messy function (I changed the sum to an integral with respect to the variable i), and set it equal to 0 to find the critical points... After much messy calculus which would be a pain to post here, I managed to get to this point
(1-ln(2)* (n+1))/2^k) = 0
Now... I am not very sure if i even managed to do all of that right. But, the only way that can be 0 is if the numerator is 0, which would mean that n = (1 - ln(2))/(ln(2))... Which doesn't make sense because I wanted some function of k in terms of n that would give me the optimal k value, and this just gives me a constant n value (as if k didn't matter when calculating the expected value, but it really seems like it should)

 

[Ray Vickson]

Homework Statement

There is a parking lot outside a building with n evenly spaced parking spaces that are numbered 1 through N with parking space #1 being closest to the entrance of the building, and parking space #n being the furthest away from the entrance to the building. A driver enters the parking lot, starting at parking space N, moving his way through to parking space #1. His goal is to park as close to the entrance of the building possible, but there's a few restrictions:

1) He knows nothing at all about the arrangement of the cars inside the parking lot (This means that all possible arrangements of cars are possible; there may be 0 cars inside the parking lot, there may be n cars, or anything in between, in any order) 2^n arrangements in total

2) He will drive all the way from parking space n to parking space k, with k in between 1 and n. Once he's reached the k'th spot, he will take the k'th spot (if available). Otherwise, he will take the next available parking space after k (could be k-1, k-2 etc)

3) he can't see spaces that are ahead of him. If he is at spot k, he can't see the k-1th spot

4) If he reaches spot #1 and still hasn't parked, he must park outside the parking lot (which I labeled as the n+1 spot, since its farther away than the n'th spot

Q 1: How close to the entrance of the building can he expect to be, on average? (in other words, what's his expected value. this is a function of which spot, k, he chooses)

Q 2: For a parking lot that is n spaces big, what is the optimal K value? (Which value of k will make the average distance from Q1 the smallest?)

Homework Equations

The Attempt at a Solution

If he picks spot #k, he has exactly k chances to park before he is sent outside the building.
The chance of him parking exactly at k is 1/2 (since it's completely random),
the chance of him parking exactly at k-1 is 1/4 (Since spot k had to be filled, and k-1 must be empty
The chance of him parking exactly at k-2 is 1/8 (Since spot k and k-1 had to be filled, and k-2 had to be empty

etc etc

So, the expected value came out to be something of this nature

(k/2)+ (k-1)/2² +(k-2)/2³ etc etc
Which can be written as
Expected value = Sum from i=0 to k-1 of ((k-i)/(2ⁱ⁺¹)

We also have to consider the possibility that there are absolutely no parking spaces available from the k'th spot, which would put him at the n+1th spot. There's a 1/2^k chance of this happening, since ALL k spots from k to 1 have to be taken. I added that to my expected value

Expected value= Sum from i=0 to k-1 of ((k-i)/(2ⁱ⁺¹)) + (n+1)/2^k

So, that's question #1

For question #2, I tried taking the derivative with respect to K of this really messy function (I changed the sum to an integral with respect to the variable i), and set it equal to 0 to find the critical points... After much messy calculus which would be a pain to post here, I managed to get to this point
(1-ln(2)* (n+1))/2^k) = 0
Now... I am not very sure if i even managed to do all of that right. But, the only way that can be 0 is if the numerator is 0, which would mean that n = (1 - ln(2))/(ln(2))... Which doesn't make sense because I wanted some function of k in terms of n that would give me the optimal k value, and this just gives me a constant n value (as if k didn't matter when calculating the expected value, but it really seems like it should)

I don't think you have enough information to make an analysis. What is the probability that all N spaces are filled? This is not just a function of N, but also of the surrounding population and the percentage of people owning cars, etc. In other words, we could have P{all spaces filled} = 0.0001 or P{all spaces filled} = 0.9999, and surely those would affect the expected value of distance (assuming, for example, some fixed distance when all the N "near" spaces are filled). However, assuming that P{space k available} = p_k for k = 1,2,...,N and q = 1 - sum_{k=1..N} p_k = P{all N spaces filled} are all given, the question does make sense. Let P(k) = probability he parks in space k. Then p(N) = p_N. How do you get P(k) for k < N? Well, he parks in space k only if spaces (k+1),...,N are filled and space k is empty. Knowing the distribution {p_j}, you can get that probability.

This will not lead to a nice expression for general {p_j}, but it might be tractable if p_1= p_2 = ...= p_N = a and P{all filled} = 1-N*a for some 0 < a < 1/N. (That is, given some spaces are empty, the probability that space j is available is the same for all j.)

RGV

RGV

 

[pdrjuarez]

However, assuming that P{space k available} = p_k for k = 1,2,...,N and q = 1 - sum_{k=1..N} p_k = P{all N spaces filled} are all given, the question does make sense. Let P(k) = probability he parks in space k. Then p(N) = p_N. How do you get P(k) for k < N?

I don't really know what 'p_k' this notation is supposed to be... could you clarify that please? So i don't get half of what you're saying pretty much, but I'll reply my best

The probability that each parking space is empty or taken is 1/2, and each parking space is independent of each other. (That's what I meant by restraint #1; all 2^n possible car arrangements are possible and are all equally likely)

Therefore P{space k available} is 1/2, for all k

Well, he parks in space k only if spaces (k+1),...,N are filled and space k is empty.

No, the spaces before K are meaningless because he will not park in any of them, regardless of whether they are filled or not. The first space he can park in is K, and if that one is filled he can park in k-1, if that one is filled he will park in k-2... etc.

Knowing the distribution {p_j}, you can get that probability.

This will not lead to a nice expression for general {p_j}, but it might be tractable if p_1= p_2 = ...= p_N = a and P{all filled} = 1-N*a for some 0 < a < 1/N. (That is, given some spaces are empty, the probability that space j is available is the same for all j.)

Again, don't really know what p_< > is supposed to mean. Sorry if the wording of the problem is confusing, it's hard to be explain this precisely without pictures =/
Thanks for your reply

 

[nickalh]

Sum from i=0 to k-1 of ((k-i)/(2$^{i+1}$) + (n+1)/2k

First let's rewrite the sum to be a simpler sum. We can actually drop out one of the k's and also greatly simplify the whole thing.
$\Sigma ^{k-1}_{i=0} \frac{k-i}{2^{i+1}}$
is
$\frac{k-0}{2^{0+1}} +\frac{k-1}{2^{1+1}} +\frac{k-2}{2^{2+1}} + ... +\frac{k-(k-1)}{2^{(k-1)+1}}$

Focusing on the last few terms,
$... 3/2^{k-2}+ 2/2^{k-1}+ 1/2^k$
We can factor 1/2 from everything making the numerator and denominator similar and easier to work with.
$\frac{1}{2}*$($... 3/2^{k-3}+ 2/2^{k-2}+ 1/2^{k-1}$ )
Ahhhh, there, that's easier to look at, and work with already.

Then we can commute everything reversing the order.
$\frac{1}{2}*$($1/2^{k-1}+ 2/2^{k-2}+ 3/2^{k-3}+... k/2^0$ )

Now the series is
$\frac{1}{2}* \Sigma i/2^{k-i}$


Rearranging just the formula for each term
$i/2^{k-i} = \frac{i}{2^k * 2^{-i}} = \frac{i* 2^i}{2^k}$

Thankfully, 1/2^k is a constant with respect to i, so it can also come out front of the sigma sign.
$\frac{1}{2}* \Sigma i/2^{k-i} becomes \frac{1}{2*2^k}* \Sigma ^{k-1}_{i=0} i 2^i$


For both our sakes, check some terms, at least two at each end, by multiplying out the 1/2^(k+1). See if it's the same as your series in reverse order.

Conclusion: this sum formula has a "closed form" meaning it can be calculated to get rid of the sum and i notation. Find the closed form before taking the derivative. Also, the entire thing can be checked with a computer algebra system. A few will even accept a bunch of terms and generate the closed form.



Some other notes:
Two technical, minor points: We're supposed to write the i=0 to k-1 throughout, but I thought this was complicated enough. Everytime I use "..." I should have several terms then a final term. Without the final term, the series goes on forever.

In the future, please scan and post your work, possibly with imagehost, flickr, photobucket, imageshack, etc. I've probably done too much work for you. Doing it oneself definitely develops skills.

Don't be intimidated by series:
As a general rule, it's much easier to set up the original sum with simpler notation. Taking some care when choosing how to do this can make our lives much easier in the long run. In hindsight, I would do this exercise by focusing on the last terms, using them as a basis for the term formula.
Also, many (most?) of the properties of integrals can apply to series because an integral equals the lim of an infinite sum.