Hey. This post is a kind of an advertisement for the MIT course 6.080 (thanks to overrider for the link). I strongly recommend everyone who has any interest in computer science to read the lectures. Course covers a lot of awesome topics like Turing machines, computability, reducibility, quantum computers, completeness and incompleteness theorems and many more. Of course, if you are quite an awesome computer scientist, you’ll hardly find anything you haven’t heard before in the course. But I believe that almost anyone can find something interesting there. Now I’d like to share some facts from the lectures with you to interest you more.

You almost certainly know that some problems are undecidable. Classic example of such a problem is a halting one. But how many problems are undecidable? Only this one? Or, may be, this one and six hundred other? Is the number of undecidable problems even countable? Well, it turns out that it’s not. While there exist countable number of algorithms (one can easily prove it by sorting programs written in some Turing-complete programming language in lexicographical order), set of possible problems has the cardinality of the continuum (proof of this fact is quite simple, it’s almost like the Georg Cantor’s proof that the set of the real numbers is not countable). So, decidable problems are like a drop in the ocean.

Other interesting fact can be proven. For any possible computational complexity (n^2, n^(n! log n) etc) there exists at least one problem for which algorithm with such complexity is the best one. That problem is “does given algorithm accept given input in no more than K steps” and it can’t be solved faster than in O(K) by actually running the algorithm.

Problem “does given statement have a proof of length N or less” is in NPC. So, if P=NP, we can choose reasonably big N and check for the existence of the proof (relatively) quickly. If there is no proof of reasonable length, we can conclude that problem is not of any interest. So, in fact, if P=NP, we should stop paying mathematicians for proofs because machines can probably do better. Unfortunately, nowadays almost everybody is quite certain that P is not equal to NP.

Another interesting topic is derandomization. Does every randomized algorithm have a corresponding deterministic algorithm? Recent success in the proof that PRIMES is in P is closely related to this question.

If the facts mentioned above make you excited, you should totally read the scribe notes. I’m out.

Few days ago one friend of mine (let’s name him A) has mentioned some psychological test. Test consists of a single question, and, according to some statistics, 98 percent of serial killers answer that question right. When another friend of mine (B) gave correct answer to the question, A said that it’s highly probable that B is a serial killer. Was he right? Of course, he wasn’t. A’s problem is that he is not familiar with the Bayesian approach at all. And here is why.

Let R be the event of giving the right answer to the question and M be the event that guy who answers is a maniac. From gathered statistics we know that P(R | M) = 0.98. Next, from Bayes theorem whe know that P(M | R) = P(R | M)P(M)/P(R). P(R) can be represented as P(R | M)P(M) + P(R | not M)P(not M). Next, assume that about 5 percent of usual people also gave the right answer to the question, so P(R | not M) = 0.05. Then, what’s the prior probability of M? I think we all agree that it’s quite small, about 1e-5 or even less. Now we are ready to calculate posterior probability of M:

P(M | R) = (0.98 * 1e-5) / (0.98 * 1e-5 + 0.05 * (1 - 1e-5)) = 0.0000098 / (0.0000098 + 0.0499995) ~ 0.0002.

Probability is very small, but why is that? That’s because my friend A was talking about the likelihood, but he didn’t take prior probabilities into account. And in this case prior probabilities are of great importance.

Btw, what’s if serial killers always answer right and normal people always give wrong answers? Then P(R | not M) = 0 and P(M | R) = 1, so our model works in extreme cases too.

Today we will consider a more sophisticated inference example, with both closed-form solution and Infer.NET program. We are going to find answers to some very important questions closely connected to the Lorenzo von Matterhorn trick from Barney Stinson’s Playbook.

First of all, let’s figure out factors influencing the successful completion of the trick. It looks reasonable that girl should search for your imaginary name in Google. Without it, trick wouldn’t work. It means that girl should have some internet device and area should be covered with internet (WiFi, 3G etc). Also, if your ugliness outweigh your imaginary wealth and fame, girl may not come with you (nevertheless, it’s highly improbable). Such suggestions allows us to build the following probabilistic model with discrete variables: 

In fact our model is a Bayesian network. It means that we should specify parent-conditional probability distribution for each variable it consists of. Let’s get started.

P(I) = 0.8 because almost all the modern phones have at least GPRS support.
P(C) = 0.9 because internet is available practically everywhere nowadays.
P(G | I, C) = 0.95 (wouldn’t you google for this strange man?)
P(G | not I, C) = 0.3 cause she can ask someone who has internet to google.
P(G | I, not C) = P(G | not I, not C) = 0 cause nobody can google without internet.
P(H) = 0.2 because not much guys are handsome.
P(S | G, H) = 0.99
P(S | not G, H) = 0.5 (it’s nice to be attractive, huh)
P(S | G, not H) = 0.9 cause wealth is more important than handsome look.
P(S | not G, not H) = 1e-5 (the worst case).

Computing probability of success is quite straightforward, so we will concentrate on two little more sophisticated questions:

1. What’s the probability of you being handsome if you’ve succeeded in the trick? 
2. If you haven’t succeeded in the trick, what’s the probability she had looked for your imaginary name in Google?

To compute those probabilities, we’ll use Bayes theorem together with the law of alternatives. This blog is not really a comfortable place for a lot of formulas, so the whole inference is available in the separate PDF. As we can see there, it’s not very hard to show that P(H | S) = 0.2449 and P(G | not S) = 0.2042. We can also write a small inference program using Infer.NET library which will give us exactly the same results.

Calculated probabilities agree with our common sense very well. Value of P(H | S) shows that it’s not necessary to be some handsome guy to perform a trick. And value of P(G | not S) tells us that most of the failures happen when girl refuses to google for some reason.

That was another example of probabilistic logic in action. Next time we’ll consider some continuos case like linear regression.

As I’ve already said, I’m going to write a few posts about Bayesian approach to probability theory and, especially, to statistical machine learning. Someday I’m going to be an expert in this topic, but, currently, I’m far from it :) So, the following series of posts is my attempt to make things clear for myself and, probably, for someone just starting to learn this amazing topic. In fact, it means that there can be some mistakes. And if you find them, I’ll be glad you reveal that as soon as possible.

Click to read more ...

Those of you who watches The Big Bang Theory CBS sitcom should be familiar with the Rock-Paper-Scissors-Lizard-Spock game introduced in the Lizard-Spock expansion episode. One of my friends has recently got a t-shirt with the rules of the game printed on it. Then, we’ve got drunk and decided to play. The one question I’ve asked before we started was if the game is fair (I still have a strong feeling that Spock must act like an ultimate weapon). When t-shirt is in front of you, it’s rather easy to answer: each vertex of the digraph drawn on it (representing weapon) should have equal in and out degrees. If so, each weapon beats and is beaten by the same number of weapons. In the mentioned Lizard-Spock game each vertex has in and out degrees of 2.

But what if you haven’t such a beautiful picture? Remember how Sheldon Cooper introduces the game:

Scissors cuts Paper, Paper covers Rock, Rock crushes Lizard, Lizard poisons Spock, Spock smashes Scissors, Scissors decapitates Lizard, Lizard eats Paper, Paper disproves Spock, Spock vaporizes Rock, and as it always has, Rock crushes Scissors!

As you can see, his speech actually represents a path in the game graph. He starts and ends with the Scissors, walking through every relationship in the game. In fact, Sheldon gives us an Eulerian circuit in the digraph. Existence of such circuit implies that each vertex of the graph has equal in and out degrees, something we were trying to figure out.

Well, each vertex Vi can have the same in and out degree Ki, but Kj can be not equal to Ki for distinct j and i. What does that mean for the players? It means that there is no rule for some pair of weapons. So, if you began to play and then discovered that nobody knows what lizard does to Spock, then something is obviously wrong with your game and you don’t need neither graph theory nor other theories to figure it out.

People often understand complex things better when good examples are provided. But, unfortunately, many mathematicians prefer abstract explanations like “so, Slut(x) and Drunk(x) obviously implies Sex(me, x)” instead of just saying “I’m pretty sure I’ll have sex with that drunk chick tonight”. That’s why I want to create a list of math application examples to some real-world things that are familiar to most people. It, probably, can make math more interesting and, of course, more comprehensible. And, I’m going to start from the graph theory because it seems to be rather clear even for people far from math. So, here we go.

Click to read more ...

Some people do not believe that switching door in Monty Hall game can actually help you to win. Usually they say something like “yeah, your math is all right, but it’s just a probability theory trick, math does not help you when you are playing in real life”. Those people sometimes pretend to be clever and intellectual, but, unfortunately, they are all wrong. There is a gap between probability theory and real life of course, but not the gap they think.

For those who are too lazy to perform a simple experiment, I’ve written this short program in C#. It plays in Monty Hall game using switching strategy and actually wins in 2/3 of all the cases.

Q.E.D., bitches!

Update:
For an example of the probability theory paradox that has larger gap with the real life one can look, for example, through St. Petersburg paradox . And very good place to start finding another interesting paradoxes is there

This post is just a test of blogspot LaTeX support provided by servalx02. Idea is based on xkcd 563.

Let’s estimate so called Emelyanov’s constant (which is named after my friend Anton Emelyanov) which represesents gay density in given city. As I live in Moscow, that would be our city of interest.

Quite much, yeah? According to the Law of large numbers, if you’ve lived in Moscow for long, then you were surrounded by 144 gays on average. I don’t think that’s bad, by the way.

Gay rate was specified according to http://www.krysalis.net/homosexuality.htm.