Author Archives: yuegaogao

Random walk

George Polya was a Hungarian mathematician who made contributions in many branches of mathematics, among which was probability theory. In this blog we will discuss the “Random Walk” problem in probability. What is interesting is that George Polya actually first theorized this problem by accident.

George Polya was at that time a professor at a university in Zurich, Switzerland. The beautiful landscape there helped him develop a habit: taking afternoon walks in local gardens. One day, when he took his afternoon walks, one strange thing happened: he met a young couple six times. Well, I don’t know how large the garden was and how many paths were there, but this coincidence did surprise our mathematician. He was wondering how could this be possible, considering that he was then taking a random walk. After he mentioned this to his wife, he decided to do some research on the probability regarding random walk. His research actually established a new topic in probability theory.

Now let’s begin our discussion about the random walk problem with the simplest case. Consider one object moving along a straight line. Our assumptions are that this object can only move leftward or rightward, and the distance it moves each time is just one unit. For each time, it has a 50% chance to move leftward and a 50% chance to move rightward. A random walk model is thus created. And now we can ask: if when the object return to the starting point, the movement will end, then what is the probability that the object could return to the starting point? Thanks to George Polya’s work, the answer is 100%. Although some people may think this is unlikely, that’s only because when we think about this problem, we have a pre-assumption that the time is limited, or finite, which is always true in our real life. However, this mathematical model sets the time as endless, so it means when there is enough time and the object keeps moving endlessly, at last it will almost always return to the starting point.

When combining this theoretical conclusion with real life experience, mathematicians created the so-called “Drunken Man Going Home” problem. Assume there is a drunken man. He comes out of a bar and walks randomly along the line connecting his home and the bar. Once he gets home he will stop. Then what is the probability that the drunken man could finally get home? The answer to this funny question is still 100%. The math model of this problem is equivalent to the previous one. Because when time approaches infinite, the different positions of fixed points on the line actually make no differences. In my own words, any finite number in front of infinite vanishes to zero. So in this case, we just move the ending point from the starting point in the first example, to a new fixed point which denotes the drunken man’s home in the second example. The result keeps unchanged.

But mathematical problems always go from simple cases to complex cases. In the original random walk along a straight line, if we change the condition from “along a straight line” to “in a two-dimensional plane”, the complexity of this problem will definitely increase. If we change the condition to “in a three-dimensional space”, the complexity of this problem will increase dramatically. And the answers to this problem also change. The law is that, when the dimension increases, the chances that the object could get back to its starting point decreases, with the assumption that other conditions keep unchanged. For example, for a three-dimensional space, the probability is 34%; for four-dimensional space, the probability is 19.3%; when the dimension reaches eight, the probability that the object can get back is only around 7.3%. This means that there is only a lucky “drunken man”, who could always find a way home; there is no lucky “bird”: in a three-dimensional space, if the bird flies randomly, its chance to get back to its nest is much smaller! (Even if it could fly endlessly.)

Some people may cannot help ask, what can the theorem on random walk be used for. Well, obviously it is not developed to help drunken men feel confident when they need find a way home. It does have very wide applications in various areas. I will broadly list its applications in three different areas.

In economics, the theorem on random walks generates a hypothesis called “random walk hypothesis”. With the help of this hypothesis, economists could construct math models to research factors affecting shares price and the change of shares prices. It is quite understandable because randomness is q characteristic of the stock market.

In physics, the famous Brownian motion can apply the theorem on random walk to achieve the purpose to simplify the system. Since molecules move randomly to every direction, if we make an assumption that the molecules will only move to a finite number N directions, then the problem can be converted to a random walk problem in finite dimensional space. We could estimate the case in real physical world through our approximation in theoretical random walk models.

In genetics, a random walk could be used to explain the change of genetic frequency — a phenomenon that finally leads to genetic drift. Because gene mutation is always random, when we view the original gene pool as a point in a multi-dimensional space, then each gene mutation will generate a new gene pool, which can be viewed as a new point that forms through the original point’s random walk. After countless random walks, we could use the computer to draw pictures that show the trajectory of these abstracted points. The trend and some important characteristics of a gene drift could be described by this.

Randomness is everywhere in nature. At first glance, randomness connotes lack of order, unpredictable and uncontrollable. However, after mathematician’s great job, we do gain many laws and theorems on randomness. Random walk now has very wide applications in various disciplines, and we must attribute this partially to the coincidence happened to George Polya.

Reference:

  1. http://www.math.wichita.edu/history/men/polya.html
  2. http://www.guokr.com/article/53059/
  3. http://en.wikipedia.org/wiki/Random_walk

Reflections on Zeno’s Paradox —— A Problem about Geometric Series, or Not?

Our knowledge of mathematics develops along with the long history of human civilization. Ancient Greece is usually considered as the cradle of western civilization and the birthplace of mathematics. Here I will discuss the famous Zeno’s Paradox, an intellectual legacy we inherited form those great thinkers in ancient Greece, whose philosophical thinking has been energetic and attractive since ancient times; Then I will have a brief introduction about the “solving” of the paradox using geometric series; In the end I will show that, in some sense, the paradox has not been fully unraveled, by reference to another problem proposed by contemporary scholars. I believe the charm of mathematics will be presented after these efforts.

The ancient Greek philosopher Zeno once created quite a few paradoxes to show his skepticism about some common phenomena. He thought plurality and change were not a universal truth, and in particular, motion was only our illusion. Among his paradoxes that survived today, most of them have equivalent math models. So I will pick up one of them, “Achilles and the Tortoise”, to represent his logic.

The problem is like this: Achilles, the most famous Achaean warrior in Homer’s Iliad, the “swift-footed” hero, is chasing a tortoise. Suppose the initial distance between them is 100-meters, and Achilles’ speed is 10 m/s while the tortoise’s speed is 1m/s. After the chasing begins, Achilles will spend 10 seconds to finish a first the 100-meters. Then he will be at the spot where the tortoise was, at 10 seconds ago; In this period (10 seconds), the tortoise also proceeds 10 meters. Then, to finish the second distance, 10 meters, Achilles spends 1 second, while in the same period, the tortoise proceeds 1 meter; Then it goes on, every time Achilles reaches the tortoise’s previous spot, he still needs to chase more because in that period the tortoise proceeds to another further spot. Hence, Zeno concludes, in this case, Achilles will never overrun the lucky tortoise, which is a very bizarre conclusion against our common sense.

This paradox raised in history of great interest. Many scholars tried to give an answer or explanation, including Aristotle, Archimedes, Thomas Aquinas, etc. The joint efforts of philosophers and mathematicians did not succeed immediately. Without the help of rigorous mathematical tools, their solutions cannot resist questioning from skepticism. To make it more clear, philosophical thinking alone could hardly solve this problem; even if it accomplished so, to convince others to believe this will be no less difficult. Immanuel Kant in his Critique of Pure Reason mentioned that rationality is not omnipotent. It has its own structure of a priori knowledge, and after itself combined with a posterior experience, it becomes useful knowledge, which guides our cognition. However, due to the nature of human’s longing for perfection, eternal, and universality (I would like to add “infinite” here), we are inclined to abuse our rationality and expands it to areas that it in fact does not apply. This is to say, human rationality arises from very specific experience, and is applicable there; but due to our preference, we create some concepts (like “perfection”, “eternal” and “universality” I mentioned above), which is non-existent in real life and also beyond rationality’s realm. But we are so confident and accustomed to our rationality that we apply it to those concepts generated by ourselves, without noticing it is not applicable there. After the abuse, confusion subsequently follows.

I really admire Kant’s genius in his noticing that a critique of human reasoning itself is very much needed. And I would use his theory to help form my personal understanding about this problem. But I will leave it here and deal with it later, after the introduction of the rigorous mathematical proving with respect to this problem.

Thanks to the invention of calculus and the epsilon-delta language, we now have the rigorous mathematical tool to deal with problems about infinity. A brief solution is to use geometric series. With respect to the “Achilles and Tortoise” problem we mentioned above, the time that Achilles needed to catch up with the tortoise can be represented as:

series

This means Achilles could overrun the tortoise after approximately 11.11 seconds. Thus, the sum of a series with infinite terms, are quite possibly finite, which may be beyond our predecessors’ understanding. But, does this problem stops here? Some modern scholars believes not. Why, because we are not sure what is Zeno’s true meaning. This is to say, the result of the formula may not answer Zeno’s question. Let me here give an example, which is called Thomson’s Lamp: suppose there is such a lamp with a toggle switch. After you start the game, it’s switched one after 1 minute, then switched off after half minute, then on after fourth minute, then off after eighth minute, and so goes on. The sum all the time we spend in the game is 2 minutes, according to the same method about sum of geometric series above. Then, one question follows: After exactly two minutes, is the lamp on or off?

This time we find it’s also very difficult to answer this variation of Zeno’s paradox, even if we know geometric series. And because of this, I believe to use geometric series could give a result, but could not solve the problem about the process, which may be Zeno’s real point. And Kant’s argument gives me guidance in understanding this paradox. Also, there is a scholar making this point more explicitly: according to Pat Corvini, this paradox arises from “a subtle but fatal switch between the physical and abstract”. When we expand our mathematical abstractions to the physical world, even it’s applicable almost everywhere, with respect to some concepts, it’s quite unimaginable and confusing. This time, we may still need mathematics as well as philosophy, to finally solve this paradox.

References:

Binmore, K. G. & Voorhoeve, A. (2003). Defending Transitivity against Zenois Paradox, Philosophy and Public Affairs, Vol.31(3), pp.272-279

John, L. (2003). Key Contemporary Concepts from Abjection to Zeno’s Paradox, Ebrary, Inc.

Wikipedia, Zeno’s paradoxes, http://en.wikipedia.org/wiki/Zeno%27s_paradoxes

Parallel Lines

I learned the parallel postulate in middle school. The best known equivalent of the postulate is attributed to Scottish mathematician John Playfair, and it says that “in a plane, given a line and a point not on it, at most one line parallel to the given line can be drawn through the point.”

The reason that I have a special impression on this postulate may be probably due to a popular metaphor in my middle school period. That metaphor related the parallel lines with the mutual feelings between girls and boys: when a girl and a boy cannot stay together, or they do not develop a mutual affection, we say that they are like two parallel lines. No matter what the two parallel lines “do”, they cannot have an interaction. Similarly, for the two unlucky people, no matter what they do, they can never fall in love with each other. I have to say this metaphor describes a tragic situation and sometimes I do not feel satisfied with the “tragic” destinies of the two parallel lines. Fortunately, as my mathematical knowledge grows, I do find that in some other branches of geometry, the seemingly unbreakable law in Euclidean geometry no longer holds. Among the new branches are hyperbolic geometry and elliptic geometry, which will be the main topic of this blog.

Before we talk about non-Euclidean geometry, let me have a brief introduction to the differences between non-Euclidean geometry and Euclidean geometry. The fundamental difference between them lies in the parallel postulate. We already stated a widely adopted equivalent of parallel postulate in the beginning of this article. For two thousand years after Euclid’s work was published, many mathematicians either tried to prove this “fifth postulate” (in Euclid’s Element) or tried to show that it’s not necessarily true. Actually, even in Euclid’s own book, this parallel postulate was left unproved; Also, unlike the first four postulates, the fifth postulate — the “tragic” parallel postulate, was not being used to prove his following theorems in the book. A breakthrough in this topic came out in the 18th century. A Russian mathematician,  Nikolai Lobachevsky, developed the hyperbolic geometry. His most famous contributions are in two aspects: he convincingly showed that Euclid’s fifth postulate cannot be proved, and he presented hyperbolic geometry to the world.

Multiple parallel lines in hyperbolic geometry. Image: Vladimir0987, via Wikimedia Commons.

In the original parallel postulate, we said for any given line R and point P, there is exactly one line through P that does not intersect R; i.e., parallel to R. In hyperbolic geometry there are at least two distinct lines through P which do not intersect R, rendering the parallel postulate invalid. Hyperbolic geometry may be against common sense at first glance, because usually, our recognition about the shape of a space is limited to Euclidean space. However, hyperbolic geometric space does exist, one example is the saddle space with a constant negative Gaussian Curvature. Hyperbolic space is possible in dimensions that are larger than or equal to two. It is curved — the reason why it differs from Euclidean planes — and is characterized by a constant negative curvature. Euclidean spaces are always with zero curvature. To make it more vivid in my own words (which very likely will not be so rigorous), if we observe a small region in the hyperbolic plane, it looks like just a concave plane. And when you draw a triangle in this concave plane, the sum of its inner angles is always less than 180 degrees. This is also a proved theorem in hyperbolic geometry.

In elliptic geometry, we have the following conclusion: “Given a line L and a point p outside L, there exists no line parallel to L passing through p, and all lines in elliptic geometry intersect.” This means we can never find any parallel lines in elliptic geometry. This kind of geometry together with hyperbolic geometry, perfectly form a counter example of the parallel postulate’s assumption “there is one and only one parallel line…”: in elliptic geometry, there is more than one parallel line, and in hyperbolic geometry, there are none. Examples of elliptic geometry are more common in our real life than hyperbolic geometry. One example is the surface of Earth. A line in such a space becomes a great circle (a circle centered at earth’s core). When you draw a line through point P and if P is away from line (great circle) L, the new line you get will be a new great circle, and it will always have two intersections with great circle L, because any two great circles on the surface of sphere will have two intersections.

Here we have three pictures visualizing the relationship between Euclid’s geometry, hyperbolic geometry and elliptic geometry.

Image: Joshuabowman and Pbroks, via Wikimedia Commons.

The establishment of non-Euclidean geometry is the outcome of many generations’ collective endeavors. For example, classical era’s scholar Proclus commented some attempts to prove the postulate, esp. Those attempts tried to deduce it from the previous four postulates; Arab mathematician Ibn al-Haytham in the 10th century, tried to prove the theorem by contradiction; in the Age of Enlightenment Italian mathematician Giordano Vitale and Girolamo Saccheri both contributed new approaches to this problem although they finally failed; Gauss and Nikolai Lobachevsky (we already mentioned him above) also joined the sequence — the latter finally finished this task by establishing a new geometric branch. This mansion was built over such a long time and I am fortunate to feel part of its grandeur and beauty.

So for those suitors who complain their misfortune that their dream lovers and they are like two parallel lines, I think you are too pessimistic. You can imagine yourself being in a elliptic geometric space. Then as long as you try your best, you will always have an intersection with the other line. I am not sure whether this will convince those guys and give them confidence. For me, I am now feeling happy and believe that everything is possible in our real world, just like that everything is possible in mathematics. The story about seemingly very simple parallel lines do make me feel the power and beauty of mathematics.

References:

  1. http://en.wikipedia.org/wiki/Non-Euclidean_geometry
  2. http://en.wikipedia.org/wiki/Elliptic_geometry
  3. http://en.wikipedia.org/wiki/Parallel_postulate
  4. http://en.wikipedia.org/wiki/Hyperbolic_geometry
  5. H. S. M. Coxeter(1942) Non-Euclidean Geometry, University of Toronto Press, reissued 1998 by Mathematical Association of AmericaISBN 0-88385-522-4.
  6. Hazewinkel, Michiel, ed. (2001), “Elliptic geometry”Encyclopedia of MathematicsSpringerISBN978-1-55608-010-4
  7. Weisstein, Eric W.“Hyperbolic Geometry”MathWorld.