Analysis · Mathematics

Banach Fix Point Theorem

Banach fix point theorem is a very powerful tool in mathematics, in particular, in functional analysis and in operator theory. I was studying for functional analysis earlier this weekend and came across it once again, even though I did not see it coming. We will first look at a few definitions, and then the theorem itself.

Let (X,d) be a metric space. A map T:X \to X is called a contraction if  d(T(x),T(y)) \le d(x,y); it is called a strict contraction the inequality is strict, or equivalently, if there exists k \in [0,1) such that d(T(x),T(y)) = k d(x,y).

As the name suggest, Banach fixed point theorem is a tool to find fix points for contraction mappings in complete metric space, and hence Banach spaces. The statement of the theorem is as follows:

Suppose (X,d) is a complete metric space. If T:X \to X is a strict contraction, then there exists a unique x^* \in X such that T(x^*) = x^*. Furthermore, for any $x_0 \in X$, if we set x_n = T(x_{n-1}) for all n \in \mathbb{N}, then \lim_{n \in \mathbb{N}} x_n = x^*.

The proof on Wikipedia is pretty concise, so we will not talk about it here.  It is often used in differential equations to find fixed points of the equation itself. There is yet another clever application that I encounter earlier this weekend, it is used in a theorem by Stampacchia in functional analysis. Maybe we will talk about it next time.

Advertisements
Mathematics · Topology

Dense and Nowhere Dense Sets

Found a neat properties for dense and nowhere dense sets in functional analysis assignments recently. Suppose (X,\tau) is a topological space, and A \subseteq X is an arbitrary subset. We say that A is dense if the closure is the whole space itself, i.e. \bar{A} = X; we say that A is nowhere dense if the interior of its closure is empty, i.e. \mathring{\bar{A}} = \emptyset.

Now, we can also think about closures and interiors in terms of their complement. We shall denote by X \setminus A to be the complement of A instead of the usual A^C; the reason is obvious once we get to the main part, I promise.

Usually in topology, the interior and closure of a set A, are defined to be the union of all open sets contained in A, and the intersection of all closed sets containing A respectively; in other words, they are the largest open set contained in A, and the smallest closed set that contains A respectively. In terms of complement, we have the interior \mathring{A} = X \setminus \bar{A} and \bar{A} = (X \setminus A)^{\circ}, this is not hard to prove.

If A is dense, then the complement has empty interior. We have

\bar{A} = X \iff X \setminus \bar{A} = \emptyset \iff (X \setminus A)^{\circ} = \emptyset

This is not surprising and is pretty standard. On the other hand, we claim that A is nowhere dense if and only if its complement contains an open dense subset of X. This is slightly more work, we have

\mathring{\bar{A}} = \emptyset \iff \bar{X \setminus \bar{A}} = X \iff \bar{(X \setminus A)^{\circ}} = X \iff  (X \setminus A)^{\circ} = X

And since the interior itself is an open set, hence (X \setminus A)^{\circ} is the open dense subset we desired.

This is pretty useful result when trying to prove Baire Category’s Theorem, or for an application of the Baire’s Category Theorem. All the best doing your assignments!

Nom nom noms · Random

Food in Zurich

Everything in Zurich is expensive. This is a general statement from a lot of people that had been to Zurich when you first ask them about Zurich. As a student, that is a total nightmare, as one has to spend approximately 1750 CHF/month (current conversion rate as of writing: 1 CHF = 1.0584 USD) to live in Zurich.

Luckily, for the first week I arrive in Zurich, I manage to spend only 7 CHF per meal on average some meals are cheap because student pricing provided by ETH Zurich and University of Zurich, but that is not the point. Perhaps adjusting my diet and eating local food helps. Generally, following locals’ food habit is a good way to save money.

One other complaint that I hear from Asian people is that the bread are really hard compared to the ones in Asia. I’d like to point out that there are literally hundreds of breads to choose from. There will be the types of bread that you are looking for if you look hard enough. Alternatively, you can try each and every bread to decide which bread has the best taste and texture; by the time you try all of them, you will already get used to eating bread usually by the forth or fifth bread, you have a general idea of how hard each bread is just judging by its skin and the colour.

Visit Migros (Some market that is like Walmart, but better quality. Perhaps like Valumart in Ontario, Canada) for cheap food, they alternate the deals every now and then so that poor students like me can get a change of flavour once in a while. There are also tricks in getting quality food in these markets, as long as you know how to ask, and where to look at. Some of the generic/off brand food actually taste as good as named brands, but costs half as much. For these brands you kinda have to try it and try your luck. Most of them taste pretty good though.

Finally, if you are a student, perhaps going to events is a good idea. These events will not feed you until you’re full, but at least you will not feel hungry in the middle of the day and have to spend a fortune for a sandwich. Or you can just take extra from the event and call it your dinner.Just kidding. Actually, don’t do it..

Game Theory · Information Theory

The Devil’s Chessboard (Problem)

DISCLAIMER: NO GOD, DEVIL, OR ANY SUPERNATURAL BEING OF ANY KIND IS HARMED IN THE PROCESS OF PRODUCING THIS ARTICLE. VIEWER DISCRETION ADVISED.DISCLAIMER: NO GOD, DEVIL, OR ANY SUPERNATURAL BEING OF ANY KIND IS HARMED IN THE PROCESS OF PRODUCING THIS ARTICLE. VIEWER DISCRETION ADVISED.

The Devil’s Chessboard is an information theory problem in game theoretic setting. As one may or may not have  heard before, the Devil’s Chessboard is a rather intimidating problem, or at least when one first learns about the problem. If one attempts to play the game (with the Devil) without any kind of strategy or by using pure luck, it is rather impossible to win the game as the probability of choosing the correct move is \frac{1}{64} (or about 1.56\%).

Furthermore, the problem can be extended to larger grids, which decreases the chance of choosing the correct move exponentially, if we choose to play the game by using only luck. In fact, some of these game theoretic problems does not even have a winning strategy (Note: Simply put, a winning strategy is a strategy in which the player(s) is(are) guaranteed to win.); in case a winning strategy exists, what is it; if the winning strategy does not exists, what is the best strategy to tackle the problem. In this article, we are going to examine the Devil’s Chessboard, and come up with the best strategy to play the game.

The Game Setting

Imagine this. You and a friend both studies mathematics in your undergraduate studies.  Envying your ability to reason, God decided to send both of you to the Devil. Contrary to the legend, the Devil did not send both of you to burn for eternity immediately. Instead, he would like to play a game with you. If both of you win the game, then you will be released and proceed with life. Otherwise, you will suffer for the rest of the eternity.

The game is as follows: there is an isolated room in which no communication to the outside realm is possible. In the center, there is a table, and on top of the table there is a 8 \times 8 chessboard. You and your friend are to follow the Devil one at a time into the room, where further actions will be taken. For simplicity, we will refer to A and B as first and second person that enters the room respectively.

Once A and the Devil are in the room, the Devil will perform the following steps:

  1. Seal the door (presumably with magic) so that no communication to the outside world is possible.
  2. Make 64 coins identical in colour, weight, etc magically appear on top each square of the chessboard; since it is done by magic, you cannot interfere with this process.
  3. The Devil then points at a square at random, and mark the position of the square on the chessboard as a proof; of course, the mark is invisible to human naked eye until the game is over.
  4. A is allowed to flip one coin on the chessboard, should s/he chooses to.
  5. A will be lead out of the room to avoid any form of collusion with $B$.

During this whole process, A is to remain silent, otherwise both of the players will be sent to Hell for eternity immediately.

Now B will enter the room with the Devil. After the Devil seals the room (again, with magic), B will get a chance to examine the board and then to pick a square on the board. If s/he choose the exact same square the Devil did, then both players are released immediately. Otherwise, both of you go to Hell. Finally, the Devil agrees that he will not cheat by manipulating the marked square; hoping that you succeed and to annoy God, the Devil allows you and your friend to have a discussion to come up with a strategy before the game starts.

Is there a winning strategy in which you and your friend will be guaranteed freedom? If there is, can you find out what the strategy is? If not, what would be the best strategy to maximize the probability of escaping Hell? The solutions will be posted next time.

Life · Travelling

First Impression on Switzerland

DISCLAIMER: I am not responsible for any sickness cause by individual stupidity and will not be held accountable for any such actions. By reading this article (partly or fully), you agree to the above conditions.

Arrived in Switzerland a day ago. It was a 17 hours trip, but thanks to the quality of my sleep, I do not have to deal with jet lag, at least for the time being. I am really glad that I do not have to deal with the constant damaging sunlight anymore. At least it is chill enough to actually wear long sleeves and not feel the heat, or sweat as if I just had a shower, or both.

One key difference that I notice between Zurich and other major cities is that there is no tall buildings around. There is no skyscrapers, glass buildings, or the typical skyline that one see when driving along the highway during the sunset. In fact, I have yet to see a building (Other than ETH Zurich, lol) that is taller than 5 floors. Calling it a humongous town instead of a city may not be too far fetched after all.

The breads here are great. Maybe it is just me, but the toasts here are actually fluffy and , soft, unlike some country that makes a dry and hard version of the bread I found here, or some other country that makes sticky and soggy toasts. Every meal since I landed had been, in one way or another, mainly bread. We shall see how many days I can go without having the urge to get some rice and cook it.

Until recently, I thought Germany cities has the best and cleanest water system. I was wrong. I was very wrong. In Germany, at best i would drink the water from a tap, but here in Zurich, unless otherwise mentioned, you can essentially drink from any moving body of water.  Saw a faucet on the street? Drinkable. Fountain in the middle of the street? Help yourself. Saw a bottle of water on a street car? Well, maybe don’t actually drink it in this case. Okay maybe don’t take the ‘any moving body of water’ above literally. My bad.

That’s it for now, tomorrow I will have bunch of new adventures to experience, and maybe share some interesting stories by the end of the week/month.