Math help pls (combinatorics/probability)

[Veho]

I have two probability-related problems I can't quite formulate. I would appreciate help from any Tempers with related knowledge. There's a Temper with a user title "mad statistician" or something along those lines, maybe he could help.

Anywhoo, the problems:

1
EDIT: Solved, thanks to Ericthegreat

Spoiler

There's a boarding queue at an airport, 100 passengers are waiting to fill 100 seats. The first passenger is a loud obnoxious asshole that doesn't care about reservations, and he will take a random seat. The passenger whose seat that was will have to take a random empty seat. The passenger whose seat that one was will have to take a random empty seat too, and so on, until the last passenger is seated. What are the odds that the last passenger ends up in his allocated seat (the seat that he reserved)?

Passengers in between the one who took a random seat and the one whose seat it was take their allocated seats. This is important.

I have no idea where to start. I was doing fine until I realized that last point

The asshole has a 1/100 chance of sitting in his own seat. If he doesn't, the guy whose seat was taken (1/99 chance of it being the second passenger, third, fourth etc.) has (101 - his place in line) places to choose from, and that's a 1/(101-his place in line) chance of taking the asshole's place, and they cancel each other out. If not, the next person has (101-his place in line) places to choose from, and so on, until one of them sits in the asshole's seat and the mixup is neutralized and the rest of the line is seated as scheduled.

2

A card game is played using a deck of 52 cards (poker deck). There are four players, each player is dealt 10 cards, and they can only look at the top 4 of those cards. Out of the remaining cards, one card is flipped over and shown. Players can then place one of their face-up cards on the revealed card, but only if the number on the card is one less or one more than the number on the revealed card (cards having values from 1 to 13, in 4 colours). What are the odds that out of the players' 16 face-up cards, not a single card can be placed on the revealed card?

So it's 40 cards out of 52, that's the binomial coefficient, then there's 16 out of 40 and 1 out of the remaining 12, so the question is, what are the odds that all the 16 revealed cards will be numbers 2 or more below or above, or the same as, the number of the revealed card? The revealed card is 1 out of 52; if it's a 1 or a 13 there are 4 cards that can be placed on it (2s in any color and 12s in any color, respectively), for the rest there are 8 that can be placed on it, What are the odds that out of the 16 face-up cards, none can be placed on the revealed card?

Can I ignore the order in which I draw the cards, and say I reveal the card first and then deal the rest (13 possible strengths)? In that case I have 16 out of 51 cards (binomial) face up, 4 or 8 of which can be played (depending on the first one). Do i separate the possibilities? I have 4 times 2 cases where only 4 cards can be played (if available), and 11 times 4 cases where 8 cards can be played, the odds of the first case are 2 against 13, the odds of the second case are 11 against 13, so i calculate conditional probability for the face-up cards for the two separate sets of cases and then add them, or do I multiply them by 2/13 and 11/13 respectively? I'm lost.

And an additional question, what about a deck of 32 cards (8 strengths, 4 colours), 6 cards dealt to each player (3 face up, 3 face down)?


Halp pls, thank you

 

[Densetsu]

I never thought I'd find Veho of all people asking for help with math homework

Spoiler

Wish I could help you there, but my statistics knowledge is ass and these problems are far beyond my ability

 

[Ericthegreat]

1. Seems like it cannot be answered(but i really dunno) Got a friend in same class you could call? Also post this on the stackoverflow for math: http://math.stackexchange.com

 

[Delta517]

I only had time to look at the first one, but I believe the answer is 1/100

 

[Snailface]

I wrote a little program to test problem 1 out. Not in the mood for difficult math this late.

It appears there is about a 50% chance the last guy will end up in the assigned seat. This could definitely be wrong.
You be the judge.

from random import randint
last=0
 
for c in range(10000):      #many trials for accuracy
    seat=[0]*101
 
    s=randint(1,100)        #first guy, gets random seat
    seat[s]=1
    p=2                    #loop will start with guy 2
    pc=p
 
    while pc < 101:        #run until 100 peeps are seated
 
        p=pc                #reset people counter
 
        while True:        #keep looping until empty seat found
 
            if not seat[p]:        #break if empty seat
                break
            else:
                p=randint(1,100)    #try to find new seat
        seat[p]=pc                  #seat a peep
        pc+=1                      #go to next person
 
 
    if seat[100]==100:        #check if last guy got assigned seat
        last+=1
print (last/10000.0*100),"%"  #calc percentage of last guy seated correctly
#it appears he only gets seated in seat 1 or 100, 50% chance each, Hmm.

 

[Veho]

1. Seems like it cannot be answered(but i really dunno) Got a friend in same class you could call? Also post this on the stackoverflow for math: http://math.stackexchange.com

Alas, my "class" days are long past It's not a class assignment, it's just a puzzle I came across.

But I found the answer on Stack Exchange, thank you for pointing me in that direction I didn't even know it existed.

Snailface, your stochastic approach seems to have come up with the correct average.

 

[Zetta_x]

I have two probability-related problems I can't quite formulate. I would appreciate help from any Tempers with related knowledge. There's a Temper with a user title "mad statistician" or something along those lines, maybe he could help.

Anywhoo, the problems:

2

A card game is played using a deck of 52 cards (poker deck). There are four players, each player is dealt 10 cards, and they can only look at the top 4 of those cards. Out of the remaining cards, one card is flipped over and shown. Players can then place one of their face-up cards on the revealed card, but only if the number on the card is one less or one more than the number on the revealed card (cards having values from 1 to 13, in 4 colours). What are the odds that out of the players' 16 face-up cards, not a single card can be placed on the revealed card?

So it's 40 cards out of 52, that's the binomial coefficient, then there's 16 out of 40 and 1 out of the remaining 12, so the question is, what are the odds that all the 16 revealed cards will be numbers 2 or more below or above, or the same as, the number of the revealed card? The revealed card is 1 out of 52; if it's a 1 or a 13 there are 4 cards that can be placed on it (2s in any color and 12s in any color, respectively), for the rest there are 8 that can be placed on it, What are the odds that out of the 16 face-up cards, none can be placed on the revealed card?

Can I ignore the order in which I draw the cards, and say I reveal the card first and then deal the rest (13 possible strengths)? In that case I have 16 out of 51 cards (binomial) face up, 4 or 8 of which can be played (depending on the first one). Do i separate the possibilities? I have 4 times 2 cases where only 4 cards can be played (if available), and 11 times 4 cases where 8 cards can be played, the odds of the first case are 2 against 13, the odds of the second case are 11 against 13, so i calculate conditional probability for the face-up cards for the two separate sets of cases and then add them, or do I multiply them by 2/13 and 11/13 respectively? I'm lost.

And an additional question, what about a deck of 32 cards (8 strengths, 4 colours), 6 cards dealt to each player (3 face up, 3 face down)?


Halp pls, thank you

I don't have much time, but let me see if I can have some words of wisdom!

Let X be the number of cards that can be played on a face up card; the support set for X is {0,1,2,3,4,5,6,7,8} (8 is definitely possible, if the value of the card is 3, then there is a slight possibility each 4 players would have all of the 2's and 4's)

However, we need to condition on what the face up card is. So let Y = the value of the face up card. The support set for Y = {1,2,3...13}

By the law of total probability: P(X = 0) = sum(j=1 to 13)[P(X = 0 | Y = j) * P(Y = j)]

Lets look at the probability space Y or P(Y=j). For a specific case, (lets say j = 1). In order for j = 1 to be possible, we cannot have handed out all of the aces to the players. However, it's possible to hand out 0 1 2 3 aces to the players; so we have to condition on the number of aces that were handed out. So we partition the space into two categories, aces and not aces.

Let Z be the number of aces that was given out. So Z = 0,1,2,3,4.

P(Y = 1) = sum(i=0 to 4) = P(Y = 1 | Z = i) * P(Z = i)

Lets look at the probability space of Z. If we have given out any cards, we could give it to any player. So of course we have to condition it on the player we have given out. It's possible to give it out to player 1 2 3 4. We can use the law of total probability and condition once again on the player, but I have an easier way of going about it. The space is partitioned in getting an ace or not getting an ace. We could condition on which player gets the ace, but because they are equally likely, I don't think it will make a difference

So the P(Z=0) means out of the 40 cards were selected, none were aces:

or P(Z = 0) = 4C0 * 48C40 / 52C40 (The notation I have used was we choose 0 out of the 4 aces, we chose 40 non aces (48 of them) ratioed by choosing 40 out of 52.

P(Z=1) = 4C1 * 48C39 / 52C40

In general P(Z = z) 4Cz * 48C(40-z) / 52C40
for z = {0,1,2,3,4}

From here, it's all downhill.

P(Y = 1 | Z = 0) means getting an ace when no aces were given out. Well out of the 12 cards remaining, 4 of them are aces, so the probability is 4/12
P(Y = 1 | Z = 1) is 3/12
P(Y = 1 | Z = 2) is 2/12
P(Y = 1 | Z = 3) is 1/12
P(Y = 1 | Z = 4) is 0/12

It's better to look at it like this: P(Y = 1 | Z = z ) = (4-z) / 12
P(Y=1) = sum(z=0 to 4)P(Y=1 | Z = z)*P(z=z) = sum(z=0 to 3)P(Y=1 | Z = z)*P(z=z) (since P(Z=4) = 0) = sum(z=0 to 3) (4Cz * 48C(40-z) / 52C40) * (4-z)/12)

A little uphill but then it goes downhill !

P(X = 0 | Y = 1) means no one has a 2. You would expect since the symmetry of this beautiful system, P(X = 0 | Y = 13) would work the same way or P(X = 0 | Y = 1) = P(X = 0 | Y = 13). The same thing for P(X = 0 | Y = 2) = ... P(X = 0 | Y = 12) (Since for Y = 2, the value 1 and 3 would be likely candidates.

P(X = 0 | Y = 1) means that no one has a 2. There are 16 cards that are faced up (of the 4 players). So all of the 2's need to be in the 36
P(X = 0 | Y = 1) = P(X = 0 | Y = 13) = 4C0 * 48C16 / (52C16) (or out of the 16 face up cards, 0 are aces and the 16 of them are not aces out of 52 choose 16 different combinations)

P(X = 0 | Y = 2) = ... P(X = 0 | Y = 12) is a little bit more tricky, we can't get one of two values, so we have to choose 0 out of the 8 cards (is either a Ace or 3) and 16 out of the other 44 cards.

So P(X = 0 | Y = 2) = ... P(X = 0 | Y = 12) = 8C0 * 44C16 / (52C16).

From this, we have all of the information you need to know to compute the probability. To find the odds: P(X = 0) / 1 - P(X = 0)

Unfortunately I have to get to class, the key point to this is defining the variables in a precise way such that the computations are pretty straight forwards, then having to condition an ass load of times!

 

[Zetta_x]

The nice thing about this experiment is that all players are equally likely to get any cards. It made everything simpler because then we would have to condition on the player since their probabilities differ. The even nicer thing is that a player could play up to any amount of cards (if the faced up card was a 2, a player could play 1 or 3 and he could play both). If a player could only play 1 card, then to find the general probability of P(X = x) would have been just a living fucking hell because you would have to condition on whether or not the player had more than one card to play and analyze how that effects the rest of the players.

However, with all of the nice things about this experiment, this is similar to only having one player. That one player receives 40 cards and 16 of them are faced up. Then they check to see whether any of those 16 cards are a match. The analysis would of been exactly the same. However, it would be a lot easier to simulate this into a computer program.

I fucking love combinatorics, however; statistics barely covers it; let me show you a statistics way of approaching the value:

It would be binomial (whether or not a card can be played). You can repeat this simulation n times then eventually estimate the probability p. If we let W be the number of times a card couldn't be played. Then after n simulations W ~ binomial (n,p). After a large amount of simulations, phat = W/n asymptotically normal (E[W], var[W]). Since W is binomial E[W] = n*p and var[W] = n*p*(1-p).

If we wanted to find out how many times we have to simulate this in order to get the true probability (your answer) within a .001 precision with 99% confidence.

We know for large values of n, phat is asymptotically normal (np, n*p*(1-p)). The margin of error = Z_alpha/2 * sqrt(pq/n). We have no idea what p is, so we take it to be the most extreme case (the one that maximizes n) which is P = .5

We working this formula around, we get ME = Z * sqrt(pq/n) => (ME/Z)^2*1/pq = 1/n or (Z/ME)^2 * pq = n (however, we maximize by choosing (p=q=.5) => (Zp/ME)^2

Our margin of error is .001 and the Z value corresponding to 99% is 2.575: plugging into the formula, we get n must be 1,657,657. While I do realize that's a fucking high number, It wouldn't take more than a minute to simulate that many times. All you would have to program is taking 52 cards (which can be seen as 1,2,3,4,5,6,7,8,9,10,11,12,13 with repetition 4). During the experiment, 24 cards become dead (40 cards - 16 (which is the actual amount that is faced up for the players)) and 16 cards are active. Out of the remaining 12 cards, choose 1 randomly. If any of the 16 active cards fits the description: program a win.

w_i is = 1 if the ith simulation is a win
w_i is = 0 if the ith simulation is a lose

W = sum_(i=1^n) w_i where n is the chosen 1657657.

The maximum likelihood estimator of your answer would be W / n; so our estimated P(no cards were put on top) = W/n

----

Jesus! I haven't had this much fun on the temp in so long.

My title used to be the drunk statistician because I was anti-social. I loved numbers and patterns but I kept to myself. Well, one day I found alcohol and something magic happened: I became social. The first 19 years of my life of avoiding people I have all of a sudden transformed into a social person. What happened is that my mind worked wonders drunk, amazing things happened, so I got addicted to alcohol. So often I would be drunk and doing statistics.

Well... drinking lost it's significance. So I don't drink much. However, I have become batshit crazy. I may seem normal, but there's a lot of stuff going in my head that I can't accurately describe it. So I read your thing that said the Mad Statistician. I was thinking about changing my title to that but people may think I am angry. However, anger is not something I often meet, I have tons of patience. It may seem at times that I am angry, but I only do it for the fun of yelling and typing loud.

So I have changed it to the insane statistician.

 

[Tom Bombadildo]

2.

 

[Zetta_x]

I have created a simulation in Matlab that simulates problem 2. The answer converged to about .0635

 W = 0;
for k = (1:1000000)
a = [1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12 13 13 13 13];
b = [];
for j = (0:3)
for i = (0:3)
r = randi([1,52 - 10*j - i]);
b = [b a(r)];
a(r) = [];
end
for i = (4:9)
r = randi([1,52 - 10*j - i]);
a(r) = [];
end
end
r = randi([1,12]);
f = a(r);
w = 1;
for i = (1:16)
if abs(f - b(i)) == 1
w = 0;
end
end
W = W + w;
end
W / k
 
 
ans =
 
    0.0635

The theoretical value I have calculated was:
0.063895