Showing posts with label math. Show all posts
Showing posts with label math. Show all posts

Thursday, February 20, 2014

Opposed Checks in D&D are the Same as Coin Flips

This is a lesson in statistics and probability, as applied to the popular Dungeons and Dragons role playing game.  I'm having trouble lately with the LaTeX embedder: if you see a lot of dollar signs and slashes, then check your plugins and permissions on your browser and allow MathJax to work, so you can see the equations better.

At least since version 3.0, the Dungeons and Dragons rule book has featured a rule of opposed checks.  These are supposed to represent, using dice, the opposition of two separate skills: so, your ability to Hide versus the orc's ability to Spot; your ability to tie a rope versus the orc's ability to escape from bonds.  You roll your skill, the orc rolls his skill, you apply modifiers, and the higher outcome wins.

Even before this, rolling dice was a common way to set the difficulty of something in old versions and in other non-d20 games.  How hard is the door to force?  You didn't think of it, now you're on the spot, so you roll a die to figure out how hard it is.  Then you tell the PCs to beat that number on their own roll.  Makes sense.

Doing checks this way is, from a probabilistic point of view, about as good as flipping a coin. The probability of the PC winning is slightly more than 50-50.  I'll prove it.

When you roll a die, a number comes up.  A random number, hopefully.  If the dice has $n$ sides, then this number is between $1$ and $n$.  It is customary to denote a random number with a capital letter: in this case, I'm going to call $X$ the result of rolling the die; $X=1, 2, 3,\ldots, n$, depending on what we roll.

If we consider some number between $1$ and $n$, say 6, then the probability that $X=6$ is, as we all know, $1/n.$  It is common to write this as $\Pr(X=6) = \frac{1}{n}.$  And, of course, it isn't just for $X=6$ that this is the case, but for any number $x$ between $1$ and $n$.  More generally, for any such $x$, we write $\Pr(X=x) = \frac{1}{n}.$

In our case, we are going to roll the same die twice.  This gives us two random numbers (the results of the two dice), which we will call $X_1$ and $X_2.$  We'll say that $X_1$ is the die we roll, and $X_2$ is the die that the PC rolls.  We want to know $\Pr(X_2 \geq X_1)$, that is, the probability that the second result is higher than the first or, more concretely, the probability that the PC wins his contest against the orc.

This could go a number of ways.  The GM might roll a 1, in which case the PC is guaranteed to win, or the GM might roll a $n$, in which case the PC has to also roll $n$ or lose, with other possibilities in between.  But we don't want to consider the probability of the PC winning given some particular roll from the GM, because that's trivial.  So what we want to do instead is consider all of these possibilities.

We look at
$$\Pr(X_2\geq X_1) = \sum_{x=1}^n \Pr(X_2 \geq x) \cdot \Pr(X_1=x),$$
which means that we consider the probability of the GM rolling some number $X_1=x$, then multiply by the probability of the PC winning given this roll, then consider this for all the possible $x$ the GM might roll and add these together.  That gives us the probability of the PC winning his roll, regardless of what the GM rolls.

Breaking this down, we find
$$\Pr(X_2\geq X_1) = \sum_{x=1}^n \sum_{y=x}^n \frac{1}{n} \frac{1}{n} = \frac{1}{n^2}\sum_{x=1}^n\sum_{y=x}^n 1 = \frac{1}{n^2}\sum_{x=1}^n (n-x+1).$$
Stopping for a second, for people less familiar with this stuff, the $\sum_{y=x}^n$ term means that we add up every value of $X_2$, starting at $x$, and ending at $n$.  In a concrete example, if we're rolling a 6-sided die, and the first roll is $X_1=3$, then we add up contributions from $y=3,4,5,6,$; that's $4 = 6-3+1$ terms we consider.  More generally, it is $n-x+1$ terms, which is why we wrote $(n-x+1)$ there.  Moving on,
$$\Pr(X_2\geq X_1) = \frac{1}{n^2} \left(\sum_{x=1}^n n - \sum_{x=1}^n x + \sum_{x=1}^n 1\right) = \frac{1}{n^2}\left(n^2 - \sum_{x=1}^n x + n\right).$$
The term $\sum_{x=1}^n x$ means the sum of the first $n$ numbers.  So,
$$\sum_{x=1}^n = 1 + 2 + 3 + 4 + 5 + \cdots + n.$$
Those who've had Calculus will be familiar with this, but other people maybe no so much.  There's a beautiful formula due to Gauss, arguably the first person to discover it, whose proof is even more beautiful.  Consider the following image:

This shows a bunch of stacks of squares, increasing from 1 to 2 to 3, on up to $n$.  The area of these squares is $\sum_{x=1}^n x.$  Now consider a second one of exactly the same size: the two interlock, forming a rectangle:

The width of the rectangle is $n$ and the height is $n+1$, so its areas is $n(n+1)$.  But the area of the rectangle is equal to twice the area of the stacked squares!  Therefore,
$$\sum_{x=1}^n x = \frac{n(n+1)}{2}.$$

So then, carrying on with our equation, we now have
$$\Pr(X_2 \geq X_1)  = \frac{1}{n^2}\left(n^2 - \frac{n(n+1)}{2} + n\right) = 1 - \frac{n+1}{2n} + \frac{1}{n} = \frac{2n - n - 1 + 2}{2n} = \frac{n+1}{2n},$$
which, as I said, is slightly better than 50% probability.  For a 6-sided die, it is $\frac{7}{12}.$  For a 20-sided die, it is $\frac{21}{40}$, which corresponds almost exactly to a DC of 10 (because a roll equal to 10 still counts as a success).  So rolling an opposed roll for the orc is the same as considering the orc's passive check.

For dice, the result is not quite $1/2$ because the rolls can only equal certain specific results (like 1, or 7), but in a general case, it is actually true that the probability of a second random number being larger than the first random number is exactly $1/2$: that is, $\Pr(X_2>X_1) = \frac{1}{2}.$  I'll prove it.

So, consider  $X_1, X_2$, which are still random numbers, but not necessarily from a die.  For instance, we might push blocks on ice, and $X_2$ and $X_1$ gives the distance the blocks travel before coming to rest.  Or throw darts at a wall and $X_2,X_1$ are the distances from a bullseye.  Or something.  It's also not necessarily that case that every possible value is equally likely.  For a fair die, every number has probability $1/n$ or coming up; for throwing darts at a bullseye, if we're any good, then we will be more likely to be near the bullseye.  Let $\Pr(X=x) = p(x)$, where $p(x)$ is just some function: give it a value $x$ and it gives you a probability $p$.  Here $p(x)$ is called the "probability distribution function".  For simplicity, we also consider $\Pr(X\leq x) = F(x)$, called the "cumulative density function".  This is the probability of $X$ being less than some value $x$; as we'll see, a separate symbol for this is really useful.

As before, we have
$$\Pr(X_2\geq X_1) = \int \Pr (X_2\geq x)\cdot\Pr(X_1=x)dx = \int (1-F(x))p(x) dx = \int p(x)dx - \int F(x)p(x)dx.$$
You may be wondering what the weird S is, the $\int$ thing.  That's an integral sign, and it basically just means "add up all the possible values of $x$."  It's different from the $\sum$ symbol in that $\sum$ considers only discrete values while $\int$ considers continuous spectra of values.  We have used here the fact that $1 = Pr(X\leq x) + Pr(X\geq x) = F(x) + \Pr(X\geq x)$ to express this in terms of $F$.

If we add up all the probabilities of things happening, we should get 100%; that is, $\int p(x)dx = 1.$  This makes sense; the probability that we roll a 1 or a 2 or a 3, etc, is 1.  So
$$\Pr(X_2\geq X_1) = 1 - \int F(x)p(x)dx.$$
To fully evaluate this, we can write it another way.  Think what happens if, instead of rolling for the orc first then making the PC roll higher than that, we have the PC roll, then roll for the orc and make sure the orc rolls lower.  It's the same thing in the end, but can be written as:
$$\Pr(X_2\geq X_1) = \int \Pr(X_2 = x) \Pr(X_1 \leq x) = \int p(x) F(x) dx.$$
Comparing these two,
$$\int p(x) F(x)dx = \Pr(X_2\geq X_1) = 1 - \int p(x) F(x)x,$$
which must mean $\Pr(X_2 \geq X_1)  = \int p(x)F(x)dx = 0.5.$

So, the long and short of it is, if we have two random numbers that we produce in the same way, one after the other, and we want to know the probability that the second is larger than the first, then this is 50%.  In terms of D&D, this means that if you generate the DC for a skill check by rolling a die, then have the PC roll to beat that die, then you may as well flip a coin to accomplish the same thing.  This also means you can fix the DC of the opposed rolls at 10, and just add the orc's bonuses to 10 to increase the DC; it achieves the exact same thing.

Sunday, January 26, 2014

What is Spin? A Concrete Explanation.

To say that a particle has "spin 1/2" is to say that it must be rotated through 720 degrees before it can return to its original configuration.  This is not something normally witnessed in the world of classical mechanics, and so this aspect of quantum mechanics is often piled up with unhelpful metaphors and mysticism.

I wrote a post previously trying to point out that quantum mechanical spin is just a degree of freedom.  Spin tells you the components of a particle in a combination of two wave states with the same energy.  You can make pseudospins and isospins with any two such states, no matter what they are.  When you rotate the system, the components get mixed up -- just like angular momentum states.  You have to rotate the system by 720 degrees before the components get mixed up enough to be un-mixed up (i.e. back to there they were).  That's all it is.

What gives spin states this weird property is that the space of rotation is three dimensional, but the spin "vector" is only two-dimensional.  Rotations of typical vectors with three components (even if one of those components is zero) work just the way you'd think they should.  But, it's not completely surprising that 2D objects in 3D space don't rotate like 3D objects in 3D space.

To illustrate where spin comes from, and how it contrasts to orbital angular momentum, consider the case of rotation in 2 dimensions.  The best way to talk about rotations is to start at the unit circle.

Friday, February 22, 2013

Vectors are Not 1-Forms

So, I recently moved in to a new research area.  It's new to my advisor, too.  Actually, generally speaking, it's pretty new period, first appearing some ten years ago or less.  Anyway, this new field deals fairly heavily with Maxwell's Equations in curved spacetime, so to understand it we are needing to review differential geometry and general relativity, two fields which are not in the normal purview of my advisor's expertise.  I was asked to prepare a chalk-talk that would introduce the key concepts of differential geometry to them, and another talk to segue in to Maxwells Equations in curved spacetime.

Not like I'm an expert on differential geometry, but I've studied it some privately and as an undergraduate.

While studying for this, it dawned on me suddenly, like the storm clouds that pile higher and higher until the first bolt of lightning strikes the ground, that vectors and 1-forms are different.

Every thing I have ever read in physics equates them.  Or not really.  Everything I have ever read in physics doesn't even demonstrate that it understands why those two should occupy different semantic domains.

What the heck am I even talking about?

Tuesday, January 1, 2013

Why Travel to Hyperspace Would Instantly Kill You

So, I've wondered a lot about a way to construct a "system of magic" (as often appear in modern fantasy works) from a collection of physical laws.  And until I got carried up in classes last semester, that was one of my main focuses of attention.

I was thinking that, in an alternative universe, there's no reason why they should have the same number of spatial dimensions as us.  So why not four, or five, or ten?

Because if you traveled to four-dimensional space, then you would find your skin insufficient to contain all of the air, blood, half-digested food, and maybe even internal organs that now find an extra degree of freedom within which to diffuse.

Five and higher dimensions makes it worse; the many things inside of you that keep you alive would disperse and splatter even faster.

So far I have discovered that to have any sort of meaningful adventure in a parallel universe, it must have the same number of spatial dimensions as we do (namely 3), it must have at least one time-like dimension, the electromagnetic interaction must exist and must recognize and interact with your electrons and protons.  Gravity would be nice, and I don't know enough about weak and strong interactions to know if they would be necessary.
http://abstrusegoose.com/457

There are most likely other limitations and dangers in such fantastic travel that have not yet come to mind.

In short, the inter-universe questing of children from our universe can never be to any world truly alien from our own.  Which is very sad.

Friday, November 9, 2012

The Dirac Sea: Turtles All the Way Down


This semester, I am taking a course on relativistic quantum mechanics.  Currently we are covering the "hole interpretation" of negative energy solutions to the Dirac equation.

I've done this stuff before, as an undergraduate, in private study, and in various grad-level courses.  So I'm used to the interpretation being given.  But I decided recently that it is perfectly absurd.

Thursday, August 23, 2012

The Berenstein Bears: We Are Living in Our Own Parallel Universe

if only facebook would make this the preview photoWhen I was growing up, all through elementary school we would watch movies and read books about the Berenstein Bears.  I still even remember the theme song for the TV show, mostly, which wasn't a song so much as a guy in a gruff bear voice speaking in rhyming couplets.  If you don't know who the Berenstein Bears are, they were nuclear family of anthropomorphic bears who lived in a tree out in Bear Country and had family-based situational comedy and taught life lessons.  And Ma Bear always wore a blue shower cap.

These bears appeared in a series of children books by the married Stan and Jan Berenstein, that later became a TV series, that got beamed to 3rd grade classrooms all over the country.  Anyone between the ages of 23-30, and maybe more, will know who the Berenstein Bears are.  And they will remember the flashy cursive bubble-letters on the front of every single book and in the opening credits of the show.  The bubble letters that spelled out "Berenstein Bears".

About a year ago, Jan Berenstein passed on, as had Stan some time before.  And appearing in headlines across the internet, I saw "Jan Berenstain Dies at 88".

BerenstAin.

They misspelled her name.  In her obituary.  Gosh, that's really just morbidly embarrassing.  "Berenstain" doesn't even make sense.

Sunday, July 1, 2012

The Physics of a Chess Board


In Through the Looking Glass by the Reverend Lewis Carol, Alice walks through a mirror in her living room and finds the chessboard that normally resides there to be teeming with little chess pieces running around.  Leaving her mirror-house, the entire country around it has been transformed in to a chessboard.  Alice starts as a pawn and has to walk forward one step at a time to the end, when she will become a queen and be able to run as fast as she wants across the country.

While Carol's story is whimsical and fun, what would be the implications of living in a chess board?  What are the "physical laws" experienced by a given chess piece?

So imagine all the universe to be a discrete 8X8 grid, alternately tiled with black and white, and conceive of a chess piece as being a kind of elementary particle in this bizarre chess world.  We will look mostly at the free dynamics of such a chess particle - that is, how it behaves dynamically in the absence of other pieces.

Monday, June 25, 2012

Zeno's Paradox and Why It Annoys Me


I have always been greatly annoyed by Zeno's paradoxes.

The reason why is due mostly to my stubborn pride at being ignored when I'm right.  When I was in 10th grade trig, we learned Zeno's paradox of Achilles and the Tortoise.  The problem so presented is an extremely simple algebraic equation, immediately solvable to anyone who has finished high school.

So in grade school, when I was taught this "paradox", I did solve it algebraically, almost before my teacher had finished reading it from the book, and I told her the answer, and she sort of gave me this exasperated smile and said "Yes, I know, but don't think about it that way."  And ever since, mention of this paradox as anything other than an ancient Greek misunderstanding of mathematics has infuriated me.

Basically, Zeno's paradox amounts to asserting that the geometric series cannot be summed.  Which is absurd; Archimedes was quite proficient at it, even in terms that Greeks would accept.  Some examples are below.  In terms of modern algebra, let $S$ be the sum of a geometric series; then
$$S = \sum_{n=0}^\infty a^n = 1+a+a^2+\cdots = 1+a\left(1+a+a^2+\cdots\right)=1+aS,$$
and rearranging, $S = \frac{1}{1-a},$ the formula you hopefully learned in high school.