Sebastian Pokutta's Blog

Mathematics and related topics

Archive for January 2010

A polyhedral characterization of border bases

leave a comment »

Tomorrow I will give a talk on a recent paper which is joint work with Gábor Braun from the Alfréd Rényi Institute of Mathematics. It deals with the polyhedral characterization of all admissible order ideals (and hence border bases) that exist for a given zero-dimensional ideal. As a hardness result, it also follows that determining an optimal order ideal (w.r.t. to a linear objective function) is NP-hard. This is in particular interesting as it shows that not only computing the L-stable span (the vector space approximation of the ideal) is hard but also choosing a ‘nice’ basis which is a mere basis transformation from a linear algebra point of view (see also my previous post for some more details). Here are the slides:

View this document on Scribd
Advertisements

Written by Sebastian

January 31, 2010 at 7:58 pm

The GNU Linear Programming Kit (GLPK) : Resources, Tutorials…

leave a comment »

I just put together some more resources, tutorials, and information about the GNU Linear Programming Kit (GLPK). The page can be found here.

If you have some information, links, etc., that you would like to see there, just drop me a line.

Written by Sebastian

January 24, 2010 at 10:44 pm

Information asymmetry and beating the market

leave a comment »

Recently, I was wondering how much money you can effectively gain by investing, given a certain information advantage: Suppose that you want to invest some money, for the sake of simplicity say $10,000. Can you assume to be able to extract an average-exceeding return from the market given that you have an information advantage? If you believe in the strong form of the efficient market hypothesis then the answer is no of course. If not, then is it at least theoretically possible?

Let us consider a simplified setting. Suppose that we can invest (long/short) in a digital security (e.g., digital options) with payouts 0 and 1 (with a price of 0.5) and let us further suppose that it pays out 1 with a probability of 50%. Now assume that we have a certain edge over the market, i.e., we can predict the outcome slightly more accurately, say with (50+edge\%) accuracy. If we have a good estimate of our edge, we can use the Kelly Criterion to allocate our money. The Kelly Criterion, named after John L. Kelly, Jr determines the proportional amount of money to bet from own bankroll so that the overall utility is maximized – this criterion is provably optimal. It was presented by Kelly in his seminal 1956 paper “A New Interpretation of Information Rate“. In this paper Kelly links the channel capacity of a private wire (inside information) to the maximum amount of return that one can extract from a bet. While this bound is a theoretical upper bound, it is rather strong in its negative interpretation: If you do not have any inside information (which includes being just smarter than everybody else or other intangible edges) you cannot extract any cash. The Kelly Criterion arises as an optimal money management strategy derived from the link to Shannon‘s Information Theory and in its simplest form it can be stated as:

f = \frac{bp-q}{b},

where b:1 are the odds, p the probability to win, and q = 1-p the probability to lose. So in our setting, where we basically consider fair coin tosses whose outcomes we can predict with (50+edge\%) accuracy, an edge of 1% or 100bps is considerable. Using the money management strategy from above (neglecting taxes, transaction fees, etc.), we obtain:

Edge of 100bp

100bp edge

with an initial bankroll of $10,000, y-axis is log10(bankroll), x-axis is #bets. The five lines belong to the %5, 25%, 50%, 75%, and 95% percentiles computed on the basis of 5,000 Monte-Carlo runs. So even the 5% percentile sees a ten-fold increase of the bankroll after roughly 4,100 bets, whereas the 95% percentile is already at a 100-fold increase. In terms of real deals the number of bets is already considerable though — after all, which private investor does 4,000 transactions??

Unfortunately, an edge of 100bp is very optimistic and for, say, for 50bp edge the situation already looks a quite different: the 50% percentile barely reaches a ten-fold increase after 10,000 bets.

50bp edge

And now let us come to the more realistic scenario when considering financial markets. Here an edge of 10bp is already considered significant. Given all the limitations as a private investor, i.e., being further down the information chain, sub-optimal market access, etc., assuming an edge of 10bp would be still rather optimistic. In this case, using an optimal allocation of funds, we have the following:

10bp edge

Here the 25% percentile actually lost money and even the 50% percentile barely gained anything over 10,000 bets. In the long run also here a strictly positive growth occurs, but for 10bp it takes extremely long: While you might be able do 4,000 deals over the course of say 10 – 30 years. Here even after 100,000 bets the 5% percentile barely reaches a 29% gain (over 100,000 bets!!). Given transaction costs, taxes, fees, etc., in reality the situation looks worse (especially when considered more complicated financial structures). So it comes all down to the question, how large your edge is.

Although extremely simplified here, a similar behavior can be shown for more complicated structures (using e.g., random walks).

Written by Sebastian

January 17, 2010 at 8:04 pm

European Capital of Culture: Ruhr.2010

with one comment

The European Capital of Culture for 2010 is Essen in Germany, on behalf of the Ruhr Area (“Ruhrpott” or “Ruhrgebiet” as we say) and its several cities (e.g. Bochum, Dortmund, Gelsenkirchen, Duisburg, Oberhausen, …). The official homepage can be found here [9]. As I grew up in Essen and practically lived there the first “part” of my life I thought I take the opportunity and provide you with some background information and links, just in case you are in Germany in 2010 and you have a chance to visit that diverse and really interesting area. Unfortunately, some of the articles are in German only, but I tried to provide English resources whenever possible.

According to wikipedia, the Ruhr Area is the fourth largest urban area in Europe with some 7.3 million inhabitants. What is special about this area is its unique industry culture and the transformation in the 90’s away from heavy industry to a more service oriented area (see [2], [3], [4], German only). As you can imagine, this transition brought a lot of initial problems and desperation to people heavily relying on heavy industry for their income and the fact that those people could not be easily moved to different jobs (see [1], German only). Now that this transition is (almost) complete, the Ruhr Area presents its distinguished face to the world as the European Capital of Culture. Also check out the special issue on Spiegel ([3], German only) about Ruhr.2010.

Events and must-sees:

An event planer with events scheduled in 2010 can be found in [8] and following the same link, you can also find the Top-10 attractions in the Ruhrpott (according to Spiegel and I kinda agree).

Impressions from the Ruhr Area:

In [5] you can listen to some “typical” sounds of the Ruhr Area. These sound recordings were taken by Richard Ortmann and represent some of the day to day noises you would have heard (and partly still would hear today). Also check out his sound archive with a more comprehensive collection of sound nostalgia [6]. Probably one of the most famous songs about the Ruhr Area is Herbert Grönemeyer’s “Bochum” (about one of the big cities in this area):

Right now, 09.01.2010 15:47, there is a live show about Ruhr.2010 as the European Capital of Culture on ZDF (one of the German main tv stations). You can find it also in the ZDF mediathek [7] together with many other shows and pictures about the Ruhr Area where you can watch it for free.

Here are a few pictures from various photographers depicting the Ruhr Area:

  1. Ruhr.2010
  2. Ruhr.2010 (2)
  3. Ruhr.2010 (3)

References:

[1]: “Wir sind die Dinosaurier – und wir wollen nicht aussterben” – Spiegel 11.02.2007 (German only)
[2]: Von der stinkenden Brühe zum Lebenselexier – Spiegel 29.08.2007 (German only)
[3]: Kulturhauptstadt Ruhr.2010 – Spiegel 08.01.2010 (German only)
[4]: Industrie in XXL – Spiegel 22.06.2009 (German only)
[5]: Der Pulsschlag aus Stahl verklingt – Spiegel 20.10.2007 (German only – but for the sounds it does not matter)
[6]: Richard Ortmann – Sound Archive (German only – but for the sounds it does not matter)
[7]: ZDF mediathek’s Ruhr.2010 collection (tv shows and pictures)
[8]: Spiegel Ruhr.2010 event planer including Top 10 attractions (German only – but rather self-explaining)
[9]: Ruhr.2010 – official homepage

Written by Sebastian

January 9, 2010 at 4:39 pm