The world is wrong about the Monty Hall problem

Today, at school, we considered the probability theory paradox called the Monty Hall problem:

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which he knows has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

The world says that by seeing that goat, you learn that the probability of the car being behind door number 2 is 2/3 and Wikipedia has various explanations.



I claim it's 1/2. My first argument is that there is full symmetry between doors 1 and 2. How could you lower the probability of door 1 being the winning one by picking it? Nonsense.

For my second argument, let's treat it like the conditional probability that it is. All probabilities will be from your, the contestant 's, point of view.

At the start, we've got 3 equally probable situations: I'll denote them as CGG, GCG and GGC hoping it's clear enough.

Now the host opens a door. You see the goat: you gain information. Probabilities change. The probability of the door number 3 being the winning one falls down to 0.

So far, no difference from the "official" solutions. However, those maintain that while the probability of the car being behind the first door stays the same, the probability of it being behind the second one increases. Why the incoherence?

An important remark here: with the new information, we now have new events. We know that GGC didn't happen, so we have 3 events that assume ~GGC, namely:

1. if the first door wins, it's CGG | ~GGC and P(CGG | ~GGC) is 1/2
2. if the second door wins, it's GCG | ~GGC and P(GCG | ~GGC) is 1/2
3. if the third door wins, it's GGC | ~GGC and P(GGC | ~GGC) is 0,

the final results being basic conditional probability calculations.


According to Wikipedia, "even Nobel physicists systematically give the wrong answer, and that they insist on it, and they are ready to berate in print those who propose the right answer". That's comforting: I may be wrong, but at least I have excellent company.

[UPDATE] After reading all the comments, I can see that I was wrong. Boy, is that problem counterintuitive! Thanks everyone for contributing! [/UPDATE]

Rijndael S-box Sage implementation

It's no secret I like Python and Sage a lot. Today, I had the pleasure of working with Sage again: as a school assignment, I was required to show the calculations that prove that the value of the Rijndael S-box in row 2, column d, was indeed d8. While I am able to invert a polynome of this size by hand (let alone apply an affine transformation), I see no reason to do it, as a suitable tool is available.

So, here we go, the Rijndael S-box in Sage:

F.<y> = GF(2, name='y')[]
K.<x> = GF(2**8, name='x', modulus=y^8 + y^4 + y^3 + y + 1)

bin_digits = lambda h: [((int(str(h), 16))//(2^i)) % 2 
   for i in range(3, -1, -1)]
bin_poly = lambda n : sum([b * x^(3-i)
   for i,b in enumerate(bin_digits(n))])

b1 = 2
b2 = 'd'

s = x^4 * bin_poly(b1) + bin_poly(b2)
p = (1/s).polynomial().coeffs()
p.reverse()

b = [0]*(8 - len(p)) + p
b.reverse()
c = [1,1,0,0,0,1,1,0]
d = [int((b[i] + b[(i + 4) % 8] + b[(i + 5) % 8] +
   b[(i + 6) % 8] + b[(i + 7) % 8] + c[i]).n()) % 2 
   for i in range(8)]
d.reverse()

s1 = sum([d[i] * 2^(3-i) for i in range(4)])
s2 = sum([d[i+4] * 2^(3-i) for i in range(4)])

print hex(s1), hex(s2)

I admit: the above is code, not calculations, but I did the calculations in class and worked hard on the code. My main problem was the bit order. Nowhere in the original publication did it say to reverse the bytes. Adding all the reverses was a moment of desperation, and imagine my surprise when it worked. I wonder how much credit that solution will get me.

A great Friday night it was.

Blogging my thesis: Bernstein was super-easy

Did I say I had trouble understanding Berstein's work? I take that back. I'm reading Boneh now.

I'm reading one paper by Boneh. I have started reading it over half a year ago. I still don't really get it.

The paper is called "Finding Smooth Integers in Short Intervals Using CRT Decoding". In it, the author does the following:

• presents a new algorithm for CRT decoding
• uses it to find smooth integers in short intervals
• discusses how to apply it to the quadratic sieve method
• generalizes the CRT decoding problem
• reduces the gap between CRT and Reed-Solomin decoding.

My brain is burning.

Why I love Sage in 6 simple lines

This is why I love Sage:

e = sqrt(log(4*B) / log(P)) + (5 / (4*d))

g = [P^(a - i) * (x*B - R)^i for i in range(a)]
h = [(x*B - R)^a * (x*B)^i for i in range(d - a)]

m = matrix(Integers(), d, [list(k) + [0] * (d - len(list(k))) for k in g+h]).LLL()

w = sum([x^i * m[0][i] for i in range(d)])

return filter(lambda x: x[0].is_integral() and gcd(P, x[0] - R) < P**e , w.roots())

(That's a crucial part of my thesis.)

Geek got to teach!

If I haven't been an active blogger lately, that's because something came up. Something that kept me stressed and busy: I lectured the security class on Tuesday.

I lectured! Security! At the University of Warsaw! If you can't believe it, don't worry neither do I.

I talked about what I knew best: mathematical methods of breaking the RSA cipher. I also gave an introduction to elliptic curve cryptography and covered primality tests. Here are the slides (Polish only). Out of 150 people enrolled, some 30-40 were present and the lecture went pretty well: there were questions, I was able to answer... And first of all, what an honor!

Blogging my thesis: 9th of October

This morning, as I decided to just check the weather, get dressed and leave to school, I had a pleasant surprise in my inbox: my classes were cancelled. Not that I am pleased that the professor is sick, only with the unexpected free time.

Free time... what is that? What is that for? What do you do with it?

When in doubt and sleepy - sleep. I started with that. Then I decided to do some Saturday stuff: I went groceries shopping, cleaned up the house a bit, hovered.

Then, I went running. They say that physical activity helps to fight depression and I could use some help, so I went wandering in my new lovely neighbourhood and came back all sweaty.

The fitness felt good, but it didn't really help me with my procrastination problem. I procrastinated like I unfortunately often do, only this time, I didn't really feel bad about it. I'll take that as an improvement.

So, not much to brag about today. Tomorrow won't probably bring more: I'm going to a friend's wedding (two friends', actually) and then to the theater, where another friend of ours is playing in "The Revenge". Maybe Sunday.

I got to level two at Project Euler

I just got to level one at Project Euler - four months after reaching level one. Here's the well-deserved cube:


I'm still writing practically only in Python. The problems are getting more difficult and so is getting to the next level - I need to solve 50 more problems to get an octahedron. That's a nice 2010 resolution.

Anyone else doing Project Euler?

Blogging my thesis: 2nd of October

On Saturdays, I usually get to stay home all day, except for a belly dance class and maybe a walk with my husband. What a great time to check mail, apply for Google Wave invites, chech mail, check Facebook, expand my musical horizons, check mail, check Facebook work on my thesis.

What have I done today? My answer is a typical one for a student asked by his advisor what he's done so far:

Er, I have found, I have read, I have understood...

I think I've finally understood the previously mentionned Bernstein method. Understanding is the toughest part (unless you were a sissie wise person and chose an easy subject) - then comes description and implementation. Actually, doing these while trying to understand works really good, I always do that. I now have half a dozen of lines of LaTeX erroneously deleted and product trees implemented in 8 impressive lines of code (n = len(primes), if n == 1: return primes and stuff like that). But all of these were proudly accomplished yesterday, and today, I just read and understood.

Well, the night is still young.

Blogging my thesis: what's Bernstein thinking?

In his paper called "How to find smooth parts of integers" Bernstein tries to find the 20-smooth part of the number x. He first finds the product of all the primes up to 20, which is 9699690.

Then he writes 9699690 mod x = r and claims that r can be represented as ab, where a = gcd(9699690, x) and gcd(b, x) = 1.

Why? Why would that be true? It's left without proof as if it was obvious, but it's not. What's Bernstein thinking? Why isn't the answer avaliable as a cute Disney DVD?



That's what I'm workin on in my thesis right now.

[Update] Argh, I messed it up. Bernstein doesn't, Pomerance does in his book where he discusses the method and apparently, he does it wrong.

Let's find the 5-smooth part of 22. We have 2*3*5= 30, 30 mod 22 = 8, gcd (30, 22) = 2, thus a = 2, b = 4 and gcd(22, 4) = 2, not 1. Gotcha!

That's what happens when you leave something as obvious instead of proving it properly.

Blogging my thesis

I'm currently in the process of writing my master thesis. Here gos the subject:

Displacement of smooth integers in short intervals and their applications in cryptography

Ain't it the coolest thesis ever?

To be honest, I don't quite see it that way. Anything I want to do inevitably turns into something I have to do. So this post is party a pep talk to myself. I don't think it matters, however: most Fiona Apple's songs are pep talks to herself and boy, do I love them.

Okay, back to the thesis. I will be breaking the RSA cryptosystem. Calm down, your private communication is not in danger. I will not obtain significant results, only a small speed improvement over doing it "the dumb way".

How do you break RSA anyway? The whole idea, is that multiplying two big primes is easy, but having only that result, finding out what the primes were is hard. "The dumb way" is trying all the possible primes. There are some smarter ways, but they only work in specific cases, and the keys used in the real world are wisely chosen, so the tricks don't apply. There's an excellent publication about this called "Twenty years of attacks on the RSA cryptosystem". A great read, and you can skip the formulas if you're not that into maths.

So, I will be factoring big numbers into two big prime factors. To do that, I will be using smooth numbers, which are kinda the opposite of primes: they have plenty of small factors. That part is really easy, and is well explained by Pomerance in his paper "Smooth Numbers and the Quadratic Sieve". The first two pages have it all in elementary language, the later ones are hard even for me.

To find these smooth numbers, I will be comparing three different methods: sieving, the Bernstein method and finding them using error correcting codes based on the Chinese Remainder Theorem.

More on how it goes will (most probably) come.

Finals finally over.

My finals are finally over. They were tough, as I failed everything I could in June, but well, I wanted a wedding in the middle of the semester, so I got my semester during the holidays. I'm still happy with my choice.

Now to the exciting stuff. First, I had AI and passed after a few hours of revisions. I was totally prepared in June, but made the lecturer pretty angry by not writing the test at the end of the semester (honeymoon) and not taking it some other time as the result of a few misunderstandings, so, no June exam in AI for me. And the lecturer didn't seem really happy to see me in September either. But, I solved all the problems correctly, so I got a C (yeah, that's my school - they love deduction in both senses of that word).

Then came a few "free" days I used to write my networks program. The teacher was really cool for letting me write in C# istead of C, C++ or Java (none of them being my cup of tea), so I had cool tools like Visual Studio (Why can't Eclipse have a "go to definition" feature? Why? Me wants!) , Linq (goodbye, parsing XML, hello, tricky code instead of for loops) and asynchronous sockets, thanks to which I didn't have to create a single thread expilcitely, and yet my application was super-thready.

That was nice, but still, implementing a protocole and a client took me more than these four free days. It took me the entire day I had for learning compilers and one and a half of the two planned for partial differential equations. There went compilers. Fortunately, they were an extra classs I took.

Equations survived. The battle was hard: revising a whole semester in one afternoon and learning the stuff I didn't get in June. At that point, your goal is pretty much not to know less that you did last time, but I think I did know more, and I passed.

The evening after equations was equally busy: the networks exam was the next day. Dear Hubby explained some stuff to me, I was well prepared. Plans for Friday were clear: get to school by 11:30, print network notes, show the program at 12, study with strangers until 14, take exam, leave.

I arrived at 11:30. My printing limit was reached. Then I realized that I needed my advior's signature bad. Really bad. Panic. The advisor is at school only on Thursdays, so what was the probability of him being here on a Friday, out of the blue? Panic. Run. Buy extra printing credit. Run to the lab guy. He not here. Other student waits too, not knowing more than I do. Okay, let's see if by any miracle the advisor hasn't shown up. He has! Two colleagues are waiting by his door and tell me it's for about an hour of waiting. We exchange valuable advice on handling the masters stuff. Lab guy still not here. Go to the admins for the printing credit, thanking heavens for the advisors presence. Get the credit. Print the notes. Oh, here's the other student waiting for the lab guy, e-mailing him. I go upstairs, because the lab guy should be there. He is! Boot pretty pink netbook. Show program. Program is liked! Advisor again. One guy, new to me, is waiting. I sit and wait with him and praise my advisor for the thesis subject he chose me. The guy enters, I start walking in circles in heels. I finaly get there. I learn that my thesis doesn't need to be extended, just finished - great news! Run. Grab coffee. You think you'll learn anything in the last 20 minutes? Not really. Breathe. Relax. Take exam. Unexpected questions. Think hard. Finally!

I'm sleepy. My head aches. I go home and take a nap. Two hours later, my husband comes home and wakes me up. My head still aches. I take meds, planning on going for a walk. I learn that I'm hot, fever sense. Meds don't work. Let's sleep some more. Sixteen hours more. Then Husband makes me wake up, and finally, finally, finally, I get back to something I like to call "normal life".

Eye candy: a few geometrical sculptures

Today guys, for your viewing pleasure, the works of a few geometrical sculptors:

James Roper, "Into the Fold":


Carlo H. Séquin, "Tetroid with 24 Heptagons, 6 colors":


Bathsheba Grossman, "The Noom":


George W. Hart, "John Deere":


Charles Perry, "Eclipse":


Of course, there are many more on the artists' respective websites. Enjoy!

Summer is here!

Yeah, Summer is here!


I had my last exam yesterday. Yep, on a Saturday, at 9 a.m. Finally, it's over!!!

Now, I know I just came back from a two-week vacation in Tunisia, but believe me, I'm tired like crazy again. Honeymoons are absolutely well-deserved vacations for the whole emotional weight of getting married, no matter how wonderful marrying one's loved one is. By going to school at the same time, you totally earn the right to another trip. And we're totally planning one. Kinda. Someday.

For now, my plans are:

• getting my butt back to the office Monday morning
• pushing my master thesis (I wonder if my advisor remembers me and that's not good)
• learning some python and cooking
  
• erm, blogging more, doing some Silverlight stuff again would be really cool...
  
• taking advantage of the fact that I now live next to the forest!
  

I hope you're excited for Summer as well. If you need, here are some activities suggestions, and here's some advice about how to put things off and stop caring to realize your dreams. Have a great Summer everyone!

[Picture credit]

I got to level one at Project Euler (and would like to thank my boss and everyone...)

I go to level one at Project Euler! I got this pretty picture as a reward:


Now what does this have to do with my boss...

First, let's precise that the term "my boss" means "those guys who make the decisions and I don't know which one decides what" - no sucking up! So, "the boss" transferred me to a Python project and with a bunch of guys, we're learning Python.

Remember how I wrote I started learnig Python by solving Project Euler problems? Well, that's what we're told to do at work! There's a contest going on, in which many problems are from there, so when I solved one, I submitted it both to work and Project Euler and it was the last one I needed to get to level one, so here I am.

Can something be more motiviating than a contest at work? I have to code...

Random stuff

I haven't been blogging for a while (only going to school, moving, marrying - you know, the usual) and something deep in my heart tell me I should be getting back on the blogging train. So here I am, with lots of random stuff.

First, private life. I'm getting married in two weeks. Dress? Not ready. Dozens of pounds to me lost on that occasion? Not happening. (I blame the lifestyle. Losing weight is hard work, doing cardio is hard to start, as you need to get in shape a bit, and while I'm getting two degrees at a time, I'm really working hard and putting a lot of pressure on myself. Can't have it all.) But, I'm marrying a great guy, for the one and only right reason to marry, so I couldn't be happier.

I'm going to an Arabic-speaking country for my honeymoon. I'm so excited! I will finally learn to count and order food! And buy Al Jamila and many more magazines!

Silverlight 3 Beta is out and I know nothing about it, expect you need to have two development environments to work in both 2 and Beta 3 at once, which is really uncool as I work in 2 but would like to explore 3 because blogging about 2 is so yesterday. You can perfectly well develop for .net 2 having 3.5 installed and everything should work that way.

I bought a box of 5 albums by Kasia Kowalska.

And I wonder who buys that. I mean, either you're a fan, so you've got the albums already, or you're not, so you buy a "best of" or nothing, you don't spend that kind of money at once. Who does that?

I am super-motivated to procrastinate write my master paper just like the other grad students all over the world and the ones portrayed on Piled Higher and Deeper. It's scary how accurate these comics are, while the behaviors shown seem so irrational:

Please tell me I'm not like that! And don't ask how the paper is going, that would be rude.

Ok, enough for today, test coming up on Monday about lexical analysis.

A projection pro: Fred Eerdekens

In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself such that P² = P, says Wikipedia. Sweet. Can you understand that? (I can, but I study math, so I have to.)

I will show you today someone who definitely can, though he's not a mathematician: Fred Eerdekens. Proof? The pictures below:




Aren't they impressive?

Update

So I haven't updated for a while... here's what I've been doing lately:

• celebrating Chritsmas with lots of family singing
• deciding to get married in April or May
• buying stuff for our new house
• handling wedding stuff
• writing my masters paper
  
• hosting a New Year's party
• getting rid of clutter

Most of that stuff is going/gone good, except that the cat vomited on my bridal magazines.

Coming next: back to work, learning Python, preparing for the 70-something exam... Enough to keep a girl busy, right?

Big day that started bad

Today was a really big day for me: I decided to start writing my master thesis!

Here's how the title goes:

Displacement of smooth integers in short intervals and their applications in cryptography.

Sounds great, doesn't it?

So. I found the papers with the stuff I needed to start and downloaded the LaTeX template. Didn't compile. Tried compiling a kinda "Hello, World!" document. Didn't compile. Switched computers. Didn't compile.

Started loading The Sims on one of the computers while fighting with MikTex 2.7 on the other one. The Sims would freeze while loading any lot. Started wondering really hard what was going on with the world.

The Sims were easier to fix. I downloaded Sims2Pack Clean Installer, that showed my add-ons by install date, with a red background if they were suspicious. I got them working after a few tries and build something like a dorm that was in fact an apartment lot. Some old guy moved to my so-called dorm, no girl did and the residents would stay in their bedrooms instead of enjoying the kitchen, study, tv room, swimming pool and other cool stuff I prepared for them. Still, doesn't beat the stupidity of the 51 NPCs that moved into that:


Fixing MikTex was harder. Actually, there was no fixing, but getting the 2.5 version from Daddy from two years ago and getting the required packages from some russian ftp server.

But, I wrote my name on the master thesis template, so I have officially started writing it today!

My new addiction: Project Euler

I've got a new dangerous addiction: Project Euler. It's a website with cool math problems, like:

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

These problems are quite easy to solve with a little piece of code, so it's great way of learning a new programming language. I try using that to learn ocaml for my functional programming class, but sometimes I forget about that and succumb to the tentation of writing a C# console application with great ease.

I have solved 12 problems out of 218 so far and when I start solving them, it's hard to stop! Yep, one more addiction...

I swear I don't celebrate Halloween

I swear I don't celebrate Halloween. I just was at a party yesterday. And two years ago too. I don't remember about last year, however - does that mean I partied that hard?

Yesterday's party was at Long Unseen Friend's place and had nothing to do with Halloween: he was just back for a few days (he's an exchange student) and wanted to meet his friends. One guy had had his birthday a few days sooner and therefore receive a few gifts and a cake substitute. Besides that, the party consisted of people sitting on the floor, eating (Long Unseen Friend's Mom prepared lots of great food), drinking beer or juice and talking. Talking consisted of people talking about what they do best and others interrupting them with a "Will you stop talking about your master thesis? We're trying to have a party here!". Almost everyone had to be interrupted in such a way at least once.

No matter how much I appreciate people trying to have fun and forget about school, I kinda miss the times where we would play Set, or worse: the differentiable function (people sit in a circle and someone gives a function and n-th person gives its n-th derivative). Well, nothing lasts for ever, not even that great game, although it could if the starting function was smooth.