Georgia Tech’s New Theory Club!

December 10, 2014 § Leave a comment

Hello everyone,

This past Sunday, I presented my proposal to the Undergraduate Council of the College of Computing for a club to facilitate the interaction between students interested in Theoretical Computer Science and its applications. And they accepted my proposal! Starting in the Spring Semester, we will have weekly meetings where we will have student or faculty talks or a problem session (or some sort of social activity).

I will write more about the club later, hopefully, but for now, I wanted to talk a little bit about what I did not get to talk about during my presentation. See, the council seemed so worn out by the long presentation and deliberation before my presentation that they wanted me speed through everything, and I didn’t even get to use my slides. I had prepared a sample problem session, and I want to talk about that here.

The problem session was centered around randomness. I started off with a class problem which I think is one John von Neumann was quite fond of. The idea is this:

Problem 1:

You are given a coin, but you have no guarantees that it is a fair coin. You just know that is really is random — there is some probability psuch that, whenever you flip the coin, it lands heads up with probability pand will otherwise lands tails up, and 0 < p< 1. You need to make a random decision, but you really want to make a decision with probability 1/2. You really want a fair coin. How can you use this possibly biased coin to make your decision?

Without spoiling the answer, I think this is quite the neat little problem, and it has a neat little answer. When I have asked about this problem in the past, I have had students give me answers for making choices with probabilities arbitrarily close to 1/2,

Once we have a way to generate uniformly random bits, the world is our oyster. We can sample over lots of different distributions. As a sample problem, I would like to know:

Problem 2:

Given only a method for generating uniformly random bits and a positive integer Ndevise a method for generating a uniformly random integer over { 1, 2, … , N}.

Of course, we could ask about other distributions, but this gets the idea across.

Finally, I wanted to close with a problem that is much harder than the previous two — possibly too hard for the UC, but I guess I will never find out.

Problem 3:

Alice and Bob as playing the following game:

  • Bob secretly picks two distinct real numbers, a and b.
  • Alice chooses to ask for a or to ask for b.
  • Bob reveals to Alice the number Alice asked for.
  • Alice then has to guess “higher” or “lower.”

If Alice says “higher,” she wins if the remaining secret number is greater than the revealed number, and if Alice says “lower,” she wins if the secret number is less than the revealed number.

Is there a strategy that Alice can use to win with probability greater than 1/2?

Before trying to solve this problem, we should notice something. Alice’s strategy needs to involve making random choices. If Alice’s strategy is not deterministic, Bob will just always make the hidden number reflect the opposite of what Alice would think.

Next, we should notice that Alice can definitely win with probability 1/2 by just ignoring everything, and then randomly picking between guessing “higher” or “lower.”

So can we do better?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

What’s this?

You are currently reading Georgia Tech’s New Theory Club! at A Student of Logic.


%d bloggers like this: