(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.
MathLet 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,
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.
[]