Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: [1] 2 3 4  All

Author Topic: A theorem about drawing and density  (Read 31934 times)

0 Members and 1 Guest are viewing this topic.

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
A theorem about drawing and density
« on: March 05, 2012, 05:02:16 am »
+7

(Inspired by the discussion in the Venture thread.)

Summary: Certain cards (such as Venture) perform a complex drawing procedure but do not return cards to your draw deck. This post shows that these cards do not change the expected density of any card (or type of card) in your draw deck unless you knew something about your deck order to begin with or you trigger a reshuffle.

Disclaimer: This is going to involve some math. This might be overkill. If you think so, I can only apologize for not being sufficiently convinced by intuition. If you're overly skeptical like me, read on!

Assumptions:
  • Everything within applies only when you do not trigger a reshuffle. Reshuffles make things more complicated. For technical reasons, I'll actually require that the drawing leaves at least 1 card remaining in your draw deck, but that's just because it doesn't make sense to talk about the density of an empty draw deck.
  • I assume that the drawing samples uniformly randomly from your draw deck. This is often equivalent to the shuffling that occurs in a real game, but it doesn't apply if you know what the top cards of your deck are, either because you sifted them or your opponent put something there. So if cards like Cartographer, Rabble, etc. are in play, then nothing in this post applies directly. If the drawing procedure reaches beyond the cards you know about (e.g. you're playing Farming Village after your opponent played Rabble, in which case you are guaranteed to discard all the cards Rabble put there and then you're in unknown territory), then the results may still be relevant.
  • I assume the card decides whether to continue drawing based only on the cards it has already drawn and does not put cards back on the deck. This is true for many cards, such as: Venture, Scrying Pool, Farming Village, Smithy, Swindler, etc. It is not true for a card like Courtyard.

Caveat: Density is a pretty crude measure of deck quality, and expected density even cruder. A more important number is the probability of getting $8 in hand, for instance. This is also much more difficult to get a handle on mathematically.

Math

Let D be the set of all cards in the draw deck. We require D to be non-empty.

A draw state (A,B) consists of a set A and a non-empty set B that partition D. Let S be the set of all draw states. i.e. S = {(A,B) : A U B = D, A /\ B = empty, B =/= empty}. (Note: I'll use /\ for set intersection.) We'll interpret A to mean the set of already-drawn cards and B to mean the set of remaining cards.

A draw policy is a function f : S -> {0,1}. The output 1 indicates to draw another card and 0 indicates to stop drawing. For example, for Venture,
  f(A,B) = 1 if A contains no treasure, 0 if A contains a treasure.

For a subset T of D, the remaining density function of T is
  d_T : S -> [0,1]
defined by
  d_T(A,B) = |B /\ T| / |B|.
For example, for Venture, you might be interested in letting T be the set of all treasure cards in your draw deck, and then d_T would indicate the proportion of cards in your draw deck that are treasures.

Theorem. Let f be a draw policy and let T be a subset of D. Suppose there is an integer N >= 1 such that
  f(A,B) = 0 whenever |B| <= N.
(In other words, we always stop drawing before emptying the draw deck.) Let (A_end, B_end) be the final draw state after drawing uniformly from D according to policy f. Then
  E[d_T(A_end, B_end)] = d_T(empty, D).
(In other words, the expected density isn't changed by drawing.)

Proof.

For all draw states (A,B), we prove
  E[d_T(A_end, B_end) | current state is (A,B)] = d_T(A,B)
by induction on b = |B|.

If r <= N, then f(A,B) = 0, so A_end = A and B_end = B, and the claim is trivial.
For r > N, if f(A,B) = 0, the claim is again trivial, so assume f(A,B) = 1.

Let c in B denote the drawn card. Then, using induction,
Code: [Select]
  E[d_T(A_end, B_end) | (A,B)]
    = sum_{c in B} E[d_T(A_end, B_end) | (A U {c}, B \ {c})] P[drawing c]
    = sum_{c in B} d_T(A U {c}, B \ {c}) / |B|
    = sum_{c in (B /\ T)} d_T(A U {c}, B \ {c}) / |B| + sum_{c in (B \ T)} d_T(A U {c}, B \ {c}) / |B|
    = [(|B /\ T| - 1) / (|B| - 1)] * [|B /\ T| / |B|]   +   [|B /\ T| / (|B| - 1)] * [(|B| - |B /\ T|) / |B|]
    = [|B /\ T| / (|B| - 1)] * [(|B /\ T| - 1) / |B|]   +   [|B /\ T| / (|B| - 1)] * [(|B| - |B /\ T|) / |B|]
    = [|B /\ T| / (|B| - 1)] * [(|B| - 1) / |B|]
    = |B /\ T| / |B|
    = d_T(A,B),
as we wanted. []
« Last Edit: March 05, 2012, 04:53:56 pm by blueblimp »
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #1 on: March 05, 2012, 04:29:41 pm »
+2

In the other thread, DG asked about an example with 3 estates and 2 coppers. This is a nice simple example that we can work out by hand, to increase confidence that the proof was correct. I'll write the order of the draw deck, then what's left remaining after the venture, then the treasure density of what's left.

EEECC -> C -> 1
EECEC -> EC -> 1/2
ECEEC -> EEC -> 1/3
CEEEC -> EEEC -> 1/4
EECCE -> CE -> 1/2
ECECE -> ECE -> 1/3
CEECE -> EECE -> 1/4
ECCEE -> CEE -> 1/3
CECEE -> ECEE -> 1/4
CCEEE -> CEEE -> 1/4

The average is
  (1 + 1/2 + 1/3 + 1/4 + 1/2 + 1/3 + 1/4 + 1/3 + 1/4 + 1/4)/10
  = (1 + 2 * 1/2 + 3 * 1/3 + 4 * 1/4)/10
  = (1 + 1 + 1 + 1)/10
  = 4/10
  = 2/5,
exactly what we started with.
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #2 on: March 05, 2012, 05:26:50 pm »
+4

Here's an intuitive viewpoint that might be helpful. Imagine drawing a single card from your deck and discarding/playing it. Intuitively, this (on average) does not change any densities of your draw deck, right? So definitely if you do this several times, it still won't change average densities. What I showed in the original post is just that, even if how many cards you eventually draw depends on the cards you draw, it still won't change average densities.
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: A theorem about drawing and density
« Reply #3 on: March 05, 2012, 11:24:19 pm »
0

Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

DG

  • Governor
  • *****
  • Offline Offline
  • Posts: 4074
  • Respect: +2624
    • View Profile
Re: A theorem about drawing and density
« Reply #4 on: March 06, 2012, 08:05:09 am »
0

I think the term density is unhelpful now. The mean card value is not changed. The distribution has changed. In the 3 estate, 2 copper example the remaining draw deck always has 1 copper remaining, a mean of 2 estates remaining, a most common number of estates remaining of 4, and a mean remaining card value of 2/5. Depending upon the specific value you are looking for (such as a mode or mean or maximum) the new distribution may result in the same value as the old distribution or not.

It's probably worth confirming for your layout of the coppers and estates that the 10 permutations each have 12 orderings which together provide the 120 possible orderings of the five cards.
« Last Edit: March 06, 2012, 08:39:05 am by DG »
Logged

DG

  • Governor
  • *****
  • Offline Offline
  • Posts: 4074
  • Respect: +2624
    • View Profile
Re: A theorem about drawing and density
« Reply #5 on: March 06, 2012, 08:49:20 am »
0

Quote
Here's an intuitive viewpoint that might be helpful. Imagine drawing a single card from your deck and discarding/playing it. Intuitively, this (on average) does not change any densities of your draw deck, right? So definitely if you do this several times, it still won't change average densities. What I showed in the original post is just that, even if how many cards you eventually draw depends on the cards you draw, it still won't change average densities.

This applies in certain situations for Dominion maths but it does not apply in others. It specifically does not apply when you make a drawing decision since then the current drawing event and any future drawing event are no longer independent. A cellar or market will not change the distribution of the draw deck but a venture or scrying pool will.
« Last Edit: March 06, 2012, 09:02:11 am by DG »
Logged

ecq

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 224
  • Respect: +162
    • View Profile
Re: A theorem about drawing and density
« Reply #6 on: March 06, 2012, 10:13:49 am »
0

I think having fewer than 5 cards in the draw pile is confusing things.  Let's assume you have 10 cards in the draw pile: 3 Estates, 7 Coppers.

Before playing Venture, the average value of a card is $1 * 7 / 10 = $0.7

Venture will draw 0-3 Estates followed by 1 Copper.  The number of shuffles placing a given number of Estates on top of the deck is: (number of ways to pick the number of estates from a set of 3) * (number of ways to pick a single Copper from a set of 7) * (the number of ways to shuffle the remaining cards)

For the 4 possible Venture draws, we need to calculate the number of shuffles that produce the given draw:

  • C -  1 * 7 * 9!
  • EC - 3 * 7 * 8!
  • EEC - 6 * 7 * 7!
  • EEEC - 6 * 7 * 6!

Sanity check:  There are 10! different ways to shuffle a deck of 10 cards.
1 * 7 * 9! + 3 * 7 * 8! + 6 * 7 * 7! + 6 * 7 * 6! = 3628800 = 10!

So, we've accounted for all the different shuffles producing any given venture draw.

Drawing C leaves an average coin value of $(6/9) in the draw pile.  EC leaves $(6/8).  EEC leaves $(6/7).  EEEC leaves $(6/6).

Multiply those values by the number of shuffles they appear in to get the sum of all possible coin values:

(6/9) * 1 * 7 * 9! + (6/8) * 3 * 7 * 8! + (6/7) * 6 * 7 * 7! + (6/6) * 6 * 7 * 6! = 2540160

Divide by the total number of shuffles to get the average coin value:
2540160 / 10! = $0.7

Whoa, exactly where we started.  Venture didn't change the average coin value in our draw pile at all.

There are at least 6 cards remaining in the draw pile and you'll only draw 5 next turn.  We can go through and calculate it, but I'm confident that the expected value of the next hand hasn't changed by any metric.
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #7 on: March 06, 2012, 06:23:20 pm »
0

I think the term density is unhelpful now. The mean card value is not changed. The distribution has changed. In the 3 estate, 2 copper example the remaining draw deck always has 1 copper remaining, a mean of 2 estates remaining, a most common number of estates remaining of 4, and a mean remaining card value of 2/5. Depending upon the specific value you are looking for (such as a mode or mean or maximum) the new distribution may result in the same value as the old distribution or not.

It's probably worth confirming for your layout of the coppers and estates that the 10 permutations each have 12 orderings which together provide the 120 possible orderings of the five cards.

I agree with your observation that there are other values that can be more important than expected density. They are also harder to analyze. If someone can provide an analysis of some other value that suggests Venture is/isn't a next-turn sifter in general, then I'd be interested. It's beyond my abilities though.

Quote
Here's an intuitive viewpoint that might be helpful. Imagine drawing a single card from your deck and discarding/playing it. Intuitively, this (on average) does not change any densities of your draw deck, right? So definitely if you do this several times, it still won't change average densities. What I showed in the original post is just that, even if how many cards you eventually draw depends on the cards you draw, it still won't change average densities.

This applies in certain situations for Dominion maths but it does not apply in others. It specifically does not apply when you make a drawing decision since then the current drawing event and any future drawing event are no longer independent. A cellar or market will not change the distribution of the draw deck but a venture or scrying pool will.

This I don't agree with. First, independence is irrelevant for expected density because of linearity of expectation. If you're interested in something other than expectation, yes you'll need to worry about independence, so the analysis will be a lot harder. That's why I chose to calculate the expectation.

Second, a card like cellar/market DOES change the densities of the draw deck (but not expected densities). Consider a really simple example of 1 copper 1 estate in the draw deck. If you play a market, then you're either going to be left with a single copper or a single estate in the draw deck. Either way, the densities are different than you started with.

Is there fundamentally something different between market's effect on draw deck densities and venture's effect on draw deck densities? I don't know. All I've done is found one way in which they aren't different.

Oh, and, I'm not really sure what you mean by "distribution of the draw deck". I'm assuming you mean something like the distribution (over all possible cards you might draw) of the resulting densities in the draw deck.
« Last Edit: March 06, 2012, 06:26:55 pm by blueblimp »
Logged

DG

  • Governor
  • *****
  • Offline Offline
  • Posts: 4074
  • Respect: +2624
    • View Profile
Re: A theorem about drawing and density
« Reply #8 on: March 06, 2012, 10:56:53 pm »
0

Quote
Consider a really simple example of 1 copper 1 estate in the draw deck. If you play a market, then you're either going to be left with a single copper or a single estate in the draw deck. Either way, the densities are different than you started with.

The distribution of the second card hasn't changed. The card that was second in your deck had a 50% chance of being a copper and that's still the case after you've drawn the first one. Only when you use the information from the first card does the distribution of the second card change. In the case of a venture however you always have the information that you will draw a number of non-treasure cards and one treasure card, providing there is a treasure card in your deck.

Quote
Is there fundamentally something different between market's effect on draw deck densities and venture's effect on draw deck densities?

You're still talking about density, but what is it? You seem to be calculating it as the mean (across all possible orderings of the deck) of the mean card value. I certainly think you're finding some interesting stuff out but unless you're more specific it is hard to evaluate.
Logged

Razzishi

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 216
  • Shuffle iT Username: Eye Urn
  • Respect: +120
    • View Profile
Re: A theorem about drawing and density
« Reply #9 on: March 06, 2012, 11:24:28 pm »
+1

The assumption a random deck directly implies that the expected value of the density function is constant with respect to place in deck.  There's no need to say anything more. 
Logged
Stop reading my signature.

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #10 on: March 07, 2012, 12:41:28 am »
0

The assumption a random deck directly implies that the expected value of the density function is constant with respect to place in deck.  There's no need to say anything more.

Would you mind expanding on this? This was my intuition, but I wasn't able to formalize it in the case where the number of drawn cards varies depending on what's drawn (which is the case for Venture). To illustrate the difficulty, observe that the conditional expectation E[d_T(A_end, B_end) | |B_end| = r] is not constant in r! For example, if r=|D|-1, that means Venture drew exactly 1 card, so it was a treasure, which means the density decreased.

So... yeah. Basically I think it is necessary to say more.
Logged

RiemannZetaJones

  • Thief
  • ****
  • Offline Offline
  • Posts: 90
  • Respect: +62
    • View Profile
Re: A theorem about drawing and density
« Reply #11 on: March 07, 2012, 12:59:00 am »
+1

One problem is determining the expected number of hands drawn in the next t turns where the total money is greater than or equal to P, where P is generally either 8 or 11. Venture can decrease this number, e.g. in a deck with 2 Gold, 1 Silver and 19 Victory cards. I don't know if it can increase it without relying on the reshuffle.

edit: this is clearly false, since extra treasures are needed to pad the deck to avoid triggering a reshuffle in some cases. See below.
« Last Edit: March 07, 2012, 03:04:43 am by RiemannZetaJones »
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #12 on: March 07, 2012, 01:01:22 am »
0

Quote
Consider a really simple example of 1 copper 1 estate in the draw deck. If you play a market, then you're either going to be left with a single copper or a single estate in the draw deck. Either way, the densities are different than you started with.

The distribution of the second card hasn't changed. The card that was second in your deck had a 50% chance of being a copper and that's still the case after you've drawn the first one. Only when you use the information from the first card does the distribution of the second card change. In the case of a venture however you always have the information that you will draw a number of non-treasure cards and one treasure card, providing there is a treasure card in your deck.

Quote
Is there fundamentally something different between market's effect on draw deck densities and venture's effect on draw deck densities?

You're still talking about density, but what is it? You seem to be calculating it as the mean (across all possible orderings of the deck) of the mean card value. I certainly think you're finding some interesting stuff out but unless you're more specific it is hard to evaluate.

By density, I mean a value of the function d_T I defined by
  d_T(A,B) = |B /\ T| / |B|,
where A is the set of cards you drew, B is the set of cards remaining, and T is the set of cards you're interested in the density of. So, for example, you might let T be the set of all treasure cards in your draw deck, and then d_T would give the remaining treasure density after you draw the cards A. I'm not concerned with the value of the treasures--although you can handle that if you like by looking separately at the copper density, the silver density, the gold density, and so on, none of which change in expectation.

So, density is only defined for one particular outcome of drawing. When I say "densities", then I'm just talking about the densities for several different choices of T. e.g. You might choose T_1 to be the set of coppers in your draw deck and T_2 to be the set of actions in your draw deck. So then you would be looking at two different densities: one for copper and one for actions.

Density doesn't depend on draw deck ordering, only on which cards are present in the draw deck. That's good because the model treats cards as being randomly selected when they are drawn, rather than shuffling the deck up-front. It'd be possible to re-work everything in terms of up-front shuffles, but that is awkward.

Density alone is not too useful, though, because it's only defined for one outcome, and before you play Venture, you don't know which outcome you're going to get. So, that's why it's useful to look at expected density (or average density, which means the same thing, since expected value is just an average). In full, the wording could be "the expected value, over all possible orderings of your draw deck, of the density of your draw deck after playing card X".
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #13 on: March 07, 2012, 01:47:07 am »
0

One problem is determining the expected number of hands drawn in the next t turns where the total money is greater than or equal to P, where P is generally either 8 or 11. Venture can decrease this number, e.g. in a deck with 2 Gold, 1 Silver and 19 Victory cards. I don't know if it can increase it without relying on the reshuffle.

Interesting conjecture! This inspired a strong non-sifting result about Venture. Fully generalizing it requires a lot of assumptions, but I can sketch the basic idea easily.

Imagine that your deck consists only of green cards and basic treasures (for simplicity). Also, assume that, regardless of whether you play Venture, you will not reshuffle when drawing your next hand. (For example, this assumption is valid if you have at least 6 treasures in your draw deck. It's not true in the example you gave!) Then the probability of drawing any particular next hand does not depend on whether you play Venture. (This implies that playing Venture does not alter your probability of drawing $8 next turn!)

Proof sketch.

The idea is to construct a bijection between draw deck orderings. For every draw deck ordering that would have you draw some particular hand next turn if you played Venture, it will be bijected with a draw deck ordering that would have you draw that same hand next turn if you hadn't played Venture. Since every draw deck ordering is equally probable, this shows Venture does not alter the probability of drawing any particular hand next turn.

First consider a draw deck ordering when we play Venture. From top to bottom, the ordering consists of a (possibly empty) string of green cards G_1,...,G_k, followed by a single treasure T, followed by the 5 cards H_1,...,H_5 that will make up your next hand, followed by some other cards C_1,...,C_m. Diagram:
  G_1, G_2, ..., G_k, T, H_1, H_2, ..., H_5, C_1, C_2, ..., C_m.
For clarity, Venture will reveal and discard G_1,...,G_k and reveal and play T, then you will draw H_1,...,H_5 as your next hand.

Biject this with the following draw deck ordering, for the situation where we don't play Venture:
  H_1, H_2, ..., H_5, C_1, C_2, ..., C_m, T, G_1, G_2, ..., G_m.
Here, we don't play Venture, and draw H_1,...,H_5 as our next hand (the same as if we had played Venture with the other draw deck ordering).

The inverse of this bijection is simple, but there is something to note. The inverse just consists of taking a single treasure followed by a (possibly empty) string of greens off the bottom of the deck, then putting the treasure on top and then the greens. The thing to note is that the treasure-followed-by-string-of-greens will not overlap our next hand, because otherwise, there is a draw deck ordering where playing Venture would cause us to reshuffle when drawing our next hand.
Logged

michaeljb

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1422
  • Shuffle iT Username: michaeljb
  • Respect: +2113
    • View Profile
Re: A theorem about drawing and density
« Reply #14 on: March 07, 2012, 02:00:28 am »
+1

Not really related to the discussion happening now, just responding directly to the OP, but the main point is pretty similar to a guest article yaron wrote for the main site a while ago, you might be interested in checking it out (it was just the first thing I thought of once I read the summary):

http://dominionstrategy.com/2010/12/04/guest-article-the-fallacy-of-cycling/
Logged
🚂 Give 18xx games a chance 🚂

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #15 on: March 07, 2012, 02:52:35 am »
+1

Not really related to the discussion happening now, just responding directly to the OP, but the main point is pretty similar to a guest article yaron wrote for the main site a while ago, you might be interested in checking it out (it was just the first thing I thought of once I read the summary):

http://dominionstrategy.com/2010/12/04/guest-article-the-fallacy-of-cycling/

Fantastic, thanks very much. It's interesting to me that the article is somewhat spot-on (although it assumes an infinite deck and some of the things it says aren't true of finite decks), but then several people disagree in the comments.

Guy Srinivasan's post uses simulation to consider the effect of reshuffles, and finds that a card such as Loan or Venture can actually have a slight anti-sifting effect when reshuffles are taken into account. Very interesting. I'll need to spend some time on it to see why this is.

Tim attempts to show that even with no reshuffles, playing loan reduces the average proportion of gold in the draw deck--which is false. He gives an intuitive argument for this, but the intuition is wrong here. I think this illustrates why it's useful to be rigorous.

rrenaud agrees with Tim's argument, and gives an example with a 2-card draw deck (Estate + Gold) to support it. Unfortunately, since gold density is not well-defined for the case where loan draws and discards both cards in the draw deck, this is not a counterexample to Yaron's article. Even though it's not support for Tim's incorrect claim, rrenaud's example is useful in showing that when you might exhaust your draw deck, then the situation is complicated (which is why I assumed in my original post that at least 1 card would be left remaining in the draw deck).

Yaron aims to refute these counterarguments by assuming an infinite deck. While this might be a useful way of thinking in some games, it isn't necessary to assume an infinite deck, as I showed in my original post.

Guy Srinivasan gives a really cute intuitive argument in the infinite deck case, which I'll quote here:
Quote
The way I’ve always internalized the “draw until you see a Gold” is “have a boy”. If everyone has kids until they have their first boy, will there be more girls or boys born? Answer: it’s still 50%, of course, because no matter what at each stage of the game you’ve got a coinflip at each.

Ingix and DG derive a formula for the expected number of cards Loan will reveal: (N+1)/(T+1), where N is the total number of cards in the draw deck and T is the total number of treasures in the draw deck. DG gives an elegant proof:
Quote
The simplest explanation is probably to look at ‘slots’ between two treasure cards. In each slot there can be any number of the other cards from the deck, including none. All the other cards are included in these slots. How many slots are there? Well there is one slot before each treasure card and one slot after the last treasure card. This divides the other cards between T+1 slots, giving the N+1/T+1 result with a little algebra.
« Last Edit: March 07, 2012, 05:52:53 am by blueblimp »
Logged

bozzball

  • Bishop
  • ****
  • Offline Offline
  • Posts: 102
  • Respect: +68
    • View Profile
Re: A theorem about drawing and density
« Reply #16 on: March 07, 2012, 03:15:48 am »
+2

The easiest way I know to verify this in your mind is to consider the last card in the deck. After you have played your venture, the conditional probability (given what you have seen) that the last card is an estate is the density of estates in whatever cards are left. Thus, before you play your venture, the probability that the last card will be an estate is the expected value of the density afterwards.

This discussion is equivalent to the following classic brainteaser:
You have a 52 card (ordinary playing cards) deck. You are going to deal out cards from the deck 1-by-1. You have to say the word "Red" before you deal one of the cards. If that card is Red then you win a dollar, otherwise you lose a dollar. How can you maximize your probability of winning?
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #17 on: March 07, 2012, 03:22:43 am »
0

By the way, the Venture case is equivalent to:

Suppose you have an urn with W white balls and B black balls, where W,B >= 2. Perform the following procedure:
  • Draw a ball uniformly at random from the urn and discard it.
  • If the ball was white, go to step 1. If the ball was black, stop.
The expected final proportion of white balls in the urn is exactly W/(W+B), which was the initial proportion of white balls. (This is equivalent to playing Venture under the assumptions in the original post, so the same proofs work.)

Python code to simulate this if you want additional confidence:
Code: [Select]
import random

W = 20
B = 10

TRIALS = 10000
w_prop_sum = 0
for i in range(TRIALS):
  w = W
  b = B

  while 1:
    if random.uniform(0,1) < w/float(w+b):
      # Draw a white ball with probability w/(w+b) and discard it.
      w -= 1
    else:
      # Draw a black ball otherwise and discard it, then stop.
      b -= 1
      break

  w_prop = w / float(w+b)
  w_prop_sum += w_prop

initial_w_prop = W / float(W+B)
avg_final_w_prop = w_prop_sum / float(TRIALS)

print 'Ran %d trials.' % TRIALS
print 'Initial contents of the urn: %d white balls and %d black balls.' % (W,B)
print 'Initial proportion of white balls: %.4lf' % initial_w_prop
print 'Average final proportion of white balls: %.4lf' % avg_final_w_prop
« Last Edit: March 07, 2012, 03:26:55 am by blueblimp »
Logged

RiemannZetaJones

  • Thief
  • ****
  • Offline Offline
  • Posts: 90
  • Respect: +62
    • View Profile
Re: A theorem about drawing and density
« Reply #18 on: March 07, 2012, 03:31:19 am »
0


This inspired a strong non-sifting result about Venture. Fully generalizing it requires a lot of assumptions, but I can sketch the basic idea easily.

Imagine that your deck consists only of green cards and basic treasures (for simplicity). Also, assume that, regardless of whether you play Venture, you will not reshuffle when drawing your next hand. (For example, this assumption is valid if you have at least 6 treasures in your draw deck. It's not true in the example you gave!) Then the probability of drawing any particular next hand does not depend on whether you play Venture. (This implies that playing Venture does not alter your probability of drawing $8 next turn!)

Proof sketch.

The idea is to construct a bijection between draw deck orderings.

This is fantastic.
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: A theorem about drawing and density
« Reply #19 on: March 07, 2012, 04:05:52 am »
0


This inspired a strong non-sifting result about Venture. Fully generalizing it requires a lot of assumptions, but I can sketch the basic idea easily.

Imagine that your deck consists only of green cards and basic treasures (for simplicity). Also, assume that, regardless of whether you play Venture, you will not reshuffle when drawing your next hand. (For example, this assumption is valid if you have at least 6 treasures in your draw deck. It's not true in the example you gave!) Then the probability of drawing any particular next hand does not depend on whether you play Venture. (This implies that playing Venture does not alter your probability of drawing $8 next turn!)

Proof sketch.

The idea is to construct a bijection between draw deck orderings.

This is fantastic.

(This post made my day, by the way, thanks.)

This can be converted into an intuitive argument that's much easier to generalize. Just imagine that, instead of Venture taking cards from the top of the draw deck, it takes cards from the bottom; if we assume that we don't know the order of cards in the draw deck, this doesn't make any difference.

With this viewpoint, it's completely obvious that playing Venture doesn't change the probability of anything that happens up until the next reshuffle, barring special cases like Inn and Counting House that care about the contents of your discard pile.

(It's interesting to reconcile this viewpoint with your example of 2 golds, 1 silver and 19 victory cards. In that example, the reason Venture decreases your probability of getting $8 in the next t turns is only because it brings the reshuffle much closer. You reshuffle at the point when, in the alternative universe, you would have drawn the bottom-most treasure in your deck.)
« Last Edit: March 07, 2012, 04:11:23 am by blueblimp »
Logged

Davio

  • 2012 Dutch Champion
  • *
  • Offline Offline
  • Posts: 4787
  • Respect: +3412
    • View Profile
Re: A theorem about drawing and density
« Reply #20 on: March 07, 2012, 06:21:08 am »
0

I've skipped past most of the arguments that are way over my head (hey, my last math class was on the university 10 years ago!).

What I want to know and was unable to distill for sure is whether the skip ability of Venture is actually helpful or moot.
It's been shown that the money density doesn't change, so playing Ventures doesn't help future hands? Is this correct?

So the only "extra" we get from Venture is the ability to trigger multiple Ventures?


I have a similar question for Farming Village. Is the ability to skip moot or does it actually help the player when there's no interaction between players? Farming Villages find either action or treasure cards, so they're done searching even sooner. The main question is: Is Farming Village only better than a normal Village when e.g. Ghost Ship is in play or are there more benefits to this potential skipping?
Logged

BSG: Cagprezimal Adama
Mage Knight: Arythea

MasterAir

  • Alchemist
  • ***
  • Offline Offline
  • Posts: 39
  • Respect: +8
    • View Profile
Re: A theorem about drawing and density
« Reply #21 on: March 07, 2012, 07:03:11 am »
0

I think I'm convinced that it doesn't affect your next hand, I'm less convinced that it doesn't affect the hand(s) after that.  If you remove green cards from your draw deck and put them in your discard then you *do* increase the money density in your draw deck.  Of that I have absolutely no doubt.  You remove cards with $0 value and thus the average card value in your draw deck increases.  I'd guess that decks with ventures in typically have better longevity than pure money decks.
Logged

Deadlock39

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1722
  • Respect: +1757
    • View Profile
Re: A theorem about drawing and density
« Reply #22 on: March 07, 2012, 08:48:21 am »
+1

I've skipped past most of the arguments that are way over my head (hey, my last math class was on the university 10 years ago!).

What I want to know and was unable to distill for sure is whether the skip ability of Venture is actually helpful or moot.
It's been shown that the money density doesn't change, so playing Ventures doesn't help future hands? Is this correct?

So the only "extra" we get from Venture is the ability to trigger multiple Ventures?


I have a similar question for Farming Village. Is the ability to skip moot or does it actually help the player when there's no interaction between players? Farming Villages find either action or treasure cards, so they're done searching even sooner. The main question is: Is Farming Village only better than a normal Village when e.g. Ghost Ship is in play or are there more benefits to this potential skipping?

The key with Farming Village (which I think someone touched on in the Venture thread) is that it improves your current hand.  As covered by this discussion, Farming Village does not improve the expected value of your deck in future turns.  What it does do is guarantee it will not draw a victory card (or Curse) this turn.

DG

  • Governor
  • *****
  • Offline Offline
  • Posts: 4074
  • Respect: +2624
    • View Profile
Re: A theorem about drawing and density
« Reply #23 on: March 07, 2012, 09:03:14 am »
0

Quote
What I want to know and was unable to distill for sure is whether the skip ability of Venture is actually helpful or moot.It's been shown that the money density doesn't change, so playing Ventures doesn't help future hands? Is this correct?


When you calculate an average (mean) card value for a full deck then you're considering something like T/C, T= treasure and C= number of cards. When you add a farming village to the deck, T remains unchanged but you might see C decrease as green cards are discarded. Therefore T/C increases.


Edit - specified full deck rather than draw deck.
« Last Edit: March 07, 2012, 10:00:56 am by DG »
Logged

ecq

  • Conspirator
  • ****
  • Offline Offline
  • Posts: 224
  • Respect: +162
    • View Profile
Re: A theorem about drawing and density
« Reply #24 on: March 07, 2012, 09:39:10 am »
+1

Quote
What I want to know and was unable to distill for sure is whether the skip ability of Venture is actually helpful or moot.It's been shown that the money density doesn't change, so playing Ventures doesn't help future hands? Is this correct?


When you calculate an average (mean) card value for a draw deck then you're considering something like T/C, T= treasure and C= number of cards. When you play a farming village T remains unchanged but you might see C decrease when green cards are discarded. Therefore T/C increases.


T decreases by 1 (assuming Farming Village draws a treasure, not an action).  It's (T - 1) / (C - discarded_cards - 1).  If your draw pile is 5 Estates and a Copper, and the Copper was on top of the deck, you go from 1 / 6 to 0 / 5, so the second term can decrease.

For any given play, the money density will probably change slightly.  On average, though, the money density will remain equal to T / C.
Logged
Pages: [1] 2 3 4  All
 

Page created in 0.072 seconds with 20 queries.