Dominion Strategy Forum

Please login or register.

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

Author Topic: Treasure Map Probabilty (Can also be applied to other cards)  (Read 15314 times)

0 Members and 1 Guest are viewing this topic.

david707

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +20
    • View Profile
+2

In this article: http://dominionstrategy.com/2011/03/09/basic-opening-probabilities/
theory asked "...probability each deck cycle of activating Treasure Maps, assuming n Treasure Maps and p cards in the deck".
In my workings, I've assumed that you have t Treasure maps and n cards in total. It is also assumed n is divisible by 5 for simplicities sake. The probability below is that in at least one hand you have at least 2 treasure maps, it is also one minus the probability of every treasure map being in a different hand. It also assumes you don't have draw cards like lab or Village/Smithy, but you can represent great halls and other +1 Action +1 Card Kingdoms by not counting them when counting the number of cards in your deck.

The answer:


This can be applied to other cards as well, for example, you could make t the number of terminal actions you have and see what the chances are of drawing two together.

Workings:
Involves some pretty advanced mathematics and I expect only a few people will understand the derivation. Basically, I'm too lazy to post them, but if someone requests I will.

If you have any probability questions you would like answered (relating to Dominion), then please say.

Logged

theory

  • Administrator
  • *****
  • Offline Offline
  • Posts: 3603
  • Respect: +6121
    • View Profile
    • Dominion Strategy
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #1 on: June 13, 2011, 07:48:53 pm »
0

Well, I would like to see the derivation, just to see how over my head it is :)

Say t = 2 and n = 10, 15.  What is p?

Could you graph that as well?  Graph n vs p, and have different curves for each t.
Logged

timchen

  • Minion
  • *****
  • Offline Offline
  • Posts: 704
  • Shuffle iT Username: allfail
  • Respect: +234
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #2 on: June 13, 2011, 07:52:28 pm »
0

Sorry, but I lol'ed when I saw you said that the math is pretty advanced. :p No offense intended, but I think stuff like Truerank is quite a bit more advanced than that.
Logged

theory

  • Administrator
  • *****
  • Offline Offline
  • Posts: 3603
  • Respect: +6121
    • View Profile
    • Dominion Strategy
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #3 on: June 13, 2011, 07:56:03 pm »
0

There are different kinds of advanced ... what MIT mathematicians find simple might not be so simple for lowly lawyers :P
Logged

timchen

  • Minion
  • *****
  • Offline Offline
  • Posts: 704
  • Shuffle iT Username: allfail
  • Respect: +234
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #4 on: June 13, 2011, 08:04:51 pm »
0

The problem is to count how many ways there are without more than 1 treasure map in a hand. When t<=n/5, you choose t "bins" out from the n/5 bins to put in the treasure map, and for each bin there are 5 ways to put it. This gives 5^t C(n/5,t). Divide this with the total number of ways to arrange the draw, which is C(n,t), you get the answer.
Logged

Teproc

  • Jester
  • *****
  • Offline Offline
  • Posts: 765
  • Shuffle iT Username: Teproc
  • aka Le Teproc
  • Respect: +356
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #5 on: June 13, 2011, 08:06:14 pm »
0

For example, as a political sciences student, I don't understand this result, and much less so the math involved to find it.

What does this result actually amounts to, basically ?
Logged
Mafia play advice: If you are not content with the way the game is going, always assume that it is your fault.

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #6 on: June 13, 2011, 08:53:17 pm »
0

Of course, this only works for n mod 5 = 0, which leaves out a heck of a lot of possibilities.

Teproc:  the exclamation points in the formula represent the factorial function.  That's the product of all whole numbers from the number down; so, for 5, it's 5 × 4 × 3 × 2 × 1 = 120.  Because the way the OP has this set up results in huge factorials (15! has 13 digits), it helps to break it down and cancel things out a bit.  For theory's question, t = 2, n = 15, we have:

n/5 = 3
5t = 25

The first factorial on top is 3!, and the first on the bottom is 1!.  Divide those and you get 3 × 2 = 6
The second factorial on top is 13!, and the second on the bottom, n!, is 15!.  Divide them, and you get 15 × 14 = 210 (on the bottom).

Simplified, then, the fraction is (6 × 25)/(210) = 0.714

Therefore, p (the chance of getting 2 Maps this cycle) is 0.286, or about 29%.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

Teproc

  • Jester
  • *****
  • Offline Offline
  • Posts: 765
  • Shuffle iT Username: Teproc
  • aka Le Teproc
  • Respect: +356
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #7 on: June 13, 2011, 09:47:35 pm »
0

Very interesting, thanks for the clarification.

29% is a bit more than I expected, but it sounds about right in that it confirms that you should probably never buy it without heavy trashing or some other kind of enabler (e.g Warehouse, Haven).
Logged
Mafia play advice: If you are not content with the way the game is going, always assume that it is your fault.

david707

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +20
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #8 on: June 14, 2011, 05:56:07 pm »
0

The problem is to count how many ways there are without more than 1 treasure map in a hand. When t<=n/5, you choose t "bins" out from the n/5 bins to put in the treasure map, and for each bin there are 5 ways to put it. This gives 5^t C(n/5,t). Divide this with the total number of ways to arrange the draw, which is C(n,t), you get the answer.

Well explained, when I said the maths was pretty advance, I learnt how to do that sort of thing at degree level and assumed most people on the forum aren't degree level mathematicians.

Of course, this only works for n mod 5 = 0, which leaves out a heck of a lot of possibilities.
I did do a more complex formula assuming that you draw you last few cards and nothing else, but that doesn't happen in dominion. The question was per deck cycle, so when you draw those last few cards you shuffle anyway.

A nice table:


And a graph:


Edit: t=9 and t=10 were not included in the graph, both appear as straight lines at 1.
« Last Edit: June 14, 2011, 05:57:46 pm by david707 »
Logged

rrenaud

  • Administrator
  • *****
  • Offline Offline
  • Posts: 991
  • Uncivilized Barbarian of Statistics
  • Respect: +1197
    • View Profile
    • CouncilRoom
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #9 on: June 14, 2011, 06:13:10 pm »
0

Even worse, we aren't British ;P.  From brief perusal of the internet, I think degree level is what Americans call undergraduate college education.
Logged

david707

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +20
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #10 on: June 14, 2011, 06:27:49 pm »
0

Even worse, we aren't British ;P.  From brief perusal of the internet, I think degree level is what Americans call undergraduate college education.

I probably should have said "University Level", which I think is the same in America and UK (Although I can imagine learning that kind of thing before Uni).
Logged

Axe Knight

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 170
  • Respect: +25
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #11 on: June 15, 2011, 11:13:38 pm »
0

I was a Mathematical Statistics major, and have tried to derive what you did, but got stuck.  Would love to see the workings of your proof.   :)
Logged
An Axe Knight draws near!  Command?

david707

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +20
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #12 on: June 16, 2011, 06:21:24 pm »
0

Okay, here are the workings:
The formula is 1 minus the probability of not matching any tmaps, so how do we work that out?
We need the number of ways to not match divided by the total number of ways to draw the deck.
The total number of ways (b) is easiest, b=n!/((n-t)!t!) (see http://en.wikipedia.org/wiki/Combination).
Now for the number of ways to not match, we need to draw something like this, where K represents a non tmap card:
{KKKKT,KKKKT,KKKKT,...,KKKKK,KKKKK,...}
Overall there will be t hands of KKKKT and (n/5)-t hands of KKKKK. Now it doesn't matter where the T is in the KKKKT hands, it can be in 5 different places in each hand, giving us 5^t. Also the hands don't have have to be in that order, their are (n/5)!/(t!((n/5)-t)!) orders to draw these hands, using combinations again. So the number of ways to not match (a) is a=((5^t)(n/5)!)/(t!((n/5)-t)!).
Finally we find a/b and the (t!)'s cancel, do 1 minus to get the required formula.
Logged

PetterTB

  • Chancellor
  • ***
  • Offline Offline
  • Posts: 24
  • Respect: +1
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #13 on: June 20, 2011, 07:06:04 am »
0

Even worse, we aren't British ;P.  From brief perusal of the internet, I think degree level is what Americans call undergraduate college education.

Does that match a bachelor at the university? A master?
Logged

david707

  • Baron
  • ****
  • Offline Offline
  • Posts: 51
  • Respect: +20
    • View Profile
Re: Treasure Map Probabilty (Can also be applied to other cards)
« Reply #14 on: June 20, 2011, 05:36:42 pm »
0

Even worse, we aren't British ;P.  From brief perusal of the internet, I think degree level is what Americans call undergraduate college education.

Does that match a bachelor at the university? A master?

Okay, I'll try and clear this up. I'm currently studying Mathematics at University and I'm reasonably confident university is the same in the UK and USA. I'm effectively doing a Bachelor's degree which also seems to be the same in the UK and USA.
Logged
Pages: [1]
 

Page created in 0.052 seconds with 21 queries.