Math help pls (combinatorics/probability)

Discussion in 'General Off-Topic Chat' started by Veho, May 17, 2013.

  1. Veho
    OP

    Veho The man who cried "Ni".

    Former Staff
    8,931
    17,347
    Apr 4, 2006
    Croatia
    Zagreb
    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 :bow:

    Warning: Spoilers inside!

    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 :bow:
     
  2. Densetsu

    Densetsu Pubic Ninja

    Former Staff
    3,435
    2,869
    Feb 2, 2008
    United States
    Wouldn't YOU like to know?
    I never thought I'd find Veho of all people asking for help with math homework :P
    Warning: Spoilers inside!
     
    Rydian likes this.
  3. Ericthegreat

    Ericthegreat Not New Member

    Member
    1,816
    324
    Nov 8, 2008
    United States
    Vana'diel
    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
     
    Veho likes this.
  4. Delta517

    Delta517 Its okay...Im a ninja ;)

    Member
    1,327
    35
    Nov 25, 2008
    Norway
    I only had time to look at the first one, but I believe the answer is 1/100 :)
     
  5. Snailface

    Snailface My frothing demand for 3ds homebrew is increasing

    Member
    4,324
    1,983
    Sep 20, 2010
    Engine Room with Cyan, watching him learn.
    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.
    Code:
    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 likes this.
  6. Veho
    OP

    Veho The man who cried "Ni".

    Former Staff
    8,931
    17,347
    Apr 4, 2006
    Croatia
    Zagreb
    Alas, my "class" days are long past :ha: 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 :bow: I didn't even know it existed.

    Snailface, your stochastic approach seems to have come up with the correct average.
     
    Snailface likes this.
  7. Zetta_x

    Zetta_x The Insane Statistician

    Member
    1,844
    257
    Mar 4, 2010
    United States
    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!
     
    EZ-Megaman, Veho and Snailface like this.
  8. Zetta_x

    Zetta_x The Insane Statistician

    Member
    1,844
    257
    Mar 4, 2010
    United States
    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.
     
    Veho likes this.
  9. Tom Bombadildo

    Tom Bombadildo Honk!

    pip Contributor
    GBAtemp Patron
    Tom Bombadildo is a Patron of GBAtemp and is helping us stay independent!

    Our Patreon
    10,901
    11,081
    Jul 11, 2009
    United States
    I forgot
  10. Zetta_x

    Zetta_x The Insane Statistician

    Member
    1,844
    257
    Mar 4, 2010
    United States
    I have created a simulation in Matlab that simulates problem 2. The answer converged to about .0635

    Code:
     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