Thursday, December 8, 2011

The Next Best Mate

The so-called "Sultan's Dowry Problem" (a.k.a "Beauty Pageant Problem", "Secretary Problem" etc.) is sometimes used as a model for searching a mate. It is a nice model for decision-making under a certain type of uncertainty.

According to the wikipedia entry:
The basic form of the problem is the following. Imagine an administrator willing to hire the best secretary out of N rankable applicants for a position. The applicants are interviewed one-by-one in random order. A decision about each particular applicant is to be taken immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants.
There is an elegant solution to the problem, when the objective of the game is to maximize the probability that the candidate chosen has the highest quality. We assume quality can be reduced to a simple number. The so called "1/e" or "37%" solution to this problem involves letting the first 37% of the candidates pass, remembering the quality Q of the best candidate from this set. Thereafter, the first candidate whose quality exceeds Q is chosen.

Todd argues that the way humans search for their mates is very different from this optimal solution. He points out that the 37% rule finds the best solution more often than any other algorithm, 37% of the time. However, what happens during the 63% of the times is not very flattering:
For instance, if applied to a set of 100 dowries ranging from 1 to 100, the 37% rule returns an average value of about 82, that is, the mean of all dowries chosen by this rule. Only 67% of the individuals selected by this rule lie in the top 10% of the population, while 8% fall in the bottom 25%. And it takes the 37% rule an average of 74 tests of potential mates that is, double the 37 that must be checked before selection can begin before a mate is chosen.
This probably explains why normal people do not apply this strategy. It turns out that normal people tend to use a much smaller "screening" period. It turns out that the length of the screening period is dependent on your appetite for risk.

If you are fixated on maximizing the probablity of ending up with the best candidate, then the 37% rule works fine. But if you are a risk minimizer - if you would rather protect your downside - while accepting anybody in the top 10% for example, the optimal screening period is much shorter - closer to 10%.

I first heard about this problem more than a decade ago, and have been fascinated by it ever since. I used this problem to create a programming assignment in the class I am currently teaching.

Friday, December 2, 2011

Text in Inkscape

Inkscape is a fantastic program for creating vector graphics. It is free, platform independent, refreshingly clean and efficient once your master some keystroke shortcuts, and amazingly powerful in terms of the things it can do for you.

It does have a few pesky features though, particularly with "text". For example there is no intrinsic way of creating subscripts or superscripts, and sometimes Greek symbols just do not render properly.

This post explains my workarounds.

1. Subscripts and Superscripts: While there is no natural way of getting these, you can always select some text, and then press Alt + arrow-key (up, down, left, or right arrows) to move the selection in that particular direction. Here is a screenshot of how that works.

2. Greek Symbols: You can try to select the Symbol font from the font dialog box, but very often, it won't get you anywhere. A handy but inconvenient workaround is to use Unicode. If you know the Unicode Standard (pdf), then you can directly enter the code of the particular character. For example, the symbol for "beta" is 03B2.
To enter this in Inkscape, first open a text dialog box as usual. Then press Ctrl + U. The status bar at the bottom of the screen prompts you to enter the code. You type 03B2 (or 03b2), and you will see it echoes the symbol "beta". You press enter, and the symbol is inserted near the text cursor.

3. LaTeX Support: Inkscape supports LaTeX expressions by default. I did not know this until recently, but you can go to Extensions > Render > LaTeX formula... (in some cases it may be under Effects > instead of Extensions >).

It opens up a dialog box, in which you can enter your formula. Inkscape calls LaTeX and con­verts the DVI out­put to SVG, and em­beds it in the document. Since it is a scalable equation (or any other LaTeX object), you can now interact with it natively in Inkscape.