Dominion > Dominion Articles

Dominion 101: What is an engine?

<< < (15/15)

trivialknot:

--- Quote from: mad4math on November 16, 2017, 06:36:51 pm ---Since there are ${2n \choose n}$ ways to shuffle the deck, and $C_n={2n \choose n}/(n+1)$ such paths that stay above the diagonal, so the propability of drawing the whole deck is $1/(n+1)$.
--- End quote ---
Oh, sweet, you found an explicit formula.  I'm not sure how you found C_n, but I guess once you have it you can just prove it by induction.


--- Quote from: mad4math on November 16, 2017, 06:36:51 pm ---Now consider the probability of drawing any particular number of cards $2k$. First, there must have been exactly $k$ labs and $k$ coppers before that point, and they must be in an order that lets you draw all of them. The probability of there being exactly $k$ of each is $\Theta(1/k)$.
--- End quote ---
Was this a typo where you meant $\Theta(1/\sqrt{k})$?  With this correction, I follow and agree with the rest of the argument.

So it appears that I was correct to say that the number of cards you draw diverges, but I was incorrect to say it was O(n).  That's funny, because earlier in the thread, people were wondering if there exists a "hybrid" deck where the number of cards you draw is more than Θ(1) but less than Θ(n).  The hybrid deck was right in front of us all along, in the form of an engine without overdraw.

mad4math:
Yes that was supposed to be $\Theta(1/\sqrt{k})$. C_n is just the catalan numbers.

ThetaSigma12:

--- Quote from: mad4math on November 21, 2017, 04:21:15 pm ---\Theta

--- End quote ---

What.

Navigation

[0] Message Index

[*] Previous page