23

« **on:** November 16, 2017, 06:36:51 pm »
So the math about a deck of exactly $n$ labs and $n$ coppers is wrong. After playing around with this for awhile, it is $\Theta(\sqrt{n})$. Your argument that it is infinite in an infinite deck only implies that it is greater than $O(1)$, but not that it is necessarily $\Theta(n)$.

Here's a rough proof:

We can think of the ordering of the deck as a dyck path from $(0,0)$ to $(n,n)$, where going up represents drawing a lab, and going right represents drawing a copper. Falling below the diagonal is equivalent to terminating. 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)$.

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)$. This is because as long as $k$ is a little less than $n$, the draws are mostly independent, and thus look like a binomial distribution, which has standard deviation $\Theta(k)$. From the argument before about the whole deck, the probability that this intital segment is in the right order to draw all of it is $\Theta(1/k)$, which means the probability of drawing exactly $2k$ cards is $\Theta(1/k^{3/2)})$.

To find the EV, we thus sum up $\Theta(k/(k^{3/2}))$ for $k$ from 1 to $n$, to get $\Theta(\sqrt(n))$

I have also found explicit values up to $n=5000$ and they are definitely growing with $\sqrt{n}$