Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: [1]

Author Topic: Math is hard - questions about chance  (Read 4669 times)

0 Members and 1 Guest are viewing this topic.

Jeebus

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2515
  • Shuffle iT Username: jeebus
  • Respect: +1635
    • View Profile
Math is hard - questions about chance
« on: March 28, 2017, 02:57:00 pm »
+1

I hope someone can help me.

What's the average number of Events/Landmarks (as a whole) in a given random Kingdom? Assume 55 L/E and 330 cards total. Assume shuffling all 330 cards and drawing until you have 10 kingdom cards as per the rules.

The average would seem to be 1.67, but that number doesn't take into account the cap at 2 L/E. And I have no idea how to take that into account.

Jeebus

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2515
  • Shuffle iT Username: jeebus
  • Respect: +1635
    • View Profile
Re: Math is hard - questions about chance
« Reply #1 on: March 28, 2017, 03:04:30 pm »
+1

Next question:

Say that the number from the first question is x. Say that we select a number of kingdoms, let's say 8 kingdoms, and no cards (including E/L) are allowed to be repeated across kingdoms. On average, how many L/E would show up in total? I think the answer is just x times 8, but I'm not sure.

ben_king

  • Golem
  • ****
  • Offline Offline
  • Posts: 190
  • Shuffle iT Username: ben.king
  • formerly grsbmd
  • Respect: +612
    • View Profile
Re: Math is hard - questions about chance
« Reply #2 on: March 28, 2017, 03:30:05 pm »
+4

Fortunately simulation is easy.  Over 10,000,000 trials, the answer to your first question is ~1.266.  And 10,000,000 trials for your second question yields ~1.266. 

So the two answers are very close, though I suspect they should not ever be equal.  If you consider the case where the number of events is smaller than the number of kingdoms, it's clear that the number of e/l per kingdom will depend on the number of kingdoms.  That should carry over to the case we're looking at here, though the effect would be much smaller.
Logged

Jeebus

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2515
  • Shuffle iT Username: jeebus
  • Respect: +1635
    • View Profile
Re: Math is hard - questions about chance
« Reply #3 on: March 28, 2017, 03:42:15 pm »
0

Fortunately simulation is easy.  Over 10,000,000 trials, the answer to your first question is ~1.266.  And 10,000,000 trials for your second question yields ~1.266. 

So the two answers are very close, though I suspect they should not ever be equal.  If you consider the case where the number of events is smaller than the number of kingdoms, it's clear that the number of e/l per kingdom will depend on the number of kingdoms.  That should carry over to the case we're looking at here, though the effect would be much smaller.

Thanks, but actually I need to know how to calculate the average based on any number of L/E and any number of cards. (I should have made that clear.) At least now I know what the result of the formula should be for this example.

For the second question, you're right. The number would be smaller than x, at least when the number of kingdoms is larger than a certain number compared to the number of L/E.

Jimmmmm

  • Torturer
  • *****
  • Online Online
  • Posts: 1762
  • Shuffle iT Username: Jimmmmm
  • Respect: +2017
    • View Profile
Re: Math is hard - questions about chance
« Reply #4 on: March 28, 2017, 05:02:46 pm »
0

Pr(0) = (275*...*266)/(330*...*321) ~ 15.7%
Pr(1) = 55*10*(275*...*267)/(330*...*321) ~ 32.5%
Pr(2) ~ 100-15.7-32.5 = 51.8%

Ave ~ 0.325+2*0.518 = 1.361

Not sure why my answer is different to ben_king's...
« Last Edit: March 28, 2017, 06:30:29 pm by Jimmmmm »
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1788
    • View Profile
Re: Math is hard - questions about chance
« Reply #5 on: March 28, 2017, 05:42:17 pm »
+2

First question:

The cap of 2 Events or Landmarks per kingdom actually makes this easier. Consider drawing 10 cards then looking to see if you have 0, 1, 2, etc. events/landmarks. If you've drawn 0, you are done. If you have exactly one event/landmark, draw one more card. If it's an event/landmark, you max out at 2; if it's not, you've filled the kingdom and have 1. If you have drawn 2 or more, you max out at 2 and discard all events/landmarks until you fill out the 10 cards for the kingdom.

Let t = number of kingdom cards (not including events and landmarks) and let w = number of events and landmarks. (I am thinking "tall"/portrait orientation cards and "wide"/landscape orientation cards)

The expected number of events or landmarks in a 10 card kingdom is equal to ....
        0 TIMES Probability of drawing 10 tall cards
PLUS 1 TIMES Probability of drawing 9 tall cards and 1 wide card, then 1 more tall card
PLUS 2 TIMES Probability of drawing 9 tall cards and 1 wide card, then 1 more wide card
PLUS 2 TIMES Probability of drawing at most 8 tall cards

In math, that becomes:
       0 * C(t,10)*C(w,0)/C(t+w,10)
    + 1 * C(t,9)*C(w,1)/C(t+w,10) * (t-9)/(t+w-10)
    + 2 * C(t,9)*C(w,1)/C(t+w,10) * (w-1)/(t+w-10)
    + 2 * (1 - C(t,10)*C(w,0)/C(t+w,10) - C(t,9)*C(w,1)/C(t+w,10))

Simplifying, the expected number of event or landmarks is
       2 - 2 * C(t,10)/C(t+w,10) - C(t,9)*w/C(t+w,10) * (t-9)/(t+w-10)

For t = 330 275 and w = 55 we get approximately 1.273 1.416.

C(n,k) is "n choose k".

--

Note: When sampling n cards without replacement from a deck with two types (of size t and w), the probability of drawing exactly k of the first type is C(t,k)*C(w,n-k)/C(t+w,n).

Edit: Correct number of kingdom cards not including landmarks and events is evidently 275. Also, the probability on the last line, probability of at most 8 tall cards, is just 1 minus probability of exactly 10 tall cards minus the probability of exactly 9 tall cards, as Mic mentions below. That shortcut is what the formula above reflects.
Edit 2: Simplified formula.
« Last Edit: March 29, 2017, 09:13:29 pm by Polk5440 »
Logged

Jeebus

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2515
  • Shuffle iT Username: jeebus
  • Respect: +1635
    • View Profile
Re: Math is hard - questions about chance
« Reply #6 on: March 28, 2017, 05:43:43 pm »
0

Pr(0) = (275*...*266)/(330*...*321) ~ 15.7%
Pr(1) = 55*10*(275*...*267)/(330*...*321) ~ 32.5%
Pr(2) ~ 100-15.7-32.5 = 51.8%

Ave ~ 0.157+2*0.325 = 1.361

Not sure why my answer is different to ben_king's...

Trying to understand the formula... In any case, to get your result it should be:
Ave ~ 0.325+2*0.518 = 1.361

I'm not sure if you typed the formula wrong or wrote the wrong result.

Can you tell me why in Pr(0) you multiply 10 numbers, while in Pr(1) you just multiply 9 numbers? The second multiplication is with 10 numbers in both...

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1788
    • View Profile
Re: Math is hard - questions about chance
« Reply #7 on: March 28, 2017, 05:57:46 pm »
0

Next question:

Say that the number from the first question is x. Say that we select a number of kingdoms, let's say 8 kingdoms, and no cards (including E/L) are allowed to be repeated across kingdoms. On average, how many L/E would show up in total? I think the answer is just x times 8, but I'm not sure.

I think we need more information here. What exactly happens to events/landmarks you pass over if you hit the cap of 2 in a kingdom? Discarded or mixed back in for drawing of the second kingdom?
Logged

Jeebus

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2515
  • Shuffle iT Username: jeebus
  • Respect: +1635
    • View Profile
Re: Math is hard - questions about chance
« Reply #8 on: March 28, 2017, 06:16:55 pm »
0

First question:

The cap of 2 Events or Landmarks per kingdom actually makes this easier. Consider drawing 10 cards then looking to see if you have 0, 1, 2, etc. events/landmarks. If you've drawn 0, you are done. If you have exactly one event/landmark, draw one more card. If it's an event/landmark, you max out at 2; if it's not, you've filled the kingdom and have 1. If you have drawn 2 or more, you max out at 2 and discard all events/landmarks until you fill out the 10 cards for the kingdom.

Thanks! I understand you're formula, although I'm not smart enough to see if there's any mistake there. I now wonder how ben_king got his result.
Just a question to your remark about the cap making it easier: Without the cap, wouldn't it just be w/t*10?

I think we need more information here. What exactly happens to events/landmarks you pass over if you hit the cap of 2 in a kingdom? Discarded or mixed back in for drawing of the second kingdom?

Good question. The way I'm doing it is mixing them back in. I'm not sure which approach would be more in line with the official setup rule. I guess it would be the approach that gets us the closest to the average of the first kingdom. I mean, with w=55 and t=330 275, that average according to your formula is 1.361 1.416. That would be the average for the first kingdom in a series of unique kingdoms. So whichever approach that would get the following kingdoms closest to that seems like the correct one. I think that would be mixing them back in...? In any case, this problem seems pretty hard!
« Last Edit: March 28, 2017, 07:54:53 pm by Jeebus »
Logged

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1709
  • Respect: +4329
    • View Profile
Re: Math is hard - questions about chance
« Reply #9 on: March 28, 2017, 06:36:16 pm »
+3

I think ben_king's simulations are wrong.

Jimmmmm's Pr(1) is missing a factor (as you noticed) of (265/320) (266/320) because you still need to draw the 10th kingdom card without hitting a landscape. This will give an answer that agrees with Polk's.

Maybe you already know this, but Polk's t is just the number of kingdom cards, not the total, so if you're interested in the 275 kingdom, 55 landscape case, t needs to be 275. This will give an average number of landscapes of ~1.416. I did sim this as well and got ~1.416.
« Last Edit: March 28, 2017, 07:19:05 pm by Mic Qsenoch »
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1788
    • View Profile
Re: Math is hard - questions about chance
« Reply #10 on: March 28, 2017, 06:44:15 pm »
0

Maybe you already know this, but Polk's t is just the number of kingdom cards, not the total, so if you're interested in the 275 kingdom, 55 landscape case, t needs to be 275. This will give an average number of landscapes of ~1.416. I did sim this as well and got ~1.416.

Lol. That's  correct. I guess I am already anticipating the next expansion! ... or I just don't know how many cards there are anymore!

« Last Edit: March 28, 2017, 06:45:44 pm by Polk5440 »
Logged

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1709
  • Respect: +4329
    • View Profile
Re: Math is hard - questions about chance
« Reply #11 on: March 28, 2017, 06:54:21 pm »
+1

Also in case you didn't know, you don't have to calculate Polk's formulas for the 2 landscape case, just take 1 - Pr(0) - Pr(1) like Jimmmmm did.
Logged

Jimmmmm

  • Torturer
  • *****
  • Online Online
  • Posts: 1762
  • Shuffle iT Username: Jimmmmm
  • Respect: +2017
    • View Profile
Re: Math is hard - questions about chance
« Reply #12 on: March 28, 2017, 07:13:29 pm »
+1

In any case, to get your result it should be:
Ave ~ 0.325+2*0.518 = 1.361

Whoops! Thanks, fixed.

Quote
Can you tell me why in Pr(0) you multiply 10 numbers, while in Pr(1) you just multiply 9 numbers? The second multiplication is with 10 numbers in both...

Yep, so the probability of having no Events or Landmarks is 275/330 for the first one, times 274/329 for the second one etc.

For one E/L, the 266 numerator is replaced by 55, since one of the 10 is an E/L. So in answer to your question, the 55 outside the brackets is one of the 10 numbers, which is why there are only 9 in the brackets. It's also multiplied by 10 since there are 10 ways to have an E/L in the first 10.
Logged

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1709
  • Respect: +4329
    • View Profile
Re: Math is hard - questions about chance
« Reply #13 on: March 28, 2017, 07:21:21 pm »
+1

Can you tell me why in Pr(0) you multiply 10 numbers, while in Pr(1) you just multiply 9 numbers? The second multiplication is with 10 numbers in both...

Yep, so the probability of having no Events or Landmarks is 275/330 for the first one, times 274/329 for the second one etc.

For one E/L, the 266 numerator is replaced by 55, since one of the 10 is an E/L. So in answer to your question, the 55 outside the brackets is one of the 10 numbers, which is why there are only 9 in the brackets. It's also multiplied by 10 since there are 10 ways to have an E/L in the first 10.

You still need to account for drawing 10 kingdom cards, to ensure that you only draw 1 landscape. You need an additional factor (266/320).
Logged

Jimmmmm

  • Torturer
  • *****
  • Online Online
  • Posts: 1762
  • Shuffle iT Username: Jimmmmm
  • Respect: +2017
    • View Profile
Re: Math is hard - questions about chance
« Reply #14 on: March 28, 2017, 07:41:38 pm »
0

I think ben_king's simulations are wrong.

Jimmmmm's Pr(1) is missing a factor (as you noticed) of (265/320) because you still need to draw the 10th kingdom card without hitting a landscape. This will give an answer that agrees with Polk's.

Huh, you're right. It's not enough to have exactly 1 in the first 10, you also need the 11th card to not be one.
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1788
    • View Profile
Re: Math is hard - questions about chance
« Reply #15 on: March 28, 2017, 07:46:31 pm »
+1

Just a question to your remark about the cap making it easier: Without the cap, wouldn't it just be w/t*10?

I don't think so, no. 55/330*10=1.67 would be with replacement (you can draw the same card twice) and drawing exactly 10 cards (not 10 necessarily tall cards).

Also, sorry for the confusion, I was using t for the number of cards not including events and landmarks (not the total number of cards including events and landmarks). Mic has corrected me on the number above.
Logged

Jimmmmm

  • Torturer
  • *****
  • Online Online
  • Posts: 1762
  • Shuffle iT Username: Jimmmmm
  • Respect: +2017
    • View Profile
Re: Math is hard - questions about chance
« Reply #16 on: March 28, 2017, 08:01:00 pm »
0

Jimmmmm's Pr(1) is missing a factor (as you noticed) of (265/320) (266/320) because you still need to draw the 10th kingdom card without hitting a landscape. This will give an answer that agrees with Polk's.

It doesn't though. It reduces the chance of 1, but increases the chance of 2, so it increases the average. Now I'm getting 1.416.
Logged

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1709
  • Respect: +4329
    • View Profile
Re: Math is hard - questions about chance
« Reply #17 on: March 28, 2017, 08:24:36 pm »
0

Jimmmmm's Pr(1) is missing a factor (as you noticed) of (265/320) (266/320) because you still need to draw the 10th kingdom card without hitting a landscape. This will give an answer that agrees with Polk's.

It doesn't though. It reduces the chance of 1, but increases the chance of 2, so it increases the average. Now I'm getting 1.416.

Which exactly agrees with Polk's, his post has been edited after a clarification from me  :)
Logged

Jimmmmm

  • Torturer
  • *****
  • Online Online
  • Posts: 1762
  • Shuffle iT Username: Jimmmmm
  • Respect: +2017
    • View Profile
Re: Math is hard - questions about chance
« Reply #18 on: March 28, 2017, 08:33:31 pm »
0

Jimmmmm's Pr(1) is missing a factor (as you noticed) of (265/320) (266/320) because you still need to draw the 10th kingdom card without hitting a landscape. This will give an answer that agrees with Polk's.

It doesn't though. It reduces the chance of 1, but increases the chance of 2, so it increases the average. Now I'm getting 1.416.

Which exactly agrees with Polk's, his post has been edited after a clarification from me  :)

Ah okay, cool.
Logged

Jeebus

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2515
  • Shuffle iT Username: jeebus
  • Respect: +1635
    • View Profile
Re: Math is hard - questions about chance
« Reply #19 on: March 28, 2017, 08:56:23 pm »
+1

To get the second kingdom, I did the formula for the three scenarios of the first kingdom (10 t used, 10 t and 1 w used, 10 t and 2 w used) and multiplied these results with the chance of each of them occurring (15.7%, 27.0%, 57.3%), and then got 1.424. So a slightly higher average E/L count for the second kingdom. This assumes you mix in any E/L drawn above 2.

For the 3rd kingdom you have 5 scenarios though (0, 1, 2, 3 and 4 w used). And so on. I wonder if there is a formula that would work.

Mic Qsenoch

  • 2015 DS Champion
  • *
  • Offline Offline
  • Posts: 1709
  • Respect: +4329
    • View Profile
Re: Math is hard - questions about chance
« Reply #20 on: March 28, 2017, 09:09:55 pm »
+3

To get the second kingdom, I did the formula for the three scenarios of the first kingdom (10 t used, 10 t and 1 w used, 10 t and 2 w used) and multiplied these results with the chance of each of them occurring (15.7%, 27.0%, 57.3%), and then got 1.424. So a slightly higher average E/L count for the second kingdom. This assumes you mix in any E/L drawn above 2.

For the 3rd kingdom you have 5 scenarios though (0, 1, 2, 3 and 4 w used). And so on. I wonder if there is a formula that would work.

I have been messing around with this as well, I wrote a small program to calculate your second question.

The average number of landscapes goes up because you remove a larger amount of kingdom cards from the available pool (10 vs ~1.416). I guess a complete answer is more complicated than that.

Across 8 games you get an average of ~11.593 total landscapes (compared to 11.328 for the easy approximation). I don't actually know if my program is correct, though the 8 game result is reasonable and it also reproduces your result for ~2.84 as the average total over 2 games.

I don't know if there's a relatively simple formula, I wouldn't be able to figure one out.
« Last Edit: March 28, 2017, 09:11:50 pm by Mic Qsenoch »
Logged

ben_king

  • Golem
  • ****
  • Offline Offline
  • Posts: 190
  • Shuffle iT Username: ben.king
  • formerly grsbmd
  • Respect: +612
    • View Profile
Re: Math is hard - questions about chance
« Reply #21 on: March 29, 2017, 08:51:30 am »
0

I think ben_king's simulations are wrong.

Jimmmmm's Pr(1) is missing a factor (as you noticed) of (265/320) (266/320) because you still need to draw the 10th kingdom card without hitting a landscape. This will give an answer that agrees with Polk's.

Maybe you already know this, but Polk's t is just the number of kingdom cards, not the total, so if you're interested in the 275 kingdom, 55 landscape case, t needs to be 275. This will give an average number of landscapes of ~1.416. I did sim this as well and got ~1.416.

Ah, I had assumed that the 330 cards did not include landscapes.  Once I adjust that, this is the number that the simulation gives as well.  Though, the result I get for the second question is no longer as close to the first answer.  I now get ~1.408 as the answer for the second question.
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1788
    • View Profile
Re: Math is hard - questions about chance
« Reply #22 on: March 29, 2017, 06:23:41 pm »
0

I now get ~1.408 as the answer for the second question.

This is not correct. I confirm Mic's calcs.

Across 8 games you get an average of ~11.593 total landscapes (compared to 11.328 for the easy approximation).

I iterated the formula above to confirm this. Straightforward program, but not a straightforward resulting formula to do by hand.

Quote
reproduces your result for ~2.84 as the average total over 2 games.

I confirm this, too.

More details:

Code: [Select]
Prob of 0 wide cards is 4.462e-08
Prob of 1 wide cards is 7.852e-07
Prob of 2 wide cards is 8.423e-06
Prob of 3 wide cards is .00006193
Prob of 4 wide cards is .00034865
Prob of 5 wide cards is .00154516
Prob of 6 wide cards is .00556432
Prob of 7 wide cards is .01641124
Prob of 8 wide cards is .04006905
Prob of 9 wide cards is .08080099
Prob of 10 wide cards is .1345347
Prob of 11 wide cards is .18262003
Prob of 12 wide cards is .19971533
Prob of 13 wide cards is .17028032
Prob of 14 wide cards is .10912924
Prob of 15 wide cards is .04719838
Prob of 16 wide cards is .01171141

Expected Number of wide cards is 11.592913
Logged

pacovf

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3499
  • Multiediting poster
  • Respect: +3838
    • View Profile
Re: Math is hard - questions about chance
« Reply #23 on: March 29, 2017, 07:53:42 pm »
0

Assuming you aren't putting the discarded landscape cards back in, the average number of landscape cards per kingdom does not depend on the number of kingdoms, unless you are somehow ensuring that you are drawing all the kingdom cards (shouldn't be possible, since it isn't a multiple of ten).

This follows from the (often discussed) result that digging for a card does not, on average, affect the distribution of the remainder of your deck (unless you only have one, or zero, remaining cards of that type in your deck). So digging for 10 kingdom cards doesn't affect the distribution of landscape/kingdom cards leftover in your randomizer deck.

Unless I am wrong, of course. EDIT: Actually, I see the problem with my argument. Just because the proportion of landscape to kingdom cards is constant doesn't mean that the average number of landscape cards drawn is the same. The average also changes with the total number of cards.



If you put the discarded landscape cards back in, then the average number of landscape cards will (smoothly?) transition from between the average for a single kingdom, to the average for all cards put together, but no idea what the actual formula is.
« Last Edit: March 30, 2017, 10:03:18 am by pacovf »
Logged
pacovf has a neopets account.  It has 999 hours logged.  All his neopets are named "Jessica".  I guess that must be his ex.
Pages: [1]
 

Page created in 0.063 seconds with 21 queries.