Tuesday, January 12, 2010

The Fundamental Theorem Of Betting

I used two popular websites to get betting odds for the today's match between Egypt and Nigeria. Here are some odds from two example sites:

Site 1: Egypt (2.90) - X (3.20) - Nigeria (2.35)
Site 2: Egypt (2.65) - X (3.10)- Nigeria (2.65)

Which site of the two should be preferred over the other? Generally, how to compare the attractiveness of different betting odds? In what follows, I am presenting what I call as the "fundamental theorem of betting".

Consider just the single game "Egypt vs Nigeria" which has 3 possible turnouts: "Egypt wins", "nobody wins" and "Nigeria wins". Let us also consider that we have a budget of Δ dollars and that we split this sum to all three turnouts, betting Δ1, Δ2 and Δ3 respectively. Finally, for every event, we expect to win some money, say W1, W2 and W3. In general, we are just interested in winning more money than we spent ( Δ dollars), so for every event that might take place (e.g. "Egypt wins" ) we might want W1 > Δ or W2 > Δ or W3 > Δ. But we might want to ask: Can all of these inequalities hold? The obvious answer is no. Otherwise, the booker would go bankrupt. Next, we have to ask: What values do the W's satisfy? It turns out that this is a linear function, with coefficients determined by the betting odds of the booker!

Consider that we have a budget Δ and we want to split this in all k possible turnouts. Thus, we will have to pay Δ1, Δ2,Δ3,..., and Δk respectively. For every turnout i the booker provides a betting odd Mi. This means that we will win Wi = Mi * Δi, in case of this turnout. Finally, every profit has a specific ratio of the whole budget Δ. This is the real profit since we are interested in making more money than we spent. For every turnout the profit will be denoted as: Ai = Wi / Δ. One can easily see that:

(A1/M1)+(A2/M2)+...+(Ak/Mk) = 1

For clearer inspection:

This is what one could call the "Fundamental Theorem Of Betting".

Remember that the μ's are the booker's betting odds and the α's are the ratios of profit over the overall budget. For example, if we invested $200 in total and Α1 = 2.0 then if turnout #1 happened we would win 200x 2.0 = $400 and so on. When an α is greater than 1 this means that we won more than we invested in total and so we are interested in establishing at least one α greater than 1.0. This means that it would be useful to consider one single quantity:

M = (1/M1)+(1/M2)+(1/M3)+...+(1/Mk)

The following cases now exist:
1) M > 1.0
If this is the case then the booker is going bankrupt. Players can construct a set of α's such that all of them are greater or equal to 1.0. This means that every player either wins more than he spent in total or he gets his money back (zero loss)

2) M = 1.0
In this border case, the players can set all α's to 1.0 and never suffer a loss. This is not very meaningful and players might try to disturb the ratios by increasing and decreasing some of the ratios.

3) M < 1.0
This is expected to be much more frequent in real world betting odds. Players will have to decide how to distribute their bets.

What's more important, the quantity M can be used as a metric of how attractive the betting odds are. The greater the quantity M is, the better the odds are for the players. Going back to the example in the beginning we have:

Site 1: M = (1/2.90)+(1/3.20)+(1/2.35) = 1.0828
Site 2: M = (1/2.65)+(1/3.10)+(1/2.65) = 1.0773

One can see with a single arithmetic comparison that Site 1 gives slightly better margins for profits (1.0828 is bigger) and it should be preferred to Site 2. Even within the same book house, players should prefer games with higher M factors than others. The first step to a complete "Theory of Betting" has been made!

Thursday, December 17, 2009

The Most Influential Person On Computer Science

Who was the most influential person on computer science (or computing if you prefer)? A web search is not particularly helpful. Most of the times, the pages I got were confusing CS with programming. However, to quote Edsger Dijkstra, "Computer Science is no more about computers, than astronomy is about telescopes". Some names may come quickly to
mind: Alan Turing, Church, Kleene etc, were all pivotal to the development of the computing science. But a deeper search can reveal the person who had the most critical impact: David Hilbert.

Hilbert was a German mathematician who worked on an incredible range of subjects: number theory, logic, geometry and over to special relativity theory. Yet, it was not his direct contribution that matters, but the influence he had to others on working on the fundamentals of computation. And it all started by his zealous stance towards a deep philosophical debate of the "ignoramus et ignorabimus".

And now the story begins.

Back in 1872 Emil du-Bois Reymond was a well-respected physiologist with considerable work on electro-physiology, studying the electric "properties" of human and animal tissues. At this year, he publishes a paper in which he claims his philosophical belief of "ignoramus et ignorabimus" (=we don't know and we won't know). This was a slightly more pessimistic version of the well known Socratic view "I know one thing; that I know nothing" but it was gaining acceptance through the philosophical circles at the time. The main point was that there are some stuff that humans do not know and they will never know (e.g. the origin of life or the universe) One might agree that it seems like a yet-another harmless philosophical idea. Some people were supporting it, others would be skeptical, but all in all, life would go on. But science was meant to take a dramatic turn because a man would take this debate to the extreme.

At that time David Hilbert was 10 years old. In subsequent years, through his work, he would confront deep philosophical problems, even within mathematics. However, the "ignorabimus" movement had really hit his nerve. In 1900, in the International Mathematics Conference in Paris, he addresses a call to arms to mathematicians by claiming: "in mathematics there is no ignrorabimus!". He uses mathematics to exterminate once and for all the pessimistic view, and claims that there should be a finite process of inference rules, that when applied, they would infer any correct statement. He then asks from mathematicians to help him in this direction (the 2nd problem in the problem list he announces at this speech was related)

Almost 28 years later, in 1928, Hilbert poses yet another challenge: The Entscheidungsproblem asks specifically for an algorithm that will be able to decide if a specific statement (e.g. 1+1=2) is true or not. During the 30's great things just start happening. In 1931, Kurt Godel breaks the first problem with his ground-breaking theorem of incompleteness. In short, most interesting systems, can either infer contradictory statements or they cannot infer some correct statements. Later, in 1936 and 1937 Church and Turing independently solve the last puzzle by proving that there are statements that cannot be proved or disproved. Hilbert's dream was shuttered but a new scientific field was born out of the proofs of these very problems! It is important to note here that, 5 years before his proof, Alonzo Church was in the famous Gottingen University during the years 1929-1931, visiting...David Hilbert.

But wait, there is more! It was not only theoretical computer science that was catalyzed by the influence of David Hilbert. The creation of the first general-purpose electronic computers would be pioneered by his assistant. Even in 1942, one year before the ENIAC project, Hilbert's former assistant in the University of Gottingen, would start an ambitious project of creating a general-purpose computer in the Institute of Advanced Studies at Princeton University, that ended in 1952. His work all these years marked the beginning of this era and his architecture is preserved more or less even in today's computers. His name was ...John Von Neumann!

Other than Hilbert, who else can claim of having a bigger impact on computer science?

Wednesday, August 5, 2009

Catching Up

An activity of 1 post per year, is hardly considered a blog. Yet, there is some good reason for that, and it is not happiness as Aaronson puts it in his own recent post. From April, when the last post was Slashdotted, I have never been in the mood for writing something, although there is actually some good potential material. Here is a short summary of the things that I have been doing since April, offering at the same time, a kind of apology to the readers of this web column.

In April, I moved to the Emirates, in a robotics laboratory (IRML) near Dubai.We have been doing work on human-robot interactions, and we have also been exploring how social information can be used to make them more meaningful. The project is called Facebots, carried out by Nikolaos Mavridis, and funded by Microsoft's External Research. Mr Mavridis, is an MIT-graduate Medial Lab) and the founder and the director of the IRML laboratory of the University of the UAE. His innovative research lies in the intersection of virtual and physical worlds, and the lab he manages is the most advanced in the region and perhaps one of the best globally. Here are some highlights the work we did, which might be extended in subsequent posts.

First there was the first Arabic speaking interactive humanoid robot, which was programmed as part of a senior project in UAE. Our robot, was able to understand a set of keywords and perform a simple pre-scripted interaction with gestures and facial expressions, and all of this in Arabic. You can watch a demo of this interaction in the following video:

Second, in the Facebots project, Facebook was used in order to build rich and meaningful interactions. For example, the robot was able to harvest data from Facebook and gossip with humans, about mutual friends present in Facebook or in real life. In a spin-off project, we researched how social information, like friendships, can assist face recognition tasks. The idea is that we tend to co-exist with friends in our photos. Results were encouraging and were published in relevant papers. Some of the prominent visitors in our lab, which also interacted with Sarah Mobilero, the little Facebots robot, were Shankar Sastry, Dean of Engineering at Berkeley, or the Ambassador of Canada in the UAE.

Both projects received some pretty wide media coverage, most notably with BBC's report on the Ibn Sina humanoid robot. You may find the BBC article here. In addition, several newspapers covered the Facebots story with The National, offering the most precise version in its UAE-wide pages. The article exists online and can be found here.

Now, I am preparing for Harvard University, where I will be taking some graduate courses in Computer Science in the Fall term, and hopefully make the way for a graduate degree in CS or Applied Mathematics. Before moving to Boston though, I hope to recover and to be done with all the catching up, because come to thing about it, there are much more to say!

Wednesday, April 15, 2009

If Philosophers Were Programmers

Although not obvious, philosophy actually has a strong relation with programming, at least for me. If you think about it, software code reflects much of how the developer perceives the problem and its solution. Before starting to program, developers spend some time thinking over the problem, identifying important properties and their underlying connections, a process that reveals their philosophy as the way they perceive real-word situations. Likewise, philosophers are constantly trying to identify the most important properties of the issues they reflect on, like life, conscience or God.

Under this perspective one might be able to make a consistent mapping of the ideas behind programming languages and the ideas that philosophers have come up over the years. It is perfectly reasonable to consider the programming languages as the different philosophies of a virtual world, in which entities do exist and interact with each other. To this respect, even the fundamental philosophical questions receive an interesting transformation: For example "What is self-conscience?" can be rephrased as "What is reflection?".

To the fun part, one might ask: "What if philosophers were programmers? What programming language they would use?". Well, here are my answers!

Socrates : The Hardcore Assembly Programmer
Socrates was one of the founders of philosophy but this is not where the connection ends. Socrates had devised a clever methodology to win every debate. He kept asking questions until a contradiction was reached. So, when someone would claim "morality is important", Socrates would ask "How do you define morality?".

In a similar manner, everything in Assembly begs for a question. There is nothing pre-assumed (at least in pure Assembly, not the distros filled with pre-processed libraries and other junk) and everything has to be as succinct as possible to have a meaning. If you were to work with the programmer Socrates and shared something like "var x = null;", your partner would start by asking "What is var?" !

Aristotle : The Influential C Programmer
Aristotle had a huge impact on Western philosophy, founding many scientific areas, from physics to biology. He was the first to closely examine real entities as the real essence of everything, in contrast to Plato's abstractions. His philosophy is driven by the golden mean as the key to reaching morality or understanding life (matter and form).

The C programming language was equally influential to the design of all other "programming philosophies", most obviously in the syntactical level. In addition, by the time of its writing in the early 70's, C was supposed to be the golden mean between the so-called high-level languages and the Assembly language, combining the capability to write machine-independent code combined with the power of low-level access.

Plato : The Idealistic C++ Evangelist

Plato is a huge figure in philosophy, student of Socrates and teacher of Aristotle. That said, I owe you an explanation about the obvious anomaly: How come that C++ is coming after C? Let me explain. Plato is famous for his Forms or Ideas, that refer to the archetypical versions of the things around us. So, the cup in your desk has is a shadow of a similar oval-shaped archetype in the world of Ideas. In programming words, it is an instance of the Cup class.

Similarly, C++ , as an extension of C, is the first language that tries to capture this idea of forms by giving the developers the capability to abstract the problem before doing anything else. This is a major step by itself, since even if no actual code solving the problem is provided, the classification and the problem modelling are evident and valuable to others. You might wonder, why Plato would not program in Java. Well he could, but there is another parameter to the story: Plato is not so confident how symbols can represent his Forms, and clearly prefers the spoken dialogue (as mentioned in Phaedrus). In a similar manner, C++, not entirely confident in its direction, remains a superset of C, being fully backwards-compatible with the more non-ideal syntax of C.

Stoics : The Happy Perl Community
Stoics and their philosophy (Stoicism) had silently, a far-reaching impact not only to Western philosophy but to the philosophy and the global culture as a whole. Interestingly enough, there is no single man behind it, but it was actually a collaborative intellectual achievement. Stoicism denies anything immaterial and tries to explain the world through propositional logic. So, Stoics reject everything Ideal and concenrate in morality, in which they call us to get free from anything we can't control, but rather appreciate the freedom to self-introspect and reach true wisdom. Stoicism rejects political systems and other formalities, and promotes Socrates' citizen of the world for everyone. People are meant to be brothers, away from distinctions, aiming to contribute happily to a society of friendship and love (jus commune gentium). You should already notice the influences to most widespread religions, like Christianism and Buddism.

Most interestingly, Perl was created in the 80's, a decade in which finally logic/functional programming had found its place in the programming languages world. However, the Perl community (and language) shares much more striking similarites with the Stoics and their philosophy. Perl as a language is to the best possible extent, free of form. Actually the most common phrase in the Perl world is "there is more than one way to do it" or TIMTOADY for short. The philosophy behind Perl rejects syntactical constraints, giving the freedom to its programmers to code in their style, but at the same time encouraging sharing and contribution to the community. Perl's power lies to a great extent to the existence of CPAN, the archive of modules and software happily shared by Perl programmers all around the globe. The language's influence to the programming world has been silent, but much more far-reaching than what is immediately observable. One could mention its strong influence to scripting, dynamic typing and functional programming, but it could be summarized to a joke which is familiar to Perl fans: The next market's crash will be triggered by a bug in someone's Perl script.

Rene Descartes : The True Java Guru
Descartes was the first philosopher of the Western culture to stand up against the Classical Ancient Greek philosophy. His core philosophy as mentioned in his famous Article 7 of the "Les principles de la philosophie" is based on the concept of cogito (=intellectual ego). Descartes believes that doubt is a proof of existence, and cogito is the cause of doubt, arriving to the famous "cogito ergo sum" (=I think therefore I exist). The cogito is not just another process we do, but actually all we do. So, what we want, imagine or feel is directly accessible through it. Descartes nearly 'proves' the existence of God, by the fact that we are able to think about the necessity of his existence. In fact any Ideal or Form can be directly accessible by our cogito. Descartes also marks another landmark in the history of philosophy: Beginning from his work, philosophy is trying to avoid confusing abstractions and to establish a succinct, almost geometrical form. Descartes presents his ideas nearly in the form of theorems.

Descartes would be the perfect Java guru. Java was the first strongly-typed language, in which everything must have a type (or share a Form) before it is being used, matching perfectly the Descartes' efforts to be always exact for what he is talking about. Descarte's cogito is in fact a revisit of Plato's Forms, with a slight variation in which ideals exist because we think about them and not in another universe. To that respect, his philosophy is purely object-oriented, as the solutions in which we arrive, are direct products of our intellects.

Immanuel Kant: The First Python Programmer
Kant found the 'easy' way to the pantheon of philosophy by rejecting two prevailing and opposing methodologies, Descarte's cogito and the empiricism, by shouting 'It's both!'. Kant investigated how humans reason, claiming that experience offers the truth, but which has already been filtered by intellectual judgement (a priori). At his mature years, he examined aesthetics, and the theory trying to explaining the way we perceive beauty. Kant was an extremely concise personality, being obsessed with tideness and exactness, doing the same things, exactly at the same time every day, to the extent that his acquaintances were 'using' him to calculate time!

Similarly, Python is a programming language that tries to combine different solutions and promote it as a new one. As a language it accepts multiple programming paradigms, from object-oriented to contract-based programming. Python programmers reject the free formats of languages such as Perl, and although they borrow several features from it, they emphasize on simple and explicit code. Python becomes so 'obsessive' that imposes whitespace identation as delimiters for code blocks to its users. In the "Zen of Python", the first out of the 19 commandments, the first one is "Beatiful is better than ugly". Kant's obsession to beauty and aesthetics, makes him triumphantly the first Python programmer ever.

Ludwig Wittgenstein: Natural Born Haskell Programmer
Wittgenstein reformed Western philosophy going as deep as to examine Socrates' 'recipe' for debate success. His monumental work, the Tractatus Logico-Philosophicus, can be compared to a hard graduate mathematical book in Logic. Wittgenstein identifies the semantic and symbolic forms as the root of all philosophical problems, leaving the rest that can be explicitly defined as the subject of science. Using pure logic, he deducts that language inherent ambiguity is what makes philosophy repeat itself, and closing his book with the famous 'What we cannot speak of, we must pass over in silence', claims to have solved,..., all philosophical problems.

Wittgenstein is a natural born Haskell programmer. Haskell was not the first functional programming language in town, but from late 80's and onwards, it has prevailed as the most important among the group. Haskell is not meant to be accesible by anyone, and just like the austere and succinct Tractatus, as Wikipedia states, it has a strict mathematical and logical form. Haskell, being purely functional, goes as deep as redefining the way we treat abstract data types, the same way Wittgenstein goes back to Socrates' dialectic to reform modern philosophy.

These all may sound weird, but for programmers, it is easy to realize these deeper connections. I am not quite sure if the same holds for philosophers. Anyway, at least by now, it should make much more sense why in every article in Wikipedia, presenting a programming language, there is special section named "Language philosophy".

Tuesday, December 9, 2008

Riots In Greece Reveal A Nation Divided In Half

I think there is nobody that has not yet heard of the huge and violent riots in Greece. It's been repeatedly over the news for 4 days on starting from Saturday 6/12/2008 when 15-year-old Alexandros Grigoropoulos was shot dead by police fire. I will try to make some statements about the madness we are currently living here, in the most sincere and truthful way possible.

The boy was not killed by police, but by a special guard.
'Special guards' is a force that does not belong to police force. They come mostly from military forces, they were formed in 1999 to patrol targets such as embassies, but remained un-armed until 2004, when Vyron Polydoras unleashed them on the urban areas, fully armed. Actually, the government was planning to integrate it into the police force by 1/1/2009 (however this seems highly unlikely now). As such special guards were not as trained as normal police officers and their existence seemed to serve only political purposes.

It was not an accident. It was a murder.
The klling was totally paranoic and absurd. Alexandros was not Carlo Giuliani. He was not killed during a riot or a protest. It was a quiet evening and the boy was out at Saturday night with his friends. A verbal dispute was enough for a military gorilla to pull the trigger. Actually the two special guards, returned back even when the dispute was over to bully the kids. This is paranoia.

Greece has no government.
Kostas Karamanlis became a Prime Minister, promising justice and transparency. However, he is trapped in his incompetence and in a party crowded by incompetence. Minister Of Interior, Prokopis Pavlopoulos (photo), is at the same time Minister of Press, after the most-provoking scandal of Vatopedi caused the resignation of Roussopoulos. Mr Pavlopoulos resigned after the murder but his resignation was not accepted.. Then, Karamanlis, totally out of touch, instead of forming a tractable plan to deal with the crisis, demanded from all other parties to clearly condemn the riots, implicitly meaning that these riots are politically supported. No comments. This absurdity has lasted long enough.

Greek youth is not rioting. It is dissapointed.
Some political parties on the left wing is attempting to exploit youth as an emering political group that is trying to express itself, a most unwise move that will fall into the void. The riots are not caused by Greek youth. They are wrong. Dissapointed? Yes. Melangholic? Yes. Pessimistic? Sure. Angry? Of course. But they are not trouble makers. They are not destroying properties or pillaging shops. Politicians should try to reach out for these young people with great caution and already some have made the big mistake.

Recent riots are much less than a revolution, but much more than hooliganism.
Politicians, analysts and journalists are referring to current unfolding riots as a social phenomenon that we will have to understand. When this stupidity will fade out, we will all realize that there is no political meaning behind setting a city building to fire. It is yet another illegal activity by criminals, extremists and immigrants. After all, these people are not any better than the guards who shot the boy. A sane demoratic society cannot justify any outlaw activity. Period.
However, this one is different. Recent riots show an unprecented violence, partially due to poverty and deep social problems and partially due to recent huge corruption scandals, like the case of Vatopedi.

Greece is now directly faced to its long deep social and political problems. The nation seems to be divided in half, the one side demanding justice and change and the other one somewhat justifying police methods and expressing the opinion that all these are supported under the table by left-wing parties...

Tuesday, December 2, 2008

My Daily Encounter With Orion

Programming is happening mostly at nights, at least for my case, because this guarantees silence and concentration. I barely can stand 2-3 hours of constant typing (unless I am really absorbed) and so I am frequently making some quick breaks by hanging around my balcony to get some good, fresh air.

I have the great privilege to be able to watch a big deal of the sky, since my house is not located at the center but in a quiet semi-suburban area near the sea, but never actually bothered to know more about the things I was gazing at. This is when I decided to set up Stellarium on my computer.

The first lesson was about the big bright triangle that I was seeing more and more often lately. It's base has three stars and it turns out it is the most known constellation on Earth. It is the Orion constellation (photo). If I was less ignorant, I'd know the basics, i.e. that Orion is visible to almost all of the Earth and in Greece it moves from East to West during the winter nights.

Wikipedia states it is the longest observable constellation, since it was formed 1.5 M years ago and it will last for the next 1M-2M years, thus having a great bond with human civilization. Orion is to be found on all cultures. In Ancient Greece, Orion was a Hunter who questioned Gods' power on Earth. Near Orion, on can find many other sky landmarks, such as Sirius on the east, the brightest star of the sky, the Taurus on the West and the Pleiades, the little 7 stars who look a little cloudy, which are next to it. Ancient imagination sometimes linked these stars together by picturing a fight of Orion with Taurus or sometimes Orion chasing the Pleiades.

Once an overwhelming experience that excited the imagination, then a great navigation tool, the stars seem to have lost their impact on human civilization (well at least the sky stars). Astromoners have computed their behaviour to the final digit to begin with.

However this is still a rewarding activity and altough I don't know if I ever forget anything that I have learned so far, since it is already a daily routine I will expect that at 4-5 am of every winter morning, Orion will be there pointing to the North, making some good company during my quick and cold homeworking breaks.

Sunday, November 16, 2008

A Programmer's (Over)View On Microsoft's PDC 2008

It has been two week that Microsoft's annual Professional Developers' Conference for 2008 came to an end.By all testaments I could find on the web, it has been a tremendous hit and the online sessions I have watched so far are really, really good.

Microsoft made a great deal of announcements: Windows 7 and Windows Azure were the most popular on the list. Apart from fancy high-tech jargon, if we were to decode in computer science terms where Microsoft places the big bets, we should mention:
  • Parallel Computing
  • Cloud computing
  • Managed Memory Framework (.NET)
Clearly, we have reached the limits of nature with these giga-capable processors on our ordinary laptops. And if we can't build better processors we can still build more of them. This is the rise of multi-core computers, and managing all these cores on the same machine is a great engineering task. Microsoft is, naturally, deeply faced with these engineering challenges that are at the heart of Windows 7 design. Windows 7 is the next desktop operating system from Microsoft, after the heavily criticized Windows Vista and its highly-advertised failure (actually Vista with Service Pack 1 has become much stable). Among other things, Windows 7, is claimed to be a much more scalable system, even up to 256 processors! Having this kind of scalability, is of course not targeted to low-end users like me and if it was, I wouldn't be able to notice it. However, if this is true, we could experience a sharp boom in high-end computational power. This interview with Mark Russinovich, a famous Windows Expert, will give you a much more technical view into the challenges of Windows 7.

In his keynote speech, Ray Ozzie (photo), Chief Software Architect at Microsoft, began with introducing Windows Azure, baptising it "Windows OS on the cloud". You can read my thoughts on cloud computing on a post I wrote some months ago. In summary, I am not the perfect fan of the idea but Microsoft on the other hand has no choice than competing directly with Amazon, Google and Yahoo! who are already into this area. Bundled with Microsoft's unbeatable developer support, it could rapidly gain much interest.

Finally, one cannot but take notice of the volume of sessions and talks about the .NET Framework which has already a prominent place in Windows developers. Microsoft is working hard on making it even more complete and adding all kinds of cool stuff in it. Microsoft announced .NET version 4.0 (current is 3.5) which will have a great deal of interesting goodies like parallel processing extensions, design-by-contract classes which lets build a kind of SLAs inside the code of your methods, a new functional programming language F#, and many more.

It is really to hard to have everything all included here. I made a quick overview, on Microsoft's take on the future and as time goes by I will try to research deeper on some things (functional programming is going to be our next topic). I highly recommend you to go over the PDC sessions which are available online. Even if you are not into Windows programming, they are very interesting and funny (especially the F# presentation)

So, to recap, Microsoft is moving, and when it does so, by the law of nature and given its big mass, it moves anything that surrounds it, and this is a fact either you hate or love Microsoft.