Writing for Wikipedia: Results of a Teaching Experiment

Some time ago I wrote an entry on a teaching experiment I wanted to conduct at TUM: As part of their graduate seminar, students have to get familiar with a scientific topic, present its core aspects in front of their peers, and write a LaTeX article summarizing again the main points. To get truly sustainable results, I asked the students to prepare their articles as if they wrote for Wikipedia. In other words, the target audience is the interested layperson, and while one should not shy away from presenting math, it should be accompanied by motivating examples and easy explanation.

And here are the results of this teaching experiment:

• Of the eight topics we offered, seven were taking, of which four were particularly suitable to become a Wikipedia article; two more could at least be added as subsections.
• Three of the suitable topics were very well prepared; so well, that we immediately recommended uploading them to Wikipedia.
• Since uploading was voluntary, only two of these three articles now appear on Wikipedia: An article on SUDOKU codes and another one on Information Dimension.
• The official course evaluation (six students participated), asking roughly 20 Likert-type questions, revealed that the course scored better than the department average over all graduate seminars (with one exception: students mentioned that there was not enough time to fulfill all tasks).
• Students also seemed to like the Wikipedia experiment: In an unofficial course evaluation, I asked eight Likert-type questions (5 = fully agree, 1 = do not agree at all; 7 students participated). The results showed that students found writing for Wikipedia motivating (average score: 4.29), that they liked writing the article first in LaTeX (5), that they would not really want to write it directly in Wikipedia (2.29), and that they learned a lot about both scientific writing and LaTeX (4.43 each). They did not learn too much about writing for Wikipedia, though (3.93).

Not sure if this qualifies as a successful teaching experiment or not - in any case, there are several things I took away from conducting the experiment:

• If you tell students to write for Wikipedia, tell them how to do it! We had a short lecture on scientific writing, but for the present case this should have been complemented by a 30 minute talk on how to write for Wikipedia.
• If you tell students to write for Wikipedia, make sure the topics are all suitable: What if a student does a very good job on a ridiculously narrow topic that can never make it into a Wikipedia article?
• Students need time. Five weeks are not enough to get familiar with a topic and prepare a well-written summary. Students should also be allowed to work on that during their winter break (that doesn't mean that they should do it - but they should be able to choose).
• During the preparation for the course, I found that there is actually more difference between a Wikipedia article and a scientific manuscript than I expected: Not only is the IMRAD structure not applicable, there is not abstract either, and also the writing style is entirely different: While in scientific manuscripts we try to write lively by including "we" as often as possible, a "we" would appear out of place in a Wikipedia article. The most challenging part, however, is the lead section: These few sentences right after the heading should deliver all relevant information of the article - "For many, it may be the only section that they read. A good lead section cultivates the reader's interest in reading more of the article, but not by teasing the reader or hinting at content that follows." Living up to these expectations is often too hard for scientists (it is for me), so how can we expect it from students?

Concluding, I hope I can repeat that experiment at a later time. Next time, three Wikipedia articles should be the absolute minimum!

Auf der Jagd nach den verlorenen Bits

In einer Zeit, in der Information eine so große Rolle spielt, sollten wir genau wissen was mit der Information in den technischen Systemen, die wir täglich verwenden, passiert. Wie viel davon geht auf ihrem Weg von der Quelle zum Empfänger verloren? Und können wir unsere Systeme so bauen, dass dieser Informationsverlust minimiert wird?

Das Smartphone-App Ihrer Bank ist sehr praktisch wenn Ihnen auf dem Weg durch die Herrengasse in Graz in einem Schaufenster ein schöner Pulli auffällt: Ein Blick auf den Kontostand genügt und Sie wissen, ob Sie sich diese sicherlich unnötige Ausgabe leisten können. Um die Sache zu vereinfachen, stellt das App negative Kontostände mit einer roten Zahl, positive mit einer schwarzen dar. Aufgrund eines merkwürdigen (und zugegebenermaßen unrealistischen) Displayfehlers sehen Sie aber nur eine blaue Zahl. Das Display hat einen wichtigen Teil der Kontoinformation zerstört.

Aber was ist Information eigentlich? Im Wesentlichen ist Information unser Wissen bzw. Unwissen über etwas Zufälliges, je nachdem ob wir die Information besitzen oder nicht. Messen lässt sich Information z.B. über die durchschnittliche Anzahl von Ja/Nein-Fragen, die gestellt werden müssen, um unser Unwissen zu beseitigen: Nehmen wir einen zufälligen Münzwurf als Beispiel, so reicht bereits eine Frage, um uns über das Ergebnis zu erkundigen: Kopf oder Zahl? Bei zwei Münzwürfen benötigen wir zwei Fragen, um beide Ergebnisse zu erfahren, bei drei Würfen drei Fragen, und so weiter. In seiner bahnbrechenden Arbeit "A Mathematical Theory of Communication" präsentierte ClaudeE. Shannon eine mathematische Formel, um die Information eines Münzwurfes – seine Entropie – zu berechnen und definierte das Bit als Maßeinheit.

Die Information eines Münzwurfes ist genau ein Bit: man benötigt exakt eine Ja/Nein-Frage, um den Ausgang des Wurfes zu bestimmen. Anders sieht es bei einer gezinkten Münze aus die in neun von zehn Fällen Kopf zeigt. Unser (Vor-)Wissen ist größer als im Fall einer fairen Münze und "im Durchschnitt" benötigen wir weniger Fragen, um den Ausgang des Münzwurfes zu bestimmen. Konkret kann man sich das folgendermaßen veranschaulichen: Werfen wir eine faire Münze zweimal, müssten wir immer zwei Fragen stellen, um die Ergebnisse beider Würfe zu bestimmen. Werfen wir die gezinkte Münze zweimal ist in vielen Fällen eine einzige, schlau gestellte Frage ausreichend: "Zeigten beide Würfe Kopf?" Wird diese Frage bejaht (und das wird sie in 81% aller Fälle), muss eine zweite Frage mehr nicht gestellt werden. Mit Hilfe von Shannons Formel kann man zeigen, dass die Information dieses gezinkten Münzwurfes bei ca. 0.46 Bit liegt: Es reichen "durchschnittlich" etwas weniger als eine halbe Frage, um unser Unwissen über einen Münzwurf zu beseitigen, etwas weniger als eine Frage für zwei Münzwürfe und etwas weniger als eineinhalb Fragen für drei Würfe.

Wie viel Bit der Kontoinformation wurden aber durch Ihren Displayfehler zerstört? Mit dieser Frage beschäftigte ich mich im Zuge meiner Dissertation an der TU Graz, in der ich den Informationsverlust in technischen Systemen untersuchte. Da sich mit einer einzigen Frage feststellen lässt ob der Kontostand positiv oder negativ ist, kann der Informationsverlust Ihres Displays höchstens ein Bit betragen. Dass der genaue Wert im Wesentlichen von der Zufälligkeit Ihres Kontostandes abhängt ist weniger offensichtlich, aber in Hinblick auf die gezinkte Münze leicht verständlich. Wenn Sie eine sehr sparsame Person sind und immer einen kleinen Puffer auf Ihrem Konto wissen, fehlt Ihnen nicht viel Information: Sie können sehr sicher sein dass die Zahl eigentlich schwarz sein sollte und Sie sich den Pulli leisten können. Wenn Sie eine sehr verschwenderische Person sind, deren Kontostand höchstens ein paar Tage im Monat positiv ist, fehlt Ihnen auch nicht viel Information: Die Zahl ist mit hoher Wahrscheinlichkeit rot. (Den Pulli würden Sie sich in diesem Fall wahrscheinlich trotzdem kaufen.) Bewegen Sie sich allerdings zwischen diesen beiden Extremen, kann Ihr Display einen beträchtlichen Teil der Information zerstört haben – im schlimmsten Fall ein Bit.

Ein Bit ist doch nicht viel, sagen Sie? Das kommt ganz auf das Bit an! Wenn Sie wissen, dass Ihr Kontostand zwischen -5000 und 5000 € liegt, müssen Sie nach Shannons Formel rund 20 Fragen stellen, um den genauen Betrag bis auf den Cent zu erfahren. Ihr Display beantwortet 19 dieser 20 Fragen für Sie – nur leider die wichtigste nicht: Ist der Kontostand positiv oder negativ? So interessant es also ist den Informationsverlust eines Systems zu untersuchen, praktische Bedeutung bekommt diese Theorie erst unter Miteinbeziehung des Relevanzbegriffs: Welcher Anteil der verlorenen Information ist für uns relevant, und welcher irrelevant bzw. störend? Ich erweiterte die Theorie in meiner Dissertation in dieser Hinsicht und verwendete die Resultate, um zu tun, was einem Ingenieur zu tun bestimmt ist: Systeme zu bauen!

Systeme werden nach gewissen Anforderungen gebaut, um gewisse Aufgaben zu erfüllen. Ein elektronisches Filter kann zum Beispiel entworfen werden, um störendes Rauschen beim Telefonieren zu unterdrücken und dabei das relevante Sprachsignal des Gesprächspartners möglichst nicht zu beeinflussen. Historisch bedingt – und schlichtweg am einfachsten – werden Filter nach Energiekriterien entworfen: Die Energie des störenden Rauschens soll nach der Filterung so klein wie möglich sein. Gleichzeitig darf die Energie der durch das Filter hervorgerufenen Störungen im Sprachsignal nicht zu groß werden, um eine angenehme Kommunikation der Gesprächspartner zu garantieren.

Ich versuchte mit meiner Arbeit einen anderen Weg einzuschlagen: In einer Zeit, in der viele unserer Systeme Information verarbeiten oder übertragen, sollte Information als Kriterium für den Systementwurf verwendet werden. Die von Shannon entwickelte Informationstheorie besagt, dass jedes System Information nur verringern aber nicht vergrößern kann. Jene Information, die wir aus dem Lautsprecher am Smartphone hören, war zuvor in der elektromagnetischen Welle in der Luft, im digitalen Signal im Smartphone unseres Gesprächspartners und in den Schallwellen zwischen dessen Mund und dem Mikrofon. Mehr als das: In jedem dieser verarbeitenden Systeme – Mikrofon, digitale Schaltkreise, Lautsprecher – ging Information verloren. Welches Entwurfskriterium könnte also besser geeignet sein als der Informationsverlust? Auf das obige Beispiel angewendet gilt es also ein Filter zu entwerfen welches so wenig Sprachinformation wie möglich zerstört und dabei die "Information" des störenden Rauschens soweit wie möglich reduziert.

Dass ein hinsichtlich Informationsverlust entworfenes Filter besser zur Informationsübertragung geeignet ist als ein nach Energiekriterien entworfenes, dürfte Sie inzwischen nicht mehr überraschen – eine andere Methode liefert eben ein anderes Ergebnis. Nichtsdestotrotz stieß ich während meiner Dissertation in der Literatur immer wieder auf Stellen, in denen Energie mit Information gleichgesetzt wurde. So wird zum Beispiel in der Statistik seit Jahrzehnten die Hauptkomponentenanalyse eingesetzt, um die Komplexität großer Datensätze zu verringern. Dabei werden die mehrdimensionalen Datensätze transformiert und Daten mit geringer Energie verworfen. Diese Vorgehensweise wird mit der Behauptung gerechtfertigt, dass die Daten mit der größten Energie auch die meiste relevante Information beinhalten. Diese Behauptung ist nicht immer richtig (und wer am lautesten schreit, hat auch nicht immer recht): Für die Hauptkomponentenanalyse konnte ich zum Beispiel zeigen, dass sie den Informationsverlust nur dann minimiert, wenn die relevante Information in einem besonderen Zusammenhang mit den Datensätzen steht, einer Tatsache, die in der Statistik nicht immer zutrifft. Es ist höchste Zeit, umzudenken.

Neben Filterentwurf, der Hauptkomponentenanalyse und der Analyse Ihres defekten Displays gibt es natürlich eine Vielzahl weiterer Anwendungen einer Theorie des Informationsverlusts: Zum Beispiel entwickelte ich gemeinsam mit anderen Forschern eine Methode, um Markoffschen Ketten zu vereinfachen, ohne dabei Information zu zerstören. Markoffsche Ketten – Folgen von zufälligen Zahlen, die in einem statistischen Zusammenhang miteinander stehen – sind wichtige mathematische Modelle und werden in der Sprachverarbeitung, als Modelle chemischer Reaktionen, in der Genetik, in der Bioinformatik und in der Warteschlangentheorie eingesetzt.

Information ist überall. Um sie nutzbar zu machen, sollten unsere technischen Systeme – Computer, Smartphones, etc. – so wenig wie möglich davon zerstören. Und selbst wenn wir es nicht schaffen sollten, diese Systeme dementsprechend zu bauen, so sollten wir zumindest wissen wie viel Information durch ungeeignet entworfene Systeme verloren geht. Die Wichtigkeit der von Shannon begründeten Informationstheorie, die ich mit meinen Resultaten zum Informationsverlust ein klein wenig ergänzen durfte, ist nicht zu unterschätzen. Es gilt heute viel mehr als je zuvor Norbert Wieners Behauptung: "Information ist Information, weder Materie noch Energie. Kein Materialismus, der dies nicht berücksichtigt, kann heute überleben."

Writing for Wikipedia: A Teaching Experiment

Writing reports and presenting results is an important part in an engineer's life, hence teaching these skills is an important (implicit or explicit) part in engineering curricula. At my former affiliation, SPSC at Graz University of Technology, we were teaching the course "Verfassen wissenschaftlicher Arbeiten" to bachelor's students in their fifth semester, preparing them for the challenging task of writing and presenting their bachelor's thesis. There, the approach was (roughly) as follows:

• Students grouped in pairs or triples and chose a topic related to the scientific process (e.g., writing good introductions, writing abstracts, giving a scientific presentation, plagiarism and literature searches, etc.).
• They had to give a presentation on this topic, teaching their colleagues the respective skills (flipped classroom).
• They chose a simple topic from signal processing (e.g., filter design) and wrote a four-page scientific LaTeX article presenting the topic as if it was their own invention.

Let me stress that again: Students should not write a review or a summary, but a scientific paper with a "novel" contribution. Why? Because that's what they have to do when they stay in academia.

Here, at the LNT of Technische Universitaet Muenchen, the offered Gradiate Seminar Mobile Communications and Coding is a very similar course (albeit for master's students): The expected outcomes are again presentation and writing skills, together with acquiring knowledge in a particular field inside communications and coding. In the last years, the approach was as follows:

• Each student chose a scientific topic and had to write a four-page scientific LaTeX article summarizing the core aspects (in the structure of a scientific paper).
• Students had to present these core aspects in a 20 minutes presentation.

The difference is apparent: Students at LNT had to write and present summaries rather than writing papers claiming original contribution. Why? Probably because that's what they have to do when they will NOT stay in academia.

But both approaches have one thing in common: Guess what happens to these four-page articles the students write. Nothing. I strongly doubt that any of our students every took a look at their paper after the end of the course. That does not mean that these articles are useless. They are not only formal requirements to achieve the degree, but they are valuable stepping stones for acquiring important skills: writing scientifically, learning about communications or signal processing, etc. In other words, the student must so to speak throw away the ladder, after he has climbed up on it.

In an effort to reduce the number of ladders thrown away, my colleague last semester required the students to copy their articles into a wiki accessible only for registered members. This was an amazing idea, one that made the seminar much more sustainable than it was before, and browsing through last year's student wiki articles gave me a good idea about what the students are capable of. Nevertheless, while the ladders are not thrown away now, they are still neatly locked up in a room in the basement.

This winter term, in which I am co-responsible for the course, I'd like to go one step further: Of all the ladders the students climb in this term, together with my colleagues we will select the most useful ones and try to make them fit for others to climb: The best student articles should end up as articles on Wikipedia. The idea is not new, as there have been several studies investigating the success of this method (for example, this one; for the supplementary material you need a subscription).

I'm not sure if we will succeed in this. Honestly, I would not want to write a Wikipedia article. But of the eight topics we are going to provide, at least four will be appropriate for an article, and at least two others could extend existing articles. Just to give you an example: As of Septemer 23rd, 2015, there is no Wikipedia article on information dimension. If such an article appears in Wikipedia by the end of January 2016, then the teaching experiment will have been successful. I'll keep you posted!

My Story with Polar Codes

It was the end of August 2010, and the weather was unusually good in Dublin. During the breaks at the IEEE Information Theory Workshop we could easily go outside, sit in the grass, and discuss the previous talks. Well, some people discussed, some just listened. Since this was my first conference in information theory (I did not even have a paper there, my boss allowed me to go there without actively participating -- an opportunity I am extremely grateful for), I clearly belonged to the second group. But then, already on the second day, there were some talks I felt comfortable with: Erdal Arikan gave a lecture on Polar Codes, a new coding technique he invented recently. What followed were several talks related to polar coding, including talks from Emmanuel Abbe (who was my main source of inspiration for my investigation of the fractality of polar codes), Tanaka (who looked at the polar coding procedure from a stochastic dynamical system point-of-view), Ido Tal and Alexander Vardy (whose code construction technique was extremely useful in proving fractality), and Eran Hof. While I did not understand a lot from his talk, I owe Eran big time: Being a total noob, I did not know anybody at this conference, and he was so kind to introduce the "big players" to me. That was absolutely necessary, because during one of the breaks I approached Sergio Verdu and asked him about the polar code construction technique he just presented. Well, apparently I confused him with Alexander Vardy (I have no idea why). Anyways, although this was one of the best conferences I've ever been to (an excursion to Castle Malahide, Whiskey tasting at Jameson's, a Riverdance show during the conference dinner, a pleasant stay at a cute little hotel, great weather, nice people, and all this together with my back-then-future-wife), this was just the beginning of my interest in polar coding.

It was in November 2011 when I presented my first paper at an information theory-related conference, the ISWCS in Aachen (during one of the short coffee breaks I met Gerhard Kramer, my current boss, for the first time; I also met Georg Böcherer, just finishing his PhD and winning the best paper award). As usual for these conferences, the first day featured tutorials in the afternoon. One of these tutorials was on polar codes, held by Emmanuel Abbe. I still have the printed handouts; one of the few paper documents I moved from Graz to Munich. It was an unforgettable experience, partly because of the awesome presentation and Emmanuel's great didactic skills, partly because of Emmanuel's lively discussion with the audience (particularly with Tor Aulin). And this great impressions led me to think about possible research directions on the train ride home to Graz. In a document called "Resarch Ideas.txt" I wrote

If a channel (one of the partitioned channels) is already very good (close to perfect), is it possible to assume all its descendant channels to be good? [...] Can we use this to find an approximation of a "good" polar code?

And then nothing happened for quite some time, as I continued my PhD research on information loss in deterministic systems. All this time, these polar codes stayed in the back of my mind and came to the front whenever I attended a conference (there were ALWAYS talks on polar codes). But time went by fast, I finished my PhD and -- totally unexpected -- started working at the Institute for Communications Engineering in Munich, becoming a member of Gerhard's lab and Georg's colleague. Some months there, not much research done (I was busy writing project proposals), the whole lab took a skiing trip to the alps in South Tirol, disguised under the title "Joint Conference on Communications and Coding". Well, in fact we did more research than skiing, something which I am quite grateful for (there are some very embarrassing photos of me trying cross-country skiing...). Instead of presenting work already done, I presented open problems, among them some ideas about polar codes. The preparation for the talk inspired me to write a blog article, and soon after that all the questions in this article were answered. Emmanuel suggested via email to extend the analysis to Reed-Muller codes, which was completed almost equally fast. It was one of the very few lucky streaks I had in my research career so far, and still some open questions pester me.

Although I am not sure if any of the obtained results is useful, I'm extremely happy to have these things out of my mind (and in a paper on arXiv). I could also present these results at the NEWCOM# Emerging Topics Workshop in Cambridge. One of the participants of this workshop was Erdal Arikan, the father of polar codes, and the very same person we were sitting next to during the whiskey tasting event at Jameson's in Dublin five years ago.

Candy Crush Codes

Candy Crush Saga is a game in which... no, I don't think I have to tell you! But I bet you didn't know yet that the game is actually NP-hard! The original proof can be found on arXiv (or, again, on arXiv; these authors claim to prove a little more general result), but there are also plenty of pop-sci articles around. (Now, that is quite interesting: Walsh posted his paper on March 8th, 2014, and the press wrote articles about it only five days later.) Anyways, that's not really what I wanted to tell you.

A typical game field of Candy Crush Saga (copyright with King Inc., taken from Wikipedia)

If you look at above picture, you will see no three candies in a row or in a column having the same flavor. Why? Because they would disappear immediately (that's more-less the only game rule). But this game rule more-less immediately leads to the following question:

If and $n\times m$ field, filled with candies of $k$ different flavors that are randomly, independently and uniformly chosen, what is the probability that there is at least one horizontal or vertical triple of the same flavor?

In other words, what is the probability that, starting a new level, something happens without you actually touching the screen. The question is obviously combinatorial and interesting in itself. But there is even more to it.

If we look at $n\times m$ fields filled with candies of $k$ different flavors, there are in total $k^{nm}$ possible arrangements. The rules of Candy Crush Saga, however, allow only a subset of these, namely,  $k^{nm}$ minus the answer to above question. For example, if we take just one row with three columns and two flavors, there are eight possible arrangements, of which two are excluded. Taking two rows allows 36 out of  64 arrangements, and three rows permit 102 out of 512. (At least that's what my first calculations show.) In other words, the set of all possible fields allows for a redundancy: If we want to transmit messages by sending pictures of Candy Crush fields, a $3\times 3$ field allows you transmit only up to 102 different messages, although there are 512 different possible arrangements. If now, during the transmission, an error occurs -- the flavor of a candy changes -- you might end up with an invalid field! Candy Crush Saga can be used as a nonlinear block code! Super-exciting, right?

At that, in turn, allows us to ask several questions:

• How should we encode a message efficiently? Is there anything better than just keeping a table of , say,102 fields? (There is.)
• How should we decode the message efficiently? That's a more difficult question if you don't want to store a table of all allowed arrangements. Maybe belief propagation can help here, as it does for Sudoku codes.
• What are the basic properties of an $(n,m,k)$ Candy Crush Code? What is the maximally possible rate given the game rule, i.e., what is the ratio between the number of possible and allowed arrangements? What is the minimum Hamming distance, etc.? How can we improve our encoder in order to guarantee a positive Hamming distance?
• Given that we change the flavor of every candy with a given probability $p \ll 1$ (and choose the new flavor uniformly among the remaining ones), what is the error probability? I.e., what is the probability that the changed arrangement is not detected as erroneous, because it also satisfies the game rules?
• What about error propagation of this code? I.e., if a given candy changes its flavor, how many "information bits" are effected? Can we still reconstruct part of the information, or is the whole block destroyed? (I guess the answer is no.)
• Connecting to the last question: What happens if we let one dimension of the field go to infinity? We would need sequential encoding and decoding techniques, such as they are usual for convolutional codes.
• What happens to all of these topics if we span the field on a cylinder (such that the rules extend over one side of the field: two candies of a given flavor on one side rule out a single candy of the same flavor on the other side) or on a torus?

Most probably, the code thus constructed is crappy. But it is nevertheless a nice topic for a research internship, I guess. And it makes learning nonlinear codes for symmetric channels as fun as Sudoku codes do for erasure channels!

Polar Code ARE Fractal!

This is a post about very recent work that has not yet been reviewed, but is publicly available on arXiv. This is not science by press conference, but hopefully encouraging discussions and comments from other researchers in the field.

At least, that is what I found out -- I'm pretty confident of the correctness of the results, but, you know, mistakes happen all the time. If you feel that some of my derivations may have flaws, I'd be happy if you could contact me!

Alright, regarding the questions in one of my previous blog post, what have I found out? Here's the short version, for more details please take a look at the paper on arXiv:

• The set of good channel $\mathcal{G}$ is Lebesgue measurable, and its Lebesgue measure is $I(W)$, the capacity of the (unpolarized) channel. This is intuitive in the sense that a fraction of $I(W)$ channels will be polarized to perfect channels. From this immediately follows that the Hausdorff dimension of this set is one.
• The dyadic rationals are good and bad. This is because dyadic rationals have two possible binary expansions, one terminating (with infinitely many zeros) and one repeating (with infinitely many ones). While the former polarizes the channel to a useless one, the latter polarizes it to a perfect one.
• Even if we do not take into account the dyadic rationals, the good channels still form a dense subset of the unit interval. The reason is that between any two dyadic rationals we can find a rational number (with repeating binary expansion) which leads to a good channel. For the binary erasure channel we can also find a rational number leading to a bad channel, so we can say a little more about BECs.
• And finally, the set of good channels is indeed self-similar, in the sense that it is a subset of its (scaled and shifted) right half (and left half for BECs). This can be most easily explained by a picture:

This picture (generated by the following code, polynomial composition from this forum) shows the thresholds on the Bhattacharyya parameter for some values inside the unit interval: If the Bhattacharyya parameter is smaller than the threshold, then the channel will polarize to a perfect channel. It can be seen that the right half (top) is an upper bound on the original set (center), which is (for BECs) an upper bound on its left half (bottom).

The most useful tools to derive these results were results about the binary expansion of real numbers, about fixed points of dynamical systems, and the Tal-Vardy polar code construction technique.

Convolution with Deltas - A Word on Notation

Mathematical notation is important. This is true even more so if we consider the convolution between two functions or between two sequences. In particular, if $f$ and $g$ are two functions, we write for the convolution

$$ h(x) = (f * g)(x) $$

whereas if $\{a_n\}$ and $\{b_n\}$ are two sequences, the convolution can be written as

$$ {c[n]} = {a[n]}*{b[n]}. $$

What should not be done in any circumstance is to write the convolution of two functions as

$$ h(t) = f(t) * g(t). $$

Why not? Well, because the convolution operator $*$ does not operate on value but on functions; $f(t)$ and $g(t)$, however, are values. That can be easily seen by inserting $t=3$ in above equation. We get

$$ h(3) = f(e) * g(3) $$

which obviously does not make any sense. The equation

$$ h(3) = (f*g)(3) $$

is the only appropriate way of writing this. In stark contrast, take a different unitary operator, like addition. For addition one can easily argue that the value of the sum of two functions at a given point equals the sum of the values of the individual functions: Addition works on values, i.e.,

$$ h(t) = (f+g)(t) = f(t)+g(t). $$

Still, many excellent textbooks on signal processing (even the ones from Oppenheim and Schafer and from Vetterli) make use of this "abuse of notation" for convolution. The reason is that as soon a Dirac (or Kronecker) delta enters the game, the famous convolution property pops up somewhere. In incorrect notation, this property can be stated as follows:

$$ h(t)=f(t) * \delta(t-T) = f(t-T) $$

Finding a correct notation is not easy. I found a few helpful comments on stackexchange. I will add my idea at the bottom, please judge yourself which you like the most. I have to admit that actually none of these is really satisfactory...

1. One commenter suggested to introduce the shift operator $T_T$, i.e., $T_T$ is the function mapping $t$ to $t-T$. Then, $\delta(t-T)=\delta(T_T(t))=(\delta\circ T_T)(t)$ and we get $h(t)=(f*(\delta\circ T_T))(t)$.
2. Another commenter proposed to write $h(t) = (f*\delta(\cdot-T))(t)$.
3. My idea is to define an ensemble of functions $\delta_T(t):=\delta(t−T)$ and then write the convolution as $h(t)=(f*\delta_T)(t)$.

While my comment might give the shortest notation, it is not as general as the one with the shift operator. I would have problems, e.g., to write the convolution of a function with its time-reversal, i.e., (in bad notation), $h(t)=f(t)*f(-t)$. If we introduce a time-reversal operator $R$ for which $R(t)=-t$, we could write the convolution easily as $h(t)=(f*f\circ R)(t)$.