God’s big decomposition problem

I was going back through some old journal entries when I found this one. It was definitely entertaining enough to be blogworthy, so I made a few small edits to it.

If there ever was a God who is simulaneously good, omniscient, and sovereign, then it’s obvious that He does not operate on this world as a centralized controller. Human beings are not like the ocean’s waves that can be calmed by a single command, or the mountains that can be moved by a simple act of faith, or the universe that can be spoken into existence. Rather, we are autonomous agents with a significant amount of free will–so much in fact that our very existence has led many to doubt at least one of 3 characteristics of God described above. But what if instead, God worked in a decentralized manner? Then it is then possible for God to be good, omniscient, and sovereign, without having to control the outcome of every situation. I will use a model that stems from decomposition theory in operational research. Hopefully, tough questions like these that are hard to answer using conventional apologetics can be answered by modeling God’s purpose as a decentralized optimization problem. Suppose that God is trying to maximize some function, which we will denote “God’s glory”. “God’s glory” depends largely on human actions, but does not necessarily correlate with what makes each individual happy.* However, provided that the distributed mechanism is sound, the world will converge to “God’s maximum glory”. There are many popular distributed optimization approaches that exist, but for the sake of argument, I will just stick to the two most popular decomposition methods in engineering: 1) Dual decomposition: This is the mechanism that can be used to reveal God’s righteousness through judgment/punishment. Herein lies the idea of karma: if you break the rules, you get what you deserve. In dual decomposition, there are no constraints to free will. God does not say that you are incapable of sinning, only that if you sin, you will be “taxed” or “priced” for sinning. This provides both awareness and incentive for righteousness. A prime example of God’s dual decomposition involves the old testament nation of Israel: Seek the Lord, and be blessed; turn away from the Lord, and be punished. “Then you will know that I am the Lord your God, who brought you out of Egypt, out of the land of slavery.” 2) Primal decomposition: If God decides instead not to punish people, but to directly influence/change people’s nature, He can accomplish this through primal decomposition. In primal decomposition, each person’s utility is not only a function of his own actions, but also an external coupling variable introduced by a higher (possibly centralized) agent. Primal decomposition can also have numerous levels of hierarchy. Then what is God’s primal decomposition? This would be His kingdom coming through His spirit and love, a direct allocation of resources to anyone who believes. First, consider how His kingdom is built: it started with Jesus Christ, who dispersed knowledge of God by teaching 12 disciples and many others during his ministry. Through his act of love on the cross, he demonstrated God’s love to sinners. His believers went out and shared this message with others, some of whom became believers as well. Likewise, God’s spirit is what marks us as saved. This comforter and helper is the variable that couples us with God. After all, Christianity is all about the relationship. =) What are important lessons to take away from decomposition: Scale: Different things require different amounts of time to come to fruition, depending on how knowledge, righteousness, love, and spirit of God are distributed among agents. Different hierarchical levels may also communicate at different frequencies, thereby dispersing the knowledge/blessing at different times–possibly even years into the future. In other words, God has his own timing, and a believer in the distributed nature of God’s workmanship will know to wait on Him. Temporary setbacks: Distributed optimization does not always require the state to improve during each iteration, only that in the end, “God’s glory” will be maximized. In other words, there is a place for suffering in a distributed environment, and suffering can often be on a path that leads to good. Therefore, one should not give up hope just because he is going through a tough trial. Miscellaneous distributed structures in Christianity: -The church (or gathering of believers) is and has always been run in a distributed fashion, usually with a shepherd periodically overlooking them. Just think about the apostle Paul and letters he writes to various churches. -Prayer: this is the channel given to distributed agents to communicate directly with the centralized agent, or God. If you believe in prayer, meaning that God listens and answers, then this is an extremely powerful means of communication. Some thoughts left out of this rambling that may be considered in the future: -I did not consider the dynamic nature of human beings. In particular, there are other game theoretical results for multi-agent systems where future reward is considered. In general, temporally-minded people have beta < 1, meaning reward that can be modeled in their minds as R(0)+beta*R(1)+beta^2*R(2)+…., where R(0) is the immediate reward, and R(t) is the reward at time t in the future (a continuous model can be used). Eternally-minded people have beta = 1. In general, people have beta < 1. God’s timelessness probably corresponds to time-averaging (beta = 1), so it is often difficult for humans with myopic vision to discern the will of God.

Justice Router ftw?

I can’t believe I still have this amusing rant from a few years back:

The Justice Router: A New Approach to “Fair” Queueing

Inspiration

For a whole year, I have been living off of Verizon DSL and sharing my connection with 8 people. Verizon is pretty lame; it caps our upload at approximately 10kB/s, meaning that between the 8 of us, resources are scarce. Unfortunately, among the 8 of us, there are resource hogs who like to download 5 movies at a time while BT-ing 3 other movies, which floods our network with tons of ACK packets and slows our internet speed to a complete halt. To give you an idea of how terrible this situation is: my average ping time is around 1/2 second. On a bad day, my ping time is around 3-5 seconds.

First of all, I am very respectful toward network usage. If I find that the ping time goes above 200-300 milliseconds, I will graciously cancel one of my two downloads or turn off AIM. Moreover, when I am playing a game, I make sure that I do not download or upload anything. My upload rate is usually below 2kB/s at a “busy” time.

Unfortunately, just because you follow rules of your own doesn’t mean others comply to it. I decided to go talk to people individually about network usage. Unfortunately, one particular person, who will go unnamed for now, gave me an attitude. Apparently I can’t talk sense into some people. To this day, he still hogs the bandwidth without regards to others.

Thanks to him, I’ve developed a new idea for queueing/packet-switching networks. I propose a method which I call Justice Routing.

Some background information

Normally, when people describe a fair queueing system, their aim is to get packets through the network with a speed proportional to their length. Therefore, every packet (of the same type) has equal transmission rate in bits/second. Most packet-switching networks have priority classes for video/sound/data packets. Streaming video packets generally get high priority, because the application on the other side needs to constantly buffer these packets to provide high quality of service (good display). Fair queueing and priority queueing are age-old problems, but they fail to address the bigger problem in a shared network–that is, network hogs.

Why does network hogging increase latency so drastically? To analyze this, we assume an M/G/1 queueing system and notice that the waiting time is proportional to the second moment of a packet service time, and inversely proportional to 1 – (arrival rate/service rate). Never mind the first part; the second part (inverse proportionality) is more important. Suppose someone is uploading ACK packets at a rate of 500 every second on average, and the router can process 1000 packets per second on average. Then 1 – (arr/serv) = 1 – 500/1000 = .5. Take the inverse, and we get 2. Now suppose someone adds a couple BT’s to his downloads and uploads at a terrifying rate. Now we have 950 packets being sent out every second. The service rate is still 1000 per second. Now we get a factor of 1/(1-950/1000) = 20! Our waiting time has increased tenfold, even though the total upload rate has not even doubled. Try increasing the upload rate another 50 packets/second, and you get an infinite waiting time! Notice that you get a much better performance downloading at half your rate than you do at full rate, hence having 1 or 2 concurrent downloads is considered good manner, while flooding the network with 8 downloads is very bad manner. Fortunately, buffers are limited in size and often smartly designed so that they drop packets if queue sizes grow too large. Using an exponential backoff mechanism (e.g. TCP/IP) for retransmission, we’ll never have infinite waiting time. But we will still have terrible 10 second waiting times. WHATEVER SHALL WE DO???

Solution–The Justice Router

The Justice Router will analyze the source and type of each incoming packet and keep a counter for each source. Every few seconds, the router will compare the counters with a certain threshold and then reset the counters. If Mr. Bacon’s counter number is higher than the threshold, his computer will receive a violation. His upload will be capped at a lower rate each time a violation is received. Violations are handed out ever so often, so that eventually a stubborn network hog will have his connection reduced to a very small fraction of the total bandwidth. However, if he behaves himself, his violations will eventually go away after some time, and full network capacity will be restored. While administrators often block or disconnect people for flooding, this router will administer justice by itself.

Unfortunately however, the design of the Justice Router is inherently “merciful.” If a person’s upload is capped, he will be less likely to receive a violation. Below a certain rate, he will no longer receive any more violations. Thus the router’s violation scheme ought to be adaptive. The next section describes a scheme for harsher sentencing.

Three-strikes-and-you’re-out

In order to exact greater punishment, I propose the three-strikes-and-you’re-out policy. When Bacon receives “mercy” for the first time (i.e. his upload cap goes below the violation threshold), he will receive a strike. After the cap increases again and decreases below the threshold, he receives another strike. After three strikes, Bacon is disconnected from the router for the same amount of time that he has been connected since the beginning of his router farm life. If there was a year of Bacon, there will be a year without him, and everyone will be happy and healthy. Now keep in mind that after Bacon is readmitted to the router, the router still keeps track of his complete history. If within the next 30 minutes, he gets 3 strikes, Bacon will be out of the Justice Router for another 1 year and 30 minutes.

Justice is served with a plate of ham and spicy pork.

The Probability Factor in the Creation vs Evolution Debate

In this post I want to examine the debate of creation vs evolution from a different angle. I am neither in favor of one or the other, but before you dismiss me as an ignoramus, hear me out. Indeed, I am somewhat Christian by “faith”, though I do have several qualms with philosophical aspects of Christianity. Nevertheless, in the realm of science vs religion, I believe that there is a very important aspect that has been left out of the public debates, most likely because the average listener/debater is not an expert in probability theory. However, I will try to present this argument in a simplified manner using a numbered outline..

1) The theory of evolution is often viewed at a very macroscopic model with too many unknown variables and is thus difficult to verify, even if the probabilistic principles driving various aspects of the theory are sound.

At the top level, you have natural selection determining which animals “tend” to survive and which “tend” to die. This is largely based on the existing environment and the survival and propagation of a particular species, which is correlated with certain “favorable” traits obtained through either mutation or sexual reproduction. Note that the number of factors (e.g. environment, interactions and behavior, genetic traits) are huge and therefore very difficult to analyze jointly. Experiments can only verify that certain aspects hold statistically in isolation (or using only a small subset of factors). Complete, joint experimentation is too complex and takes too long to conduct.

2) There exists a truly probabilistic element in the universe, namely, that particles exhibit probabilistic wave functions.

I’m not a physicist, but from what I know that according to quantum mechanics, before observing any particle, the particle exists only as a probabilistic wave function which collapses upon observation. It is entirely possible (though not probable) for a baseball to be thrown horizontally and yet curve upward into space. In any case, to analyze sexual reproduction or gene mutations at the quantum scale is intractible. Hence evolution is still modeled based on statistical experiments at a higher level. Hence, while some mistaken quantum physics to support the theory of evolution, this is not true, though it is philosophically “consistent” with evolution.

3) What is often measured is the “average case” or “high probability” behavior, not the “ground truth”.

This is hopefully self-explanatory and is related to the above argument (intractibility). A simple illustration is brownian motion (the precise behavior of molecules) for an object at rest (a macroscopic, average behavior). One might perform kinematic experiments based on modeling the object as a whole, instead of accurately measuring the precise locations and trajectories of its individual particles.

4) The laws guiding the universe are assumed to be stationary.

Stationarity is a concept derived from the theory of random processes which states that what has happened, is happening, and will happen in the future (as time goes to infinity) will always follow the same distribution. Stationarity is an extremely important assumption required for the scientific method to hold, since, given that a result is validated, then it has always held in the past, holds in the present, and will always hold in the future. Otherwise all experimental results are meaningless.

5) 3-4 makes a strong case against young earth creationism, but only “with high probability”.

Stationarity can make a strong case against young earth creationism for two reasons: it supports the big bang with high probability. If the physical laws have always held as they do now, based on astronomical data there should be a singularity (with very high probability) around 13-14 billion years back in history. It also makes a case for the accuracy of radioactive carbon dating.

6) Interestingly, young earth creationism is also consistent with scientific theory based on 3 and 4.

Why? If the world indeed operates based on nondeterminism, then however negligible the probability of young earth creationism, there is still a non-zero probability that universe arranged itself accordingly in 7 days, just as there is a negligible (but non-zero) probability that the universe exists in its current state at the present time! To understand this, one needs to remove the paradigm of thinking in terms of “wholes”. We are not discussing the average behavior of macroscopic objects, but rather each individual quark, boson, muon, etc. in the observable universe. The reason why our observed universe has near zero chance of existing is a simple consequence of the sheer number of particles in the known universe, and the fact that they each exhibit probabilistic wave functions.

Hence, even if observable evidence points to the big bang “on average”, the universe need not always behave “on average”. Christians believe that with God all things are possible (though not necessarily probable)–and in this case God needs only operate within His own designed physical rules! Hence young earth creationism is consistent with scientific theory under the “guidance” of a non-quantum Cause.

7) Young earth creationism can not be experimentally verified. (i.e. it is philosophically valid, but can not be considered science.)

Unfortunately, due to its extremely low probability of occurence, it is nearly impossible to experimentally validate the 7 days of creation theory. The only tools that can be used to support young earth creationism is suggestive evidence (e.g. almost every nation had a “dragon” in its mythology/folklore, suggesting that humans might have lived among dinosaurs). Otherwise, it must be accepted by “blind faith”.

Another way to think about it is the following: If you saw a “miracle”, could you repeat it?

Conclusion: I am not the most eloquent writer, but hopefully this post has helped you to think “outside the box” regarding the debate that has been all over the news since… 1844. And hopefully those of you who are on different sides of the spectrum can develop an appreciation for one another’s viewpoints.

Markov Chain Madness!

What are Markov chains? In a brief, not so accurate summary, Markov chains is a probabilistic modeling technique where you try to determine the probability of being in a certain state given that you were in a certain previous state. Like, if you’re in a happy mood now, you’re 70% likely to be depressed tomorrow, and 30% likely to be happy again tomorrow. That’s a pretty dismal sounding Markov chain though. =(

http://en.wikipedia.org/wiki/Markov_chain

Apparently there are many really cool applications to Markov chains, such as algorithmic music composition and parody generators. Actually, parody generators might look familiar. They are the annoying ones that tend to make it past the spam filters in your emails. =(

Depressing image

Wow, now I’m really depressed. Even my precious Fourier Transform fails at love!

More can be found here.

Really Cool Traffic Paradox!

Did you know that shutting down a road can actually improve traffic in a city?

The phenomenon is known as Braess’ paradox, which states that adding an extra link/road in a network/city could increase overall latency. For a graph theorist, the idea is highly counterintuitive since all the previously existing flows still exist. The reason why this happens, however, is due to the Nash Equilibrium induced by SELFISH drivers. Yes, you know… like… EVERYONE?

Let’s use a simple toy example below (click to enlarge) [1]:

Here, let us assume that all traffic is flowing from s to t along two roads through points v and w. The total traffic is 1 unit (The traffic may consist of many smaller unit flows, e.g. 10 cars contributing 0.1 units of traffic each.). The function l(x) indicates the latency (say, in minutes) induced by x units of traffic along that road; hence in (a), the optimal traffic flow would be to have half the cars choose the top path, and half choose the bottom path. The resulting latency is 1.5 minutes for every driver.
Now, suppose a one-way street was built to connect v to w, as shown in (b). This street is infinitely wide and has no speed limit, and hence cars can essentially “teleport” from v to w with 0 latency. What is the new optimum? Surely, it is at least as good as the old optimum, and in fact it is the same as the old optimum. People could just pretend the one-way Warp 9 road does not exist. However, this will not happen if people do not cooperatively decide to do so. If no driver can communicate (in a friendly way) with other drivers, which is usually the case, the following occurs:

Suppose there are 10 cars. Car #1 sees that it can choose s->v->w->t and make it in 0.2 minutes. Car #2 sees that car #1 has chosen its route, but it sees that s->v->w->t is also beneficial because he can share the road with car #1 and still make it in 0.4 minutes. The same goes for the other 8 cars. In fact, no car will want to choose s->v->t or s->w->t at any time because it will ALWAYS be slower than chooseing s->v->w->t. (They are selfish after all.) Therefore, the result is that everyone chooses the same path, and everyone gets to the destination in 2 minutes.

Hence, adding an extra road causes everybody to lose 30 seconds. WEIRD HUH? So next time you see construction on the road, take a detour and don’t necessary expect a heavier delay than if construction did not exist. You might get to your destination faster!

Such is the price of anarchy.

[1] Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002