The Right Way!

It’s been an amazing March and the journey so far has been exhilarating. Fighting dragons, crossing bridges, running races, going in “Strange Loops” etc. Looks like an excerpt from a fairy tale adventure except for the fact that the prince (supposedly me) is definitely not living happily anymore. Big thanks to a couple of colleagues (that includes my mentor Mr. Pai) who helped open the window:

CreateWindowEx(
        WS_EX_CLIENTEDGE,
        g_szClassName,
        “Hello Linear-Programming”,
        WS_OVERLAPPEDWINDOW,
        CW_USEDEFAULT, CW_USEDEFAULT, ∞, ∞,
        NULL, NULL, hInstance, NULL);

Well! It all started when my colleague got this wonderful problem from his friend. It went like this:

“What would be the maximum messages that you could send using any given number of senders and dispatchers with varying capacities plus other defined constraints?”

This was the “Larger than Life” generic version of the problem that we yearned to crack. The real problem (the one I believe I have solved rightfully below) was too tempting to be conquered, especially after having slain the dragon (I was able to contain a trojan-horse in my PC without having to forfeit/format my kingdom/hard-disk), I ended up with a naïve procedure that of iteratively, proportionally dividing the load based on sender/dispatcher capacities. My mentor knew from day one that, this was a classic Linear Programming (LP) problem (which I couldn’t fully comprehend then) and he was quite adamant in trying to get this solved “the right way”.

Thus began my captivating journey on Mr. Well’s “Time Machine” across Prussia, along with Euler trying to cross all the 7 Konigsberg bridges “exactly once” (Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani) and Greece, where I pitted against the tortoise in place of Achilles trying to prove Zeno wrong and then going in “Strange Loops” over Escher’s paintings (Godel-Escher-Bach: An Eternal Golden Braid by Douglas R. Hofstadter). And finally after pounding through various other Finite Mathematics & LP books ranging from (A Beginner’s Guide To Finite Mathematics: For Business, Management, And The Social Sciences by W. D. Wallis) to (Linear and Nonlinear Programming: International Series in Operations Research & Management Science by David G. Luenberger & Yinyu Ye), I finally was able to comprehend the problem at hand, and more importantly confront the beast that we intended to leash, “the right way”.

The Problem:

Three senders S1, S2 and S3 can send 50, 100 and 60 messages respectively. These senders need to consume three dispatchers namely D1, D2 and D3 with message capacities 40, 80 and 60 respectively. Determine the message distribution across the senders and dispatchers for maximum throughput provided:

  • S1 can consume only D2 and D3 for sending messages
  • S2 can consume only D1 and D2 for sending messages
  • S3 can consume only D1 and D3 for sending messages

 

:: My Take On It ::

The problem has been modeled into the following matrix and LP problem as shown in figure below:

The Problem Matrix In LP Terms

The Problem Matrix In LP Terms

I have adopted the “Simplex Method” for solving it as shown in figure below:
The Simplex Solution

The Simplex Solution

:: And now we have the distribution with maximum possible messages (180) as shown in figure below::
The Distribution For Maximum Messages

The Distribution For Maximum Messages

In case, you are still wondering why I live unhappily, you need to take a look at the “size” of the window again that my colleagues have opened.
Yeah it certainly is Infinity ()!

Probabilistic Bliss

This day that year :: 1989

Mathematics had eluded my senses (both common and uncommon) and I was literally treading this pathetic path (identifying problem patterns and memorizing its solutions). It was destination “disaster”. I was traumatized and the probability of a success was merely 0.5

This day that year :: 1990

An apple fell. I should say it literally broke or rather rewired the entire logic circuits of my psyche. I was so glad it fell unlike Mr. Newton who thought why it fell though I felt it fell late (better late than never, right?) I began to reason, analyze and attack the problems. I should confess that I became passionate, obsessed and finally possessed by Math.

This day this year :: 2009

Almost 2 decades. Mathematics rules my senses today. Till day, I don’t really know how this Boolean State Transition (0-1) occurred that too in such a short span. I attribute this success primarily to Mohan sir (my tutor) and to an unseen, unknown force (let me call it God) who, for a purpose, made this happen, which I am still in pursuit of.

Last weekend, I was flipping through the pages of a book on Discrete Mathematics that I bought (thanks to one of my mentors Pai for recommending this book) recently. And I stumbled upon this chapter on probability. It was a feeling that I cannot express through mere words. It was mere bliss as I laid down the Lego Blocks of knowledge one by one and I am sure that I did come up with the most beautiful structure that Richard Johnsonbaugh would have envisioned his reader to create.

Now with this confidence (or rather an element of defiance/arrogance, if I am to confess), I decided to try my fortune on the “Monty Hall” problem. It wasn’t that late before I joined the huge majority that failed trying. My obvious answer was obviously wrong. Hey! At least I tried. I tried to reason where I went wrong and read the solution that was illustrated in detail. I could very easily understand the rationale behind the solution (which is arguably been contested by many as confusing). Thanks to my foundation on probabilistic analysis that was re-solidified by Johnsonbaugh. I would like to share my take on it with the hope that it sheds light to any confused soul.

Monty Hall Problem

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice? (courtesy: Wikipedia)

:: My Take on IT ::

The key to the solution is to ascertain your best odds of nailing the prize with the choice you had made, assuming your chosen door has the prize hidden behind it, based on the 2 options that you have.

Option 1 (We decide to stick with our initial choice)

Remember the “key”, I had outlined above. Based on this, we would opt for Option 1 because we believe we chose the door with the prize behind it. The probability of choosing “this” door out of the 3 choices given is quite obviously 1/3.

Option 2 (We decide to change our initial choice)

Remember the “key” again. Why does one need to change the initial choice? Because, he/she believes that the remaining closed door (leave apart the closed door that was initially chosen and the opened door without the prize) has the prize behind it.

With this assumption our initial choice (say first event in probability world) had left us with a winning probability (p1) of 2/3 (i.e. the door with the prize is one among the remaining 2 non-selected doors out of the 3 choices). Now, here comes the crucial step in this experiment. The host (unlike in Option 1 where his/her action doesn’t affect the result) is actually telling us something very important i.e. the remaining closed door (leave apart the closed door that was initially chosen and the opened door without the prize) holds the prize in this case. And we can confidently pick this door (say second event in probability world) with a winning probability (p2) of 1 (certainty). So now, as the experiment is fair and the events are independent, the probability of the entire experiment would be (p1 * p2) i.e. 2/3.

Conclusion

To conclude, let’s analyze our findings on options 1 and 2.

  • Assertion 1: The chance of winning with Option 1 is 1/3.
  • Assertion 2: The chance of loosing with Option 1 is 2/3 (1-1/3).
  • Assertion 3: The chance of winning with Option 2 is 2/3.
  • Assertion 4: The chance of loosing with Option 2 is 1/3 (1-2/3).

Now, do I need to tell you what to do? Yeah! You guessed it right. The Assertions says it all!

:: It is best to switch your choice (Option 2) to increase your odds of winning the prize ::

Well that wasn’t that difficult, right? I guess not!

And, if you still find it confusing, please try visiting this site which helped me understand this solution to the problem.