Thursday, December 31, 2009

best of the decade

Happy New Year!

(I'm not up on popular culture enough to pay attention to only new things so this stuff isn't strictly from 2009 or the decade, just found by me therein...)

Favorite books in 2009: The Blind Watchmaker by Richard Dawkins, Desert Solitaire by Edward Abbey, A Sand County Almanac by Aldo Leopold, A Happy Marriage by Rafael Yglesias, Memories of My Melancholy Whores by Gabriel Garcia Marquez, A Room of One’s Own by Virginia Woolf, Pride and Prejudice by Jane Austen.

... and in the 2000s: Zen and the Art of Motorcycle Maintenance, by Robert Pirsig, and Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas Hofstadter.

Favorite movies in 2009: A Serious Man, and Fast Cheap and Out of Control

... and in the 2000s: Amelie, and Waking Life

Favorite music in 2009: Punch Brothers, Gillian Welch and David Rawlings, Greg Brown, Derek Trucks, the Bowmans, Lucinda Williams

... and in the 2000s: Gillian Welch and David Rawlings, Tegan and Sara, Simon and Garfunkel, Third Eye Blind, and Brahms

Favorite TV show in 2009: Modern Family

... and in the 2000s: Friends and West Wing

Favorite hobbies in 2009: bluegrass music and natural hot springs

... and in the 2000s: amateur astronomy, motorcycling, camping, programming, math, and taking care of cats

Favorite economic theories in 2009: prospect theory, quantal response equilibrium, and probabilistic voting

... and in the 2000s: everything and only things micro

Favorite math subjects in 2009: Um I haven't exactly learned much math lately but have to include this for the decade category...

... and in the 2000s: Galois theory, algebraic topology, and all things combinatorics

Most exhilarating experience in 2009: seeing the Punch Brothers live at Night Grass at Telluride Bluegrass Festival

... and in the 2000s: bungee jumping, and all those startling near-death motorcycle incidents that I would prefer to avoid but sure are exhilarating in the strict sense of the word

Favorite place in 2009: Telluride, CO, and Great Sand Dunes National Park

... and in the 2000s: New York City (esp. Central Park), and the inner Grand Canyon

Favorite software in 2009: TeXShop (Stata is decidedly OFF the list despite the fact I'm forced to use it more than anything else. Take your stupid one-at-a-time rectangular data spaces and give me R any day.)

... and in the 2000s: R, Excel (yes believe it folks, Excel pre-2007 is unbelievably awesome when exploited in the right ways), Picasa

Favorite innovation in 2009: NFL game rewind online, ultra-cheap external hard drives, red bull

... and in the 2000s: wireless internet, the obsolescence of the traditional audible use of telephones, motorcycles, diet coke/diet mountain dew/red bull, google scholar/search/mail/earth/picasa/books...

Wednesday, December 30, 2009

John Mackey

is awesome. (Even if the author of the piece doesn't fully realize it.)

paths to reason

As a child or young adult, one of the intellectual questions that most frequently possessed me was the existence of god. By college I had exhausted of the debate and considered the question totally resolved, so that by the time I developed this compulsive blogging habit, it no longer held my interest. However, issues of religion in general were not included in my original strictly epistemological contemplations, and my views on that wide of array of issues has continued to evolve over time and is most certainly not set in stone, so this is still interesting conversational fodder to me. Additionally, recent readings (Christopher Hitchens) have put me in the mood to lay out explicitly some of the earlier abandoned conclusions. So I'll probably be putting some chunks of religious philosophy (or just criticism, to put it less politely and more accurately) up here in the near future.

But there is a pretext that needs to be written first, which is my particular religious background and the path I took away from faith, which I think is sufficiently unique to be worth clarifying. Interpretation is always colored by the background of the speaker. So here's a brief description that can serve as a footnote to future religious discussion.

I was raised Presbyterian. My young life was more consumed by church activities than by anything else (except maybe music if you include the church-based music activities). My mom is the organist, my brother is following in her footsteps, and my dad sings in the choir. I went to church every single Sunday, multiple times on special weeks and every possible special holiday service. I went to Sunday school every single week and completed the confirmation class in junior high. I was in the children's choir, the youth choir, the handbell choir, the youth group, went to vacation bible school every year, and volunteered at the Wednesday after school program. I went to church camp, did all the fundraisers and projects, and spent countless afternoons just hanging out at church while my mom practiced, stamping envelopes and such.

Despite this extreme level of involvement at church, I never really got it into my head that faith was a truly important part of life. I took it for granted until I was 9 and went through the motions, with sincerity, of everything you're supposed to do, but I think the aura of "family business" that church had due to my mom's employment prevented any real sense of reverence from developing. Talk about church was about workplace politics rather than the meaning and importance of faith, which therefore never was something I held deeply personally and was horrified to abandon. But it was also not something I resented or was mistrustful of, it was just there, a nonnegotiable part of life like breakfast and spelling tests. (The eventual resentment was a result, not a cause, of atheism - after writing off religion, the high forced level of participation obviously got aggravating quickly.)

Somewhere around age 9 I had an epiphany that god is nothing but Santa Claus for adults, an invisible threat/reward system designed to induce good behavior, and probably somewhere along the line one generation had forgotten to inform the next about the charade. I quibbled about epistemological details for a few years after that, sometimes preferring the 'agnostic' label, but that was basically it. (And I obviously modified the Santa Claus story to something closer to, as Hitchens so wonderfully puts it, "[Religion] comes from the bawling and fearful infancy of our species, and is a babyish attempt to meet our inescapable demand for knowledge, as well as for comfort, reassurance, and other infantile needs.")

The point is, I never spent much mental effort on questions of internal inconsistency of religious logic, or the reprehensibility of religious morality, etc. There was no reason to think supernatural things existed, and so the rest was a moot point. This was a convenient license to continue to ignore sunday school lessons and biblical teachings in church, so that I am to this day supremely and woefully ignorant of religious mythology, history and literature. The burden of proof is on the other side, so they can nitpick over Hebrew translations and Bible verses all they want, but I don't need to.

The other point is that it's somewhat unusual to go from extreme religious involvement to atheism in a sudden step. Society is absolutely becoming more secular, but this is a slow trend of lapsing practice reinforced over generations, rather than a slew of individual epiphanies. Either way towards society-wide skepticism is fine with me, but I (admittedly conceitedly) have a huge appreciation for the active step of breaking out of a philosophical system previously taken for granted. Most of my friends are not religious for one reason or another but it's the ones who were raised seriously religious and broke free independently that I feel I can really relate to on this subject.

Another notable aspect of my religious background is that I grew up in the buckle of the Bible belt. Religion is so taken for granted that aside from some quibbles over exact denominations, I had no idea there was a nonreligious option in life. When I finally got the nerve to mention my atheism in junior high, my friends were literally terrified for my soul. The cultural tide was so powerful I never even considered taking a real stand on religion, except for some isolated tirades in the 'gifted and talented' class at school, where at least one or two other people were reluctantly open to the idea that god was an invented concept, and there was even a jewish kid (ironically this class included most of my sunday school class as well.) It is simply unacceptable in Oklahoma to abandon religion, and while I didn't so much care about social ostracism among my peers (obviously... I worked successfully towards that in many other ways) I certainly didn't want to attract negative attention from the various people who held the reins on my life.

The other factor is that I really didn't want to hurt my true church friends by either insulting their entire way of life or by putting myself on a direct train to hellfire in their eyes. So I basically kept it to myself until I was more or less on my own and would still never confront friends from my hometown with this debate. There's nothing to gain from it. I don't require their respect or understanding to be happy, and I have no problem with their pursuing happiness through delusion, so long as they don't subject me to their lifestyle. (Obviously this last condition is the problem... so obviously so and so prolifically described that I don't have much to add on that point.)

And that's about it. More on the superiority of secular morality later.

Monday, December 28, 2009

books

When You Are Engulfed In Flames, by David Sedaris: Hilarious. His voice (listened to this on the drive back) is off-putting and took some getting used to, and the first few stories weren't great, but from then on were some of the most hilarious short stories I've ever heard. (In particular, Solution to Saturday's Puzzle.) I'm surprised he's on the radio with such a voice. The title piece was the worst.

Create Your Own Economy, by Tyler Cowen: I adore Tyler Cowen but this book was disappointing. It's hard to pinpoint why. Maybe it's that nothing was too profoundly true and unexpected, but it's very likely that I'm the exact wrong person to be surprised or even intrigued by what he is saying, so that that would be too personal a critique to be worth passing on. Maybe it's that a few things were frustratingly wrong or presented badly, in particular the entire discussion of autism as such (which is one of the unifying themes for the whole book, unfortunately). I may rant about that separately later but don't feel like getting into it right now. Or maybe it's just that he uses words in unorthodox ways and invented phrases without being specific enough about what he means, so that I spent a lot of time distracted by trying to figure out what "creating your own economy" means (I think I finally understand, and think even in hindsight that's a horrible way to put it) and figuring out which of the many meanings of the word "story" he is currently referring to, than actually being blown away by the discussion. But again, I have stronger preferences for precision than most, so who knows. Maybe you'll love it.

A Mathematician's Apology, by G.H. Hardy - Endearingly absolutist and haughty, in the sense it's very clear a mathematician wrote it. A fireside-and-cocoa of books, for the mathematically tickled audience. And it only takes an hour or so.

Sunday, December 27, 2009

Berkeley insanity

Berkeley is more politically insane, on the other end of the spectrum, than anyplace I've lived in the middle of the country.

"Berkeley High School is considering a controversial proposal to eliminate science labs and the five science teachers who teach them to free up more resources to help struggling students." Here's an idea, MAKE THEM TAKE MORE SCIENCE CLASSES.

"The proposal to put the science-lab cuts on the table was ... [part of a] plan to change the structure of the high school to address Berkeley's dismal racial achievement gap, where white students are doing far better than the state average while black and Latino students are doing worse. ... [I]nformation presented at council meetings suggests that the science labs were largely classes for white students." Hmm, maybe the achievement gap has something to do with the fact that minority students ARENT TAKING SCIENCE CLASSES.

Not to mention that, the dilemma of helping one group of students but not the other is NOT to cancel one of the programs that is actually helping the first group.

Congressional censures of Richard Dawkins and creationism in science classes and school sponsored prayer is crazy, but at least I can chalk that up to the small-minded idiots in charge in those parts of the country, who are smug about their resistance to modernity and reason. But Berkeley is home of people who are smug about their open-mindedness and intelligence and reasonableness, and this is what they come up with.

I may end up in the emergency room with an aneurysm before bedtime.

Thursday, December 24, 2009

blizzard!

Merry Christmas! Or happy belated winter solstice. Or happy Atheist Children Get Presents Day (this year observed on January 19, which is just too far away, so I'm making the executive decision to bump it up to coincide with my holiday mood.)

I'm at home in Oklahoma in the biggest blizzard I can remember in this state since the epic incident in 2nd grade when we got 13 inches of snow during spring break. It was the best thing that could happen to a 7 year old.

But this time it's so severe that all the Christmas Eve services are cancelled and, for the first time in my life, my mom is spending a calm christmas eve evening at home rather than frenetically playing services and rehearsing and generally frazzling herself to death. Instead, we turned on the John Rutter Christmas Album, and put lights on the Christmas tree with hot cider.

(Just thought I would mention my appreciation for these externalities of religion before moving on to the things that Christopher Hitchens's audiobook has dredged up in my brain on the long drive home. =)

Wednesday, December 23, 2009

moderation, and in moderation



Sunday, November 22, 2009

environmentalism

Back on the subject of seemingly irreconcilable beliefs derived from instinct and logic, and on the best way to promote an ethic of respect for the environment.

I recently reread A Sand County Almanac (arguably a top 3 most beautiful book I'm aware of*) and it reminded me that my economic rhetoric in favor of environmentalism is only a tool I hope to manipulate the rest of humankind with in order that my beloved wilderness is preserved for my own enjoyment.

The thing is, I don't think the rhetoric is disingenuously manipulative. I believe every word of it. Sustainable practices pay off after an initial investment. Externalities need to be internalized. The benefit in recreation and peace of mind and natural history appreciation to humankind that comes from restricting use in certain natural areas is often greater than any more-easily-quantifiable profit from industrial activities that might be undertaken there. And even if you don't believe all that, the potential unknown impact of our actions is so high and are actions so irreversible that extreme conservationist caution is still worthwhile from a human-expected-utility perspective.

But really, I don't care about all that. It's true, but it's not why I favor conservation. I favor conservation because I love wildness. Mostly I love being in the wilderness, feeling connected to all 4.5 billion years of natural earth history, and feeling wholly human by returning to basics as much as is possible in today's world. But even if I were rarely allowed to participate in wilderness personally, I know that it is valuable. There is no logic in the world to destroy my unconditional love of nature and the belief that we as humans should protect its integrity.

Unfortunately this powerful instinct is not shared by even a majority of the population anymore, and there are many other valid and powerful reasons to respect the environment. Thus rhetoric is exclusively dominated by those cost-benefit analyses mentioned above.

Of course when motivations differ the outcomes are never quite the same. The mainstream environmentalist debate currently centers on climate change that may doom our existence. It doesn't really care about minimizing our interference in nature so as to ensure the survival of naturally occurring biodiversity and pristine wild lands untouched even by access roads and visitors centers. If we could destroy all of what nature really is and still ensure species survival, that would be fine, they indirectly say. To some extent the catch-all "we don't know what we're getting into so be careful" argument takes care of whatever else you want it to, but is limitedly convincing, and in any case all of this still misses the point.

Motivations ultimately drive the outcome even if you can manipulate them in the interim. The only way we will protect our natural heritage along with ensuring our own survival on the planet is by instilling a true ethic of conservation in the culture at large. This is what Aldo Leopold was advocating half a century ago and instead of making progress in that direction, we have scared some of the population into similar effort for very different reasons. While that may help slow global warming in the short run, it only damages the cause in the long run when we figure out how to destroy even more without destroying ourselves. The economic motivations that promote environmentalism in this century will point in a completely different direction in the next.

And so I am at a loss. I know that nature should be respected, and the best deductive train of logic I have to back that up is one that will ultimately provide license for destruction, even if I believe in its validity right now. Human behavior is hard enough to change with bulletproof logic; instincts and values are downright impossible.

*Along with Zen and the Art of Motorcycle Maintenance, and Gödel Escher Bach

Thursday, November 12, 2009

self-evident truths

Some of the questions that bother me most arise when self-evident truths conflict with logical deductions. These truths are such core values and beliefs that I can't imagine invalidating them, but on the other hand, I revere logic to the point of fetishism.

But logic when applied to the real world is a whole lot more slippery than gut knowledge. The universe is extremely complex and any time we restrict ourselves to a small set of axioms to work from, we will miss real truths or prove nonsense. Disagreement among educated interlocutors is not usually semantics, it is a result of incompatible foundations. (But often the converse is true: disagreements often aren't actual disagreements once two parties agree on a word-representation for their priors.)

Of course, in science, we pin ourselves to actual observations to sort through the infinitude of possible deductive paths. But many interesting questions are not easy to test empirically. The universe, in its mindboggling complexity, makes a poor wind-tunnel, and wind-tunnels are hard to construct to address every subtlety of interest. Hence the human race has spent the last few millennia debating the same basic philosophical questions ad nauseam with hardly any conclusive headway.

The average person is very suspicious of those who invent convoluted arguments to support views held so deeply that debate is futile. And scientists are very suspicious of those who hold beliefs so deeply they can't digest any contrary evidence. But, it is vastly easier to invent spurious logic in favor of whatever you want than to stubbornly insist on self-delusion in the face of evidence that is truly convincing (and those who do are never key players in the conversation anyway.) I think the wisdom of crowds holds here. Those who abdicate their intuition in deference to deduction are easily misguided, while those who let their gut instincts, observations, and logic interplay in a complicated and messy way to guide them towards truth, often find it.

Monday, November 9, 2009

Berlin Wall

Today marks the 20th anniversary of the fall of the Berlin Wall. This was a remarkable (peaceful!) triumph of freedom over oppressive government (and specifically free markets over communism; communism requires oppression) and one that has particular meaning to me, having been born in West Germany while that qualifier was still needed and lived in Berlin a decade after reunification.

I'd rather quote my dad than comment further, since he's an actual expert on the subject, as a professor of Germanic Linguistics at Oklahoma State University:

As a scholar, Te Velde was a frequent visitor to East and West Germany. While the wall was up, the differences between the two countries were considerable. “At first, the wall was built with cinder blocks and mortar. Then it was concrete blocks. There was a no man’s land with dogs and mine fields between the countries,” Te Velde said.

Russia controlled East Berlin, and West Berlin was the British, French and American zone after World War II. “East Berliners wouldn’t talk to tourists,” Te Velde said. “You felt the presence very much of the firm grip of the government.” Its higher profile citizens were the frequent target of surveillance by the East German Ministry for State Security or Stasi, he said. A good filmed representation of life under surveillance in East Germany can be seen in “The Lives of Others,” he said.

“West Berliners were a special breed. It was a place of escape for youth to be exempt from military service,” Te Velde said. It offered a western-style shopping zone, nightlife, bars and clubs, he said, adding, “West Berlin was always a great theater city.”

With the first signs across Europe that the Berlin Wall might fall, Te Velde said, “I was flabbergasted ... Within a week it was obvious the wall was coming down. There would be no jail, no reprisals.”

To Te Velde, the wall represents the unchecked strength of a government with a powerful military. After World War II, Germany was on its knees and couldn’t resist the Soviet takeover. That weakness manifested a dangerous power balance, said Te Velde. If there is collusion of political and military power ... and there is no response from the people to stand against solidification,” he said, there is a situation rife for military divide. “There are some tendencies in this country that we could develop into the same as then but the conditions are not the same. We are not helpless and on our knees. There is power of the people. The only danger is if people don’t recognize their power to stand up to restrictions of power or the military.”

Saturday, February 14, 2009

Valentine's Day Math

(The Stable Marriage Problem, in other words.)

I was recently reminded of this fun problem from Combinatorics, which was my favorite math class in college. The goal is to match N men with N women in such a way that no man and woman would both prefer to be married to each than to their assigned spouse (ie, it is a stable matching). There's a simple algorithm for this, invented by Gale and Shapley:

Each round, every single man proposes to his favorite woman who has not previously rejected him. The women collect and consider all these offers, and accept their favorites. If a woman has already accepted another proposal, this engagement is broken off, and that man becomes single again. This continues until everyone is paired up (which necessarily happens, since eventually every man can propose to every woman.)

Notice three properties of the resulting matching:
  1. It is stable. If there existed a man and woman in the final matching who wanted to have an affair, then that man would have proposed to that woman before his actual spouse, and that woman would have accepted.
  2. The men are paired with their favorite women that they could possibly be paired with in a stable matching. If this were not true, then there is some man M1 who is the first man to be rejected by his favorite feasible wife, W1. Say she rejected M1 in favor of another man, M2. Since men propose in order of preference, and M1 is the first man to be rejected by his favorite feasible wife, M2 must prefer W1 to any of his feasible wives. But in that case, in the stable matching (existent by hypothesis) in which M1 marries W1, W1 prefers M2 and M2 prefers W1 to W2. This contradicts the definition of stable.
  3. The women are paired with their least favorite man that they could possibly be paired with in a stable matching. This is true since if M1 is married to W1 in the algorithm, and in some other stable matching, M1 is married to W2 and W1 is married to M2, then by fact 2, we know M1 prefers W1 to W2, and therefore W1 must prefer M2 to M1 or otherwise that other matching wouldn't be stable.
The moral of the story is obvious.

But, now let's abandon traditional gender roles and sexual orientation and consider the PC version of the puzzle, say the Stable Life Partnering Problem. Now we have N people, all of whom might like to marry any of the other people, and each person chooses at the beginning whether s/he wants to be an asker or an askee. The trick is, asker's can now also be asked. I'm not sure what an easy fix for this would be. The problem is, in any round, an asker of course prefers to get a "yes" from their askee than to say yes to any other offer made to him. But then you can have a cycle of askers proposing to each other, and everyone is waiting for the person downstream to respond before accepting or rejecting other offers. There needs to be different rules for timing to make the problem tractable. Any ideas? (If asker's can't ask other askers, of course this boringly devolves into the other problem.)

(By the way, Happy V-day to all others whose revealed preferences rank writing about math over going out for the holiday =)

Friday, February 6, 2009

football meets economics

Slate had an interesting article recently about proposed changes to an overtime rule in the NFL, specifically, how it is decided which team gets the first possession. This paper on the subject makes the point more formally, for those who, like me, prefer their stories with a side of math. The analysis leaves out some considerations, however, that I think should change the conclusion.

Currently, a coin flip determines who gets the first possession, and a kick-off by the other team determines the initial field position. As overtime is decided by sudden death, the team with first possession has an advantage: they win in overtime in the last ten years more than 60% of the time. (Interesting, the historical average is lower. But better offensive drives have pushed up the advantage.) This coin-flip determination is thus nonideal, although there is no ex ante advantage for either team, because the probability of winning is randomly decided.

Two solutions to this unfairness are proposed. One is the simple fair-division mechanism familiar to any rival siblings: one chooses a split, and the other chooses which side to take. That is, one team would choose an initial field position, and the other team would choose whether to play or defend from that position. The "fair" position would depend on the teams involved of course, and it would take a couple seasons for teams to work out the best strategy, but the average fair position is estimated to be 15-20 yards. Also, note that any improvement in offense will never push the fair position as far back as the 0 yard line, since the probability of giving up a safety enforces this lower bound. (The paper makes this assumption explicitly, but for some reason does not point out this reason for its realism.)

The imperfection in this mechanism arises from imperfect information: The choosing team knows its strengths better than the dividing team, so the dividing team is at a disadvantage. A different mechanism, based on auctions, does better in this respect. In this rule, each team "bids" on field position, and the one willing to take possession closer to their own goal gets the ball at some compromise between the bids of the two teams. This is a perfectly symmetric rule, and thus favored by the economists and by the guys who wrote to the NFL to try to get the rule changed.

My first objection to this conclusion is that a little bit of unfairness in the divide-and-choose scheme is ok. It's true that if a coin toss determines which team divides and which chooses, this introduces an arbitrary element into the game. But, instead of introducing additional arbitraryness, the asymmetry could be used to counteract an arbitrary advantage that already occurred: the coin flip at the beginning of the game to assign first possession. The winner of that coin flip had a small advantage, and thus if the game ends up tied, they played slightly worse. They should thus be forced to divide the field and allow the other team to choose possession in overtime. Both advantages are small, so cancelling them out in this way should be a nearly perfect resolution.

My second objection is to the pragmatic details of the implementation of an auction rule. There are several ways it could be done, as listed by the guy, Quanbeck, who tried to get the rules changed. First is a live dutch auction, then an ascending live auction, and last a sealed bid auction. The last way is just boring. The first two ways would of course cause the coaches to plan ahead what yard they would seize or concede possession at, but in a live auction format, they would also try to read each other's body language for subtle clues and adjust their strategy on the fly. This puts too much visible responsibility on the coach, when it's better for the game if the players are the ones responsible for their fate and the coaches stay on the sidelines. Additionally, can you picture a non-trivial pause in a super-tense hard-fought violent game for a geeky field-position auction exercise? Quanbeck can, but he's an electrical engineer =) A divide-and-choose rule would take no longer than the coin toss, and make a lot more sense to the masses.

Thursday, January 15, 2009

biased coin flipping

Probability riddle!

Easy version: There are two players, A and B. They have one fair coin. What game can they play such that player A wins with probability exactly 1/3?

Harder version: Now players A and B have a single coin that lands heads with probability p in [0,1]. What game can they play, which halts with probability 1, such that player A wins with exactly probability q in [0,1]? (Hint: First pretend they have a fair coin. Then simulate a fair coin with an unfair one.)

Try it first, this riddle is quite within reach with a little pondering, and there are lots of correct answers at least for the first part.

Answer after spoiler space...
.
.
.
.
.
.
.
.
Ok, for the first version here is the answer I came up with but there are others for sure, maybe much simpler. Write 3 as 11 in binary. Now flip the coin in sets of two flips, with heads as "1" and tails as "0", so that each pair of flips spells an integer between 0 and 3. If you ever spell 11, ignore it. If the first integer between 0 and 2 that you spell is 0, player A wins. Another answer: Flip the coin repeatedly until you get tails. If tails occurs on an even numbered flip, player A wins.

Note that in general, you can use this method to simulate any rational number a/b. If 0 is one of the first a unique n-bit (where n is the number of bits needed to write b in binary) numbers spelled with the coin in {0,1,...,b-1}, then player A wins. The logic is that in an arrangement of the integers from 0 to b-1, there is an a/b chance that 0 is in the first a numbers in the sequence.

For the harder version, first let's create an event of probability p with a fair coin. To do this, write p in binary. Now spell out another decimal digit by digit by flipping the coin as above. If the resulting number is less than p, player A wins. This halts with probability 1 because in some finite time you will figure out whether the number is less than or greater than p: on the first flip that differs from that digit of p. The intuition for this is pretty straightforward. p fraction of all real numbers between 0 and 1 are less than p.

Now to simulate a fair coin: I actually found a much less pretty answer for this, thought to myself "I bet there's some really easy symmetrical solution to this" and then didn't bother trying to find it. But then a friend of mine told it to me. Turns out it's known as Von Neumann's trick. All you have to do is flip the coin in sets of two. If it comes up T/T or H/H, ignore it. If it comes out T/H, take that as a tails flip. If it comes out H/T, that's heads. By symmetry there is an equal probability of these two events.