Posts

First-Envelope Problem, Probabilistic Reasoning

Image
Suppose you are given two envelopes both containing money, and you know that no matter what the amounts are, one envelope contains double the amount of the other. You want to choose the envelope that contains the largest amount. Without loss of generality, assume that the money are of integer type. Denote the two envelopes as X = n   Y = 2n, n \( \in \mathbb{N} \) You pick one envelope of the two at random, and before you open it, you are given the opportunity to change your choice and pick the other envelope instead. What would you do, and why? It is natural to think that this question is meaningless, since both envelopes are pressumably assigned probability 0.5 of containing the largest amout, and thus by choosing to change your choice you are basically changing your probability of success from 0.5 to 0.5, which is trivial. It's like betting on "Heads" on a coin flip game, and then choosing to bet on "Tails" instead. You can certainly d...
Post a Comment
Read more

How, why, and when is recursion the better choice for your algorithm?

Image
Recursion is an algorithm design technique in which the underlying algorithm calls itself with updated input until certain conditions are met. These terminating conditions that end the recursive call of the algorithm are also called "the base" of the recursion. How can a process (aka algorithm) can actually call itself? Simple. All there is to know is that there exist a dependence relationship between the states of the algorithm. For example, consider the famous Fibonacci sequence of natural numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, etc. One can notice that each term of that sequence, except the first two, can be writen as a sum of the previous two terms. In other words there exist the following dependence relationship between the current state and the previous two states: 1 1 2 = 1  + 1 3 = 2  + 1 5 = 3 + 2 8 = 5 + 3 13 = 8  + 5 21 = 13 + 8 The formal way to write this relationship between the terms is: f(n) = f(...
Post a Comment
Read more