Re: chess problem

matt271829-news@xxxxxxxxxxx wrote:
Proginoskes wrote:
quasi wrote:
But simulation gives an answer of slightly less than .75, so 49/99
seems not to be correct.

I was wondering when someone was going to run a simulation. 8-)

The method should still work. (Later) It does; I just got some numbers
wrong.

[...]
On 17 May 2006 22:03:30 -0700, "Proginoskes" <CCHeckman@xxxxxxxxx>
wrote:


Gino Martelli wrote:
i have this one other probability problem that i can't seem to solve
easily....

a parking lot has 12 adjacent spaces and 8 are occupied. an suv arrives
and needs two adjacent spcaes to park. What is the probability that it
is able to park? Generalize.

I used the ball in urns formula here such that i got:

(12C4 - 9C4) / 12C4 which is roughly about 75%

Is there any other way to arrive to this answer?

I'm not sure the urns formula will do it; I think it's a little more
complex than that. (Unless I missed another interpretation of 9C4.)

One way to do it is to use Inclusion-Exclusion, but it gets messy: Let
P(n) be the ways to choose 4 elements (out of {1,2,3,...,12}) such that
n,n+1 are chosen. Then you want

| P(1) union P(2) union ... union P(11) |
= sum | P(i) | - sum | P(i) intersected P(j)|, such that 1 <= i < j <= 11,
+ sum | P(i) intersected P(j) intersected P(k) |, such that
1 <= i < j < k <= 11.

The first term is easy to calculate: 11 * C(8,2), since each P(i) has
C(8,2) elements.

Should be 11 * C(10,2).

The last term is easy to calculate, since the only way to have 4
elements is to choose
j = i + 1 and k = j + 1: 12 - 4 + 1 = 9. (You can also choose the
smallest element.) If there is any less overlap, then there will be 5
or more numbers.

Now for the second term. If j > i + 1, then you've chosen 4 numbers.
Since the number of ways to choose i and j so that i < j is C(11,2),
and there are 11 ways to choose
j = i + 1, there are C(11,2) - 11 ways to choose j > i + 1.

No, that's 10 ways, so the value here should be C(11,2) - 10.

Now for j = i + 1. If i > 1 and j < 11, then you've chosen 3 numbers in
a row by choosing i and j (which can be done in (12 - 3 + 1) - 2 = 8
ways), and there are two forbidden numbers (i-1 and j+2), so you now
have 7 numbers to choose from.

No; there are no forbidden numbers here. So you have 9 to choose from,
not 7.

If i = 1 then you've chosen 1,2,3. Then the number of choices for the
4th number is 8 (5 through 12). Same argument for j = 11.

And this should be 9, not 8. (In fact, the last two quotes could be
combined.)

Grand total: 11 * C(8,2) - (8 * 7 + 2 * 8) + 9 = 245.
Probability of having two adjacent spaces: 245 / C(12,4) = 49 / 99.

Grand total: 11 * C(10,2) - ((C(11,2) - 10) + 8 * 9 + 2 * 9) + (9) =
369, same
as
12C4 - 9C4.

Hmmm. I bet there's an identity lurking here, once you generalize.

Moral of the story: Don't ad lib formulas when you're at the computer.
8-)

--- Christopher Heckman

Your method looks very complicated. How about doing it like this...

Let s be the total number of spaces in the lot, and c be the number of
cars occupying those spaces. The total number of possible arrangements
is C(s,c). Now imagine all the cars in a row, next to one another. To
make it impossible to park the SUV we need to place the s - c empty
spaces amongst the cars such that no two are together. There are c + 1
slots between the cars (including the two ends), so the empty spaces
can be placed in C(c+1, s-c) ways.

Therefore the probability that the SUV can't be parked is C(c+1,
s-c)/C(s,c), and the probability that it can be parked is 1 - C(c+1,
s-c)/C(s,c).

For c = 8, s = 12 we have 1 - C(9, 4)/C(12,8), which is just a
different way of writing (12C4 - 9C4) / 12C4, which was the OP's
answer.

.... and, generalising further, if the SUV takes up n places then it's
still just balls I think... oh, and urns too.

The urns are the c+1 slots between the cars, the balls are the s-c
empty parking spaces, and we need to find the number of ways to
distribute the balls in the urns such that there are at least n balls
in at least one urn - or, in terms of the complement, such that no urn
has more than n-1 balls.

Thus, for n = 3 I get the probability of being able to park the SUV
equal to

1 - 1 / C(s, c) * [sum over i of C(c + 1, i) * C(i, s - c - i)]

where the sum is taken over 0 <= i <= c + 1 and (s - c) / 2 <= i <= s -
c. To make C(s, c) valid I suppose I should also stipulate c <= s (if c
s then the answer is obviously zero). These various conditions could possibly be tidied up a bit...

I haven't looked at n > 3, but the balls and urns equivalent would be
well documented somewhere I imagine.

.

Relevant Pages

  • Re: m balls k urns
    ... >urns shoud be distinguishable. ... There are m indistinguishable balls and k distinguishable ... distinguishable urns, with repetitions allowed. ... throws of 3 dice with 6 sides each there are. ...
    (sci.logic)
  • Estimating correlations between groups using binomial sampling
    ... Consider a large number of urns containing balls of various colours. ... Looking at the raw data, I suspect that the numbers balls of different ... I might estimate the correlation ...
    (sci.stat.math)
  • Re: Placing Balls in Urns and Expected values
    ... urns, if balls are indexed, too. ... there are n possibilities how to place all balls into ... To compute probability, ... Any distinction vanishes. ...
    (sci.math)
  • Re: Help with Urn Problem
    ... number of SINGLY occuppied urns when M balls are randomly placed into N ... exactly one ball, and find the probability that exactly K, ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.stat.math)
Quantcast