"What is mathematics?" The Professor asked us in the first class of Set Theory. None of us could find a satisfying answer. Finally he replied : "Mathematics is the study of patterns".
What particularly nice about this definition is that it suggests that one could find mathematics in many areas, not only in science and engineering but also in our every day life - if only we will listen and pay attention for the right clues; I would like to post here an example where an every daily boring trip with a car can be mathematically fascinating.
Suppose you are driving your car alone in the night listening to your favorite songs in your mp3 player. You are listening now to song number 32 ('Ramona' by Beck Hansen from the Scot Pilgrim's soundtrack) the song is over and you are in the mood for song number 103 ('39 by Queen).
A conventional mp3-player has three buttons for controlling the songs flow-
'prev' button, 'next' button and a 'rdm' (random) button. (see pic)
Assuming that you have a circular list of 300 songs in the mp3-player, how should you press the button to reach the song?
The obvious way is to press 'next' button 71 times but remember that you are a safe driver and want to avoid accidents. Pressing the same button so many times might be dangerous (and tedious). Is there a strategy that allows you to press buttons as little as possible?
Close inspection of two strategies
In order to understand what do I mean by 'as little as possible', let us analyze two strategies:
Suppose that we have a circular list of \(n\) songs. Assume that we are now in song \(i\) and that we want to reach song \(j\).
Strategy 1 - Pressing 'prev/next' to reach j.
Since the list is circular there are two paths between any two songs - and the maximal distance should be \(\cfrac{n}{2}\). Now, assuming that \(i\) and \(j\) are uniformly distributed (i.e are arbitrary) their distance should be uniformly distributed between \(1,...,\cfrac{n}{2}\) (not counting the case where \(i=j\)). This would give us an expected number of \(\cfrac{n}{4}\) pressings.
Strategy 2 - Pressing 'rdm' until the destination.
This strategy is also easy to analyse - In each press, the odds of reaching the desired song are \(p=\cfrac{1}{n}\). The number of button-pressing is a geometric random variable with parameter \(p\), it is known that its expected value is \(\cfrac{1}{p}=n\).
Note that the number of button-pressing in both strategies yield a linear result that is, they belong to the class of \(O(n)\).
Now we can state the problem: Does there exist a strategy that yields an expected number of button pressing that is asymptotic better than \(O(n)\)?
.
.
.
The answer to this problem is yes!
Optimal Strategy -
A. Press 'rdm' until \(Distance(i,j)<\sqrt{n}\).
B. Press 'prev/next' to reach j.
Let us calculate the expected time for this strategy: Suppose \(T\) is the number of button-pressing for reaching song \(j\). Note that \(T\) is a random variable and that we can decompse it to two random variables \(T=R+U\), where:
\(R\) is the number of button-pressing for reaching the set \(A=\{k\in{1...n}|Distance(k,j)\leq\sqrt{n}\}\) (note: \(|A|=2\sqrt{n}\)).
\(D\) is the number of 'prev/next' button-pressing.
The probability for reaching the set \(A\) each time we press the 'rdm' button is \(p=\cfrac{|A|}{n}=\cfrac{2}{\sqrt{n}}\) - hence \(R\) should be a geometric random variable and \(\mathbb{E}R=\cfrac{1}{p}=\cfrac{\sqrt{n}}{2}\).
After reaching the set \(A\) we can be in any one of the songs \(j-\sqrt{n},..,j+\sqrt{n}\) and the probability to be in any one of these songs is uniform, so \(D\) should be uniformly distributed in the set \(\{1,...,\sqrt{n}\}\}\) and,as the case of strategy 1, \(\mathbb{E}D=\cfrac{\sqrt{n}}{2}\).
altogether \(\mathbb{E}T=\mathbb{E}R+\mathbb{E}D=\sqrt{n}\), which is \(O(\sqrt{n})\).
Proving that this strategy is optimal is quite hard and technical. I will discuss it in my next post.
No comments:
Post a Comment