bcsj.dk

I recently came upon a scenario described in the Magic: the Gathering subreddit, where a player had a situation in which the win or lose scenario was not obvious. It was a rather old post, but linked to recently in a question about indeterminable situations in Magic.

Comment from discussion Natedogg2’s comment from discussion "Does MTG Have Undecidable Game States?".

Comment from discussion Ostgar’s comment from discussion "I’m a Level 5 Judge. AMA.".

The question involves coin flipping and thus is probabilistic in nature, i.e. there is a chance that the player would win, but would it be guaranteed?

The scenario is as follows: The opponent is a 6 life and has Leonin Elder in play. Our player has Filigree Sages and Wirefly Hive in play and access to arbitrary amounts of mana. It is the opponents end step and for whatever reason our player will lose the game at the end of his next turn.

• 

• 

• 

Because our player has access to arbitrary amounts of mana, he may through Filigree Sages activate Wirefly Hive an arbitrary number of times. Each time Wirefly Hive is activated he flips a coin and if it comes up heads he gets a 2/2 creature token, which he can attack with next turn. If it comes up tails, he looses all the creature tokens again and will have to start over. This is fairly simple, he should just need 3 consecutive success to win, right? But there is a catch here.

The opponent had the Leonin Elder in play, which means their life total goes up by 1 every time one of the tokens is created by Wirefly Hive. Okay, so the 3 success would create 3 tokens netting him 3 life. We still can win from here. We will need 3 more tokens to counter act this life gain and the life gain from the additional tokens. So we actually needed 6 consecutive successes. Still another catch?

Every time we try for consecutive successes and fail to get enough the opponent gains more life points, thus each successive attempt will require more consecutive successes. I.e. every time we fail to win it gets harder to win. But we can repeat infinitely, shouldn’t we be guaranteed to win at some point?

Removing all the Magic lingo the problem becomes the following “simple” game:

There are two players $ A $ and $ B $. $ A $ starts with $ N $ points and $ B $ with 0 points. If at any time $ B $ has the same amount (or more) points than $ A $, then $ B $ wins. $ B $ may flip a coin and on heads $ B $ gains 2 points and $ A $ 1 point. On tails $ B $ looses all their points. What is the probability that $ B $ wins?

Here comes math.

We may model this problem using a stochastic process $ \{X_n\} $. $ X_n $ will be the state that our opponent is at $ n $ life. Then the probability of moving from state $ X_n $ to $ X_m $ is $ \mathcal P(X_m|X_n) $. In essence, we would flip a coin until a) we fail, or b) have enough consecutive successes to finish our opponent, which we model as moving to the state $ X_0 $. For example, if we are in state $ X_1 $, then there is 50% probability of succeeding a flip, which gains our opponent 1 life up to 2 and gives us a 2/2 creature that may win us the game, and 50% probability of us failing the flip, which leaves us in the current state. Note that in this state there is no rising difficulty.

Suppose we are in the state $ X_2 $, then the probabilities look like $$ \mathcal P(X_0|X_2) = 0.25, \quad \mathcal P(X_2|X_2) = 0.50, \quad \mathcal P(X_3|X_2) = 0.25, $$ and $ \mathcal P(X_i|X_2) = 0 $ for all other $ i $.

The full collection of transition probabilities $ p_{ij} = \mathcal P(X_i|X_j) $, $ i,j \in \mathbb N_0 = \{0,1,2,\dots\} $, is given by the formula $$ p_{ij} = \begin{cases} \frac1{2^j} & \text{if $ i=0$,} \\ \frac1{2^{i-j+1}} & \text{if $ 0<j\leq i < 2j $}\\ 0 & \text{otherwise}. \end{cases} $$

If there was only finitely many states we could describe our probability of being in any particular state as a vector, but since there is no upper limit, we can’t truly. However, we are not out of luck. Since the probability of getting to $ X_0 $ appear to be decreasing at higher states we can approximate the true process by a truncated one. We pick some $ N > 0 $ and say that $ X_N $ is the state where we lose the game. We will let $ \mathcal P(X_i|X_n) $ remain as before as long as $ i,n < N $. Then $$ \mathcal P(X_N|X_n) = 1 – \sum_{i=0}^{N-1}\mathcal P(X_i|X_n). $$ We may then define the transition matrix $ P_N $, which has the elements $$ (P_N)_{ij} = \begin{cases} p_{ij} & \text{if $ 0\leq i,j < N $}, \\ 1-\sum_{k=0}^{N-1}p_{kj} & \text{if $ i=N $ and $ j < N $}, \\ 1 & \text{if $ i=j=N $}, \\ 0 & \text{otherwise}. \end{cases} $$

For example, if $ N = 5 $ the matrix looks like this $$ P_5 = \begin{bmatrix} 1 & \frac12 & \frac14 & \frac18 & \frac1{16} & 0 \\ 0 & \frac12 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac12 & 0 & 0 & 0 \\ 0 & 0 & \frac14 & \frac12 & 0 & 0 \\ 0 & 0 & 0 & \frac14 & \frac12 & 0 \\ 0 & 0 & 0 & \frac18 & \frac7{16} & 1 \end{bmatrix}. $$ If $ N = 9 $, $$ P_9 = \begin{bmatrix} 1&\frac12&\frac14&\frac18&\frac1{16}&\frac1{32}&{\frac{1}{64}}&{\frac{1}{128}}&{\frac{1}{256}}&0 \\ 0& \frac12 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0&0&\frac12&0&0&0&0&0&0&0 \\ 0&0&\frac14&\frac12&0&0&0&0&0&0\\ 0&0&0 &\frac14&\frac12 & 0 & 0 & 0&0&0\\ 0&0&0&\frac18&\frac14&\frac12 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 &\frac18&\frac14&\frac12&0&0&0\\ 0&0 &0&0&\frac1{16}&\frac18&\frac14&\frac12&0&0 \\ 0&0&0&0&0&\frac1{16}&\frac18&\frac14&\frac12&0 \\ 0&0&0&0&0&\frac1{32}&{\frac{7}{64}}&{\frac{31}{128}}&{\frac{127}{256}}&1 \end{bmatrix}. $$

By picking a starting state $ X_\ell $, which is represented by a vector $ \mathbf v_\ell $ with elements 0 except for the $ \ell $’th element (counting from 0), which is 1, and multiplying the vector by the matrix $ P_N $ repeatedly,

$$ P_N^k\mathbf v_\ell = \overbrace{P_N\cdot P_N \cdots P_N}^{\text{$ k $ times}}\mathbf v_\ell = \mathbf w, $$

we get the probability of ending up in any particular state. By increasing $ N $ and $ k $ until $ \mathbf w = (w_0,w_1,\dots,w_N) $ stabilizes (in a certain sense) we may find a quite accurate probability of us winning from any given state.

For instance, for the scenario described in the beginning, $ \ell = 6 $, the probability of winning would be just under 4.7%, while the likelihood of getting caught in a spiral of the opponent gaining life is the remaining 95.3%.

The above was obtained by taking $ N = k = 50 $, which yields the result 4.685865122%, and increasing to $ N = k = 100 $ only adds $ 8\times 10^{-9} $% to this probability.

As a final note, since in official Magic: the Gathering rules one can only shortcut a loop by stating that it will be repeated some $ n $ times, not until a given condition or state is satisfied, the official ruling would be to try to play out the coin flips and if it doesn’t succeed in the first couple of tries you would have to yield the match or likely lose the match due to slow play warnings.

I sidste indlæg skrev jeg, at vi som det næste ville følge op på differentiation af polynomier, og vise at reglen $$ (x^p)’ = px^{p-1} $$ holdt for generelle $$ p \in \mathbb{R} $$. Vi tager dog lige et sidespring først og vender tilbage til en af resultaterne, som vi blot brugte uden at tænke nærmere over det sidste gang. $$! (a+b)^n = \sum_{k=0}^n\binom{n}{k}a^{n-k}b^k, $$ hvor $$ a,b\in \mathbb{R} $$ og $$ n \in \mathbb{n} $$. Vi vil vise denne identitet.

Induktion

Siden vi gerne vil vise at identiteten holder for all naturlige tal $$ n $$, har vi faktisk uendeligt mange identiteter vi gerne vil vise. Det kan jo tage lang tid, hvis vi går til dem en for en, så vi vil bruge et trick; nemlig et induktionsbevis.

Princippet i induktion er ganske simpel. Vi viser første, at vores identitet holder for et lille $$ n $$, hvilket forhåbentlig ikke er så svært. Dette kaldes induktionsbasisen. Herefter vil vi antage at vores identitet holder for et ukendt $$ n $$ og så vise at i så fald må den også holde for $$ n + 1 $$. Dette kaldes induktionstrinnet.

Hvis vi nu vises at identiteten holder for fx $$ n = 2 $$ og dernest viser den anden del, så kan vi se, fordi $$ n = 2 $$ virkede, må $$ n+1 = 2+1 = 3 $$ også virke. Men så kan vi jo vælge $$ n = 3 $$, og derfor må det også virke for $$ n +1 = 4 $$; osv…. Det er som dominobrikker der vælter og altid tager den næste med. Således får vi at identiteten holder for alle naturlige tal $$ n $$.

Bevis

Så lad os komme i gang.

Induktionsbasis

Jeg foreslog $$ n =2 $$ i eksemplet herover, men $$ n = 1 $$ er faktisk nok her. Dog synes jeg, at det er fint, hvis vi tjekker begge dele. Vi for brug for følgende $$! \begin{aligned} \binom{n}{0} &= \frac{n!}{0!(n-0)!} = \frac{n!}{n!} = 1 \\ \binom{n}{n} &=\frac{n!}{n!(n-n)!} = \frac{1}{0!} = 1 \end{aligned}. $$
For $$ n = 1 $$ har vi $$! \begin{aligned}(a+b)^1 = a+b &= \sum_{k=0}^1\binom{1}{k}a^{1-k}b^k \\ &= \binom{1}{0}a^1b^0 + \binom{1}{1}a^0b^1 = a + b. \end{aligned} $$
For $$ n = 2 $$ har vi via kvadratsætningen $$! (a+b)^2 = a^2 + 2ab + b^2 = \binom{2}{0}a^2b^0 + 2a^1b^1 + \binom{2}{2}a^0b^2. $$ Det eneste vi bør tjekke er om $$ 2 = \binom{2}{1} = \frac{2!}{1!(2-1)!}$$? Hvilket vi klart ser!

Induktionstrin

Vi antager nu at identiteten faktisk holder for et naturligt tal $$ n $$. Det her er den svære del: Nu gælder der de følgende udledninger. Læg mærke til at i første linie benytter vi vores antagelse til at omskrive $$ (a+b)^n $$. $$! \begin{aligned} (a+b)^{n+1} &= (a+b)(a+b)^n = (a+b)\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k \\ &= a\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k + b\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k \\ &= \sum_{k=0}^n\binom{n}{k}a^{(n+1)-k}b^k + \sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k+1} \\ &= a^{n+1} + \sum_{k=1}^n\binom{n}{k}a^{(n+1)-k}b^k \\ &\qquad\quad\, + \sum_{k=0}^{n-1}\binom{n}{k}a^{n-k}b^{k+1} + b^{n+1} \\ &= a^{n+1} + \sum_{k=1}^{n}\binom{n}{k}a^{(n-1)-k}b^{k} \\ &\qquad\quad\, + \sum_{k=1}^n\binom{n}{k-1}a^{(n+1)-k}b^{k} + b^{n+1} \\ &= a^{n+1} + \sum_{k=1}^n\left[\binom{n}{k} + \binom{n}{k-1}\right]a^{(n+1)-k}b^{k} + b^{n+1} \\ &= \sum_{k=0}^{n+1}\binom{n+1}{k}a^{(n+1)-k}b^{k}. \end{aligned} $$
Dermed har vi vist at identiteten holder. I den sidste lighed brugte vi følgende identitet $$! \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}. $$ Den viser vi nu $$! \begin{aligned} \binom{n}{k} + \binom{n}{k-1} &= \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!} \\ &= \frac{n!}{(k-1)!(n-k)!}\left[\frac{1}{k} + \frac{1}{n-k+1}\right] \\ &= \frac{n!}{(k-1)!(n-k)!}\left[\frac{n+1}{k(n-k+1)}\right] \\ &= \frac{(n+1)!}{k!(n-k+1)!} \\ &= \frac{(n+1)!}{k!((n+1)-k)!} = \binom{n+1}{k} \end{aligned} $$ Vi brugte her nogle tricks; fx benyttede vi at $$ k! = k\cdot (k-1)! $$ og ligeledes $$ (n-(k-1))! = (n-k+1)! = (n-k+1)\cdot (n-k)! $$ til at kunne tage $$ (k-1)! $$ og $$ (n-k)! $$ ud af en parentes i første linie. Fra linie 3 til 4 lavede vi så det modsatte trick for at samle faktorerne igen.

Konklusion

Vi har hermed vist at identiteten holder for alle naturlige tal $$ n $$.

Differentiation er et regneredskab vi stifter bekendtskab med i gymnasiet i Danmark, og mange husker nok basale regler som at $$ x^n $$ differentieres til $$ nx^{n-1} $$. De fleste har formentlig selv observeret det ved at beregne differenskvotienten for fx $$ x^2 $$ og tage grænseværdien. Men det er bare et tilfælde, så hvordan sikrer vi os at det virker for dem alle? Vi vil her lave den lidt mere generelle udledning.

Positive heltalseksponenter

Vi lader $$ y = f(x) = x^n $$ hvor $$ n \in \mathbb{N} = \{1,2,3,\dots\} $$. Vi viser at $$ f'(x) = nx^{n-1} $$. Vi får brug for følgende: I) Vi skriver summer kompakt vha. sum-symbolet Sigma ($$ \Sigma $$), $$! \sum_{k=0}^n a_n = a_0 + a_1 + a_2 + \dots + a_n. $$ II) For en toledet størrelse $$ (a+b)^n $$ gælder $$! (a+b)^n = \sum_{k=0}^n\binom{n}{k}a^{n-k}b^k, $$ hvor $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$ er binomial koefficienten. III) Vi observerer at $$ \binom{n}{1} = n $$.

Da har vi $$! \begin{aligned} \Delta y &= (x+\Delta x)^n – x^n \\ &= \sum_{k=0}^n\binom{n}{k}x^{n-k}\Delta x^k -x^n\\ &= \sum_{k=1}^n\binom{n}{k}x^{n-k}\Delta x^k \\ \frac{\Delta y}{\Delta x} &= nx^{n-1} + \sum_{k= 2}^n \binom{n}{k}x^{n-k}\Delta x^{k-1} \\ \frac{dy}{dx} = \lim_{\Delta x\to 0} \frac{\Delta y}{\Delta x} &= nx^{n-1} + \underbrace{\lim_{\Delta x\to 0}\Delta x\sum_{k= 2}^n \binom{n}{k}x^{n-k}\Delta x^{k-2}}_{=0} \end{aligned} $$ $$! f'(x) = \frac{dy}{dx} = nx^{n-1}. $$ Dermed er vi færdige.

Negative heltalseksponenter

Vi lader nu $$ y = f(x) = x^{-n} $$ hvor $$ n \in \mathbb{N} = \{1,2,3,\dots\} $$ og $$ x \neq 0 $$. Vi viser nu at $$ f'(x) = -nx^{-n-1} $$. Da har vi $$! \begin{aligned} \Delta y &= (x+\Delta x)^{-n} – x^{-n} \\ &= \frac{1}{(x+\Delta x)^n} – \frac{1}{x^n} \\ &= \frac{x^n – (x+\Delta x)^n}{((x+\Delta x)x)^n} = -\frac{(x+\Delta x)^n-x^n}{((x+\Delta x)x)^n} \\ &= -\frac{nx^{n-1}\Delta x + \Delta x\sum_{k=2}^n\binom{n}{k}x^{n-k}\Delta x^{k-1}}{((x+\Delta x)x)^n}.\end{aligned} $$ Fra linie 2 til 3 sætter vi på fælles brøkstreg og fra linie 3 til 4 omskriver vi tælleren på samme måde som for positive heltal ovenover. $$! \begin{gathered} \frac{\Delta y}{\Delta x} = -\frac{nx^{n-1} + \Delta x\sum_{k=2}^n\binom{n}{k}x^{n-k}\Delta x^{k-2}}{((x+\Delta x)x)^n} \\ \frac{dy}{dx} = \lim_{\Delta x\to 0}\frac{\Delta y}{\Delta x} = -\frac{nx^{n-1}}{x^{2n}} = -nx^{-n-1}. \end{gathered} $$ Dermed er vi færdige.

Det vil sige… næsten færdige. Faktisk bør vi sikre os at $$ x+\Delta x \neq 0 $$. Siden $$ x \neq 0 $$ findes der tal mellem $$ 0 $$ og $$ |x| $$ og vi kan vælge $$ |\Delta x| $$ til at ligge der imellem. Så bliver $$ x+\Delta x $$ aldrig $$ 0 $$ og $$ \Delta x $$ kan gå mod $$ 0 $$ uden problemer.

Andre eksponenter…?

Reglen vi beskrev i starten holder helt generelt for $$ n $$. Ikke bare heltalseksponenter (forskellige fra $$ 0 $$), men også for reelle tal. Det vender vi tilbage til i den næste indlæg.