Meta Matters

Saturday, January 15, 2011
By dreeves

Today Messy Matters celebrates its 25th anniversary, in internet time. Here are three meta topics to mark the occasion.

Typo Bounties

The first meta topic is sort of an excuse to pay our loyal readers, which might seem backwards. With around 1000 active readers of Messy Matters and growing we like to think we must be adding real value to the interwebs. Nonetheless, the fundamentally right price for our blog posts is, I contend, at most zero. Why? First, the marginal cost of an additional consumer of our blog is zero. (Which is a fancy way to say it costs us nothing for you to read our blog, given we’ve already produced it.) But more importantly, any revenue would come at the expense of some users who wouldn’t get past the paywall, no matter how frictionless it was. And at the scale we’re at, we’d rather have those additional readers than the money. Note that that’s a purely economic calculation: the revenue would be tiny but the additional users increase our chances of snowballing in popularity to the point where we could make real revenue later on. Or maybe we just have other reasons to prefer maximum readership at the expense of revenue, like stroking our egos, or the magnanimous bequeathing of our wisdom to the world, or, you know, something.

So, fine, micropayments aren’t realistic for small-scale blogs. And by this reasoning, small-scale blogs shouldn’t have ads either, which I think is true. And then, ironically, after writing that we were offered $100 to link to Ace Online Schools. Ka-ching! Still, I would say that our making$100 by writing the previous sentence is the exception that proves the rule. [EDIT: See addendum below.]

Notice I said the right price is “at most zero”. We might well be happy to charge less than zero, i.e., to pay for more users when we’re small. That’s probably just too weird to try to do directly, and is fraught with fraud problems anyway. So how about this: We’d like to make it easy for people to notify us of typos on our blog. (The comments aren’t a great place for that, unless the typo impacts the meaning or understandability.) And we’d love to reward our most careful and loyal readers. So Bethany Soule kindly created for us the typo bounty widget you see in the sidebar. Typos are currently worth $20 apiece. Meta Poll Meta topic two. We have so many ideas for what to write about in the new year that we don’t know where to begin, so we thought we’d let you all have a say. We won’t listen to you, I’m just hoping that for the ones Sharad thinks I should not for the love of God write about (anything in which I reveal my absurd political ideas, for example) that I can point to this poll indignantly and say “but our public demands it!” So, at risk of encouraging us, here’s a poll. Vote for as many things as you like: If there are any of these that you want to know what on earth we’re talking about, ask in the comments! (And note that Sharad disavows this frivolous navel-gazing. These are just my ideas.) Bonus Puzzle Finally, we’re going to start appending some of our favorite puzzles to each post, sufficiently altered to deter googling the answer. Here’s the inaugural one: You have a pair of dice that you suspect are loaded. How can you use them to generate a perfectly fair, 50-50 outcome? (If you’re tempted to first try to establish the probabilities for the dice empirically, you’re on the wrong track. There’s a better, exact way. Also, they’re visually identical but not necessarily loaded identically.) The prize is a hundred dollars. Just kidding! The prize is a link to your website right here, the market value of which is apparently$100. Write your answer in the comments.

Congratulations to Alex Strehl for having the first fully correct answer to the puzzle. The problem is a variant of one proposed and solved by John von Neumann: how to get a fair result from a biased coin. The twist here is that one of the dice might be nonrandom. Alex solved that problem by alternating dice, and Bill Dirks solved it by summing them. (Various other correct and practically correct answers came in after those two.) We’re going with Bill’s as the official answer: Roll the dice twice. If the sum from the first roll is bigger than the sum from the second roll, call it heads. If it’s smaller, call it tails. If the sums are equal, start over and try again.

So, funny story about that $100 link. When they contacted us, they said it didn’t matter if the context was negative, they’d pay$100 for the link. I showed them the excerpt above and asked if that would suffice. They said no, the deal was off if I revealed that it was a paid link. And they had the gall to suggest — not realizing this had already gone to press — that if I wanted to be all meta about it I could say how we refused the offer and that it wouldn’t matter if you’re MIT [link to MIT] or Slimeball Online School [secretly paid link!], the answer is no. Well, I’m proud to say that it takes more than $100 to induce us to lie through our teeth to our readers (make us an offer!). Oh, they also realized they had given us the wrong link originally. I guess I’ll just leave it wrong, since the wrong one seems perfectly innocuous. [EDIT: Nearly a year later I finally got SEO-savvy enough to know that "seems perfectly innocuous" doesn't really cut it and it's presumably some kind of shady content farm. So I replaced the link with something genuinely useful.] Next, typo bounties. So far, two sharp readers caught two misspellings: “indentical” and “charactized”. If I’m going to pretend I was being rational about this then I guess it was worth at least$40 to me for you all to read this post (like hawks)! As if that weren’t enough to call my rationality into question, I remembered after writing this post that, belying my point about small-scale blogs, I pay $4/month for this one: letter.ly/dave. “Illustration by Kelly Savage” by Kelly Savage Tags: , , , , , • http://ai.eecs.umich.edu/people/dreeves dreeves Ouch, this post cost me$20 in the first 20 minutes. I shall now reread it!

• Joe

Define “low” as the outcomes {1,2,3} and high {4,5,6}

1. Roll both dice, if not both low or both high, restart
2. Roll both dice again. To continue both dice must share a state (so either both high or both low) AND the state must not be the same state as in step 1. Otherwise restart the entire process.

3. By step 3 we have either observed A) both dice being low, then both dice being high, or B) both dice being high, then both dice being low. Each of these two events has probability 1/2, given we have got to this point.

• http://ai.eecs.umich.edu/people/dreeves dreeves

@Joe, at risk of being persnickety, I’m declaring the problem still open. That solution, while not wrong, is both overly complicated and sort of incomplete. In particular it won’t work if the dice are loaded so that they only ever show low numbers.

• http://www.cs.rutgers.edu/rl3/index.html Alex Strehl

Choose a die arbitrarily. Roll it twice. If the first roll is less than second roll, output ‘heads’. If second is less than first, output ‘tails’. If both rolls are equal, then repeat with the other die. Continue with alternating dice until an output is produce.

• Giovanni

Mark your position on the floor. Take the first die. Throw it on your left. Now take the second die. With the same arm, throw it on the right. Now measure the distance of each die from your position. If the right one fell farther than the left one, then decide head, else, tail.

:-)

• Bill Dirks

I think this will work.
1) Roll both dice and sum the result, call this S1.
2) Roll both dice again and call the resulting sum S2.
3) If S1 equals S2, start again.
4) If you make it here, there is a 50/50 chance S1 > S2 and vice versa.
This will fail if both dice are so loaded that they are not random (for example if die one always rolls a 3 and die two always rolls a 6) since you’ll always fail step 3 but I think that’s in line with the spirit of this problem.

• Arthur B.

Throw the die, if the one closest to you has a lower value than the one furthest from you, pick heads, if it’s higher, pick tail. If the values are identical, throw again. This will work unless both dies are non random and loaded on exactly the same face. It’s slightly more robust than Bill’s answer which fails for two non random but distinct dies.

• Eric

I like Arthur’s answer, except that it’s assuming that each die is equally likely to be the one closest to you, which may not be the case if one of them is more heavily weighted than the other. Maybe a step closer to the correct answer would be:

Arbitrarily choose one of the dice to roll first. Roll this die, and then roll the second. If the value on the first die is greater than the value on the second, choose “heads”. If the value on the second die is greater than the value on the first, choose “tails”. If both values are the same, re-roll until they are different (and then choose “heads” or “tails” as previously described).

This still fails in the case where both dice are nonrandom and loaded on the same face, though.

• http://dreev.es dreeves

Great answers, everyone! I think they’ve gotten progressively better and that Eric’s is the best we can possibly do. (It shouldn’t be based on where the dice land, since, as Eric points out, one may tend to roll farther than the other. And it should work even if both dice are totally nonrandom, as long as they aren’t both nonrandom in the same way.)

Apparently you all weren’t motivated by the promise of being linked to since you didn’t leave URLs, but if you send me one I’ll include it in the addendum to the post.

Eric, when you say “Arbitrarily choose” do you mean “randomly choose”? In which case, if you have a way to randomly choose, why roll the dice at all?

Dan, did you really sell that link? The Great Omniscient Google Black Box on the Mountain may punish you for that. Personally, to me the difference between advertising and spam is all about disclosure. And you certainly did disclose the link as an ad, to your (non-omniscient) human readers at least.

Wow, $20 per typo?! That seems incredibly generous: how did you arrive at that number? • http://blog.oddhead.com David Pennock BTW That illustration is awesome. Kudos Kelly. (Also love the alt text and the byline.) • http://dreev.es dreeves Good point, Dave! In *practice* Eric’s answer would be fine: no need to flip a coin to choose a die, just pick one. You’ve got two visually identical but distinct things so picking one “arbitrarily” is like drawing from a hat. But you’re right, that’s another source of randomness, though not one that obviates the need for the dice, I would say (rather the dice are like slips of paper in a hat). Still, I take back what I said: there’s technically no solution when both dice are completely nonrandom. As for selling the link, it’s an interesting story! Stay tuned for the addendum to this post. And$20/typo was chosen such that the expected payout per post would be around a dollar, given our level of obsessiveness in editing. That was the theory, but I’m up to \$40 so far! Classic overconfidence!

To reiterate Dave’s and Dan’s points, responses involving throwing and/or randomly selecting dice are not mathematically rigorous solutions. Both Alex and Bill gave rigorously correct answers that fail to yield a 50-50 outcome only when both dice are deterministic—in which case there is no way to simulate a fair coin flip. In my opinion, though, Bill has provided a slightly more elegant solution (sorry, Alex!).

• Eric

Like Dan was getting at, I think for the method I mentioned to work, you just need a way to shuffle the dice (and I am assuming that the weighting of the dice won’t affect the shuffle). So, for example, shake the dice in your hand, set them down on the table, and always choose the leftmost die as “die number 1″.

This allows you to, in effect, randomly choose which die is “die number 1″, but the fact that you can randomly make that choice doesn’t make the “heads or tails” algorithm useless, since all you can do without it is randomly choose between two indistinguishable items. Of course, if the items were distinguishable, then all you’d have to do is shuffle and pick one, and then assign heads if you picked the black die and tails for the red die, for example. But the fact that it was specifically mentioned that they were indistinguishable makes me think that shuffling is fair game, because it seems like it was added to avoid the trivial “heads for black, tails for red” answer.

Given that shuffling is allowed, I do still think the method works even when the dice are completely nonrandom, as long as the two dice aren’t nonrandom in the same way.

Sorry, Eric, but I’m going to reject your solution! I’m more of a stickler than Dan….While there may have been some ambiguity in the question, I believe that it violates the spirit of the problem to assume you can choose a die uniformly at random. I agree though that IF you can choose a die at random, then you can improve upon Alex and Bill’s solutions to generate a 50-50 outcome even when the dice deterministically land on two different numbers.

• Eric

Fair enough. At the very least, I’m happy that my argument for why shuffling should be valid (“if not, why even state in the problem that the dice are indistinguishable?”) has a sort of meta feel to it itself.

And I’d also like to second the kudos for that great illustration.

• Eric

(And to add one last piece to my meta-ish argument, if Alex and Bill’s solutions are sufficient, why even state in the problem that there are two dice? It could just as easily be done with one.)

• http://www.thenorthwebsite.com/ North

I believe the only truly perfect answer is this:

1) Sell the loaded dice as curios to a passer by for any non-integral number of dollars to be paid in cash.

2) Flip any one of the acquired coins.

:D

• http://www.thenorthwebsite.com/ North

P.S. — Oops. I forgot to stipulate that the non-integral number may not be specified to a resolution of less than 0.01 dollars. :)

• http://www.levreyzin.com Lev Reyzin

It seems that the fact there are two dice is a red herring. For the (rigorous) solutions above, 1 die works just as well (assuming it’s not deterministic).

• http://dreev.es dreeves

I think I made it two dice because the singular of “dice” sounds so morbid! Just kidding, it was mostly a red herring. Or for the interesting twist that one die might be nonrandom. And I think I did specify visually identical to head off cheap solutions like drawing one of them from a hat. So I like Eric’s meta-argument! Still, I guess I’ll agree with Sharad that Bill’s should be the “official” solution (so far), with the official version of the problem changed to not mention how the dice look and to explicitly rule out forms of randomness other than actual rolling of the dice.

• http://www.thenorthwebsite.com/ North

OK, so here’s my serious answer. :)

I came up with this idea …

1) Pick either die (or you can use the sum of both).
2) Roll once and note the result.
3) Roll again and “flip” the result around the median value of all possible rolls (3.5 for 1d6, 7 for 2d6) — so for 1d6 a 6 becomes a 1, a 5 becomes a 2, and so forth.
4) Add this flipped result to the result of the first roll; there’s a 50/50 shot that this sum is greater than twice the median value of all possible rolls.

… but then i realized that this is really another form of Bill’s answer.

My rationale was based on probability density function (PDF). A loaded die (or the sum of two) has some given PDF that is _not_ uniformly distributed over the possible outcomes. The key to generating a 50/50 outcome is to somehow translate the PDF into something symmetrical around a known axis of symmetry. “Flipping” a second roll (which has the same PDF) around the median of possible rolls makes it the mirror image of the other. Summing the two creates a new random variable with the desired symmetry around the sum of the median values (which is simply double the median value).

All that said, i took another look at Bill’s solution and realized he beat me to the punch, and perhaps did so more elegantly. He effectively does the same thing by _subtracting_ one roll from the other (by checking to see which is greater). The subtraction performs the “flip” of the PDF, and the difference is a new random variable that’s symmetrically distributed around zero, so there’s a 50/50 shot that it’s positive (S1 > S2).

In both cases, a roll has to be able to generate at least two different outcomes. The resultant PDF based on loaded dice that always roll the same number is still symmetrical, but only generates one outcome, so — much like flipping a marble — it’s not very useful.

ANYway … sorry for the long diatribe, but when i realized i might explain both my paradigm and how it justifies Bill’s solution, i thought i would share. :) Thanks for fun problem!

• Alex Strehl

fwiw, I still like my answer better than Bill’s, because it requires less rolls on average to halt (even if you’re required to roll both dice each turn).

Alex, I admit that it’s a subjective call, and really, the two solutions are nearly identical. As an aside, if your goal is to efficiently generate 50-50 outcomes, instead of alternating between coins you could treat the situation as a multi-armed bandit, learning over time the better coin to flip.

• http://crisicon.com Cris Iconomu

use new rules:
- the face “facing” the thrower is the one that counts.
- if the die is pointing an edge at the thrower, use a ruler or something similar to push it agains the wall and force it to present a face (okay, this is a bit streched but you get the idea…)
no matter how the dice are loaded, by disregarding which face is up you eliminate the one factor participating in the “mechanism” – gravity. the rest is just … random
i asumed the use of cubic dice :)

• http://www.levreyzin.com Lev Reyzin

Sharad – what are the payoffs in this bandit problem?