Boltzmann "soft max" distribution

Let us have n items. The "fitness" score of item i is f(i). Let the probability of picking item i, p(i), be defined as:

Then by varying the parameter T, we can vary the selection from picking a random item (T infinite) to: having higher probabilities for items with higher fitness (T small finite) to: strictly picking the item with the best fitness (T goes to 0).

T is called "temperature" - analogy to cooling.

Exercise

Prove:

1. Each p(i) is a number between 0 and 1, no matter what the fitness is (positive or negative). This scheme does not require that fitness has to be positive.

2. The sum of all the p(i)'s is 1.
   i.e. This is a prob. distribution.

3. No matter what T is:
   1. If 2 items have same fitness, they have same probability of being picked.

   2. If all fitnesses are the same, we pick random item.
      Q. "Pick random item" means each p(i) = what?

4. No matter what the fitnesses are:
   1. As T → ∞ we tend to pick random item.
      Q. For any item what is p(i)?

   2. As   T -> 0   we tend to pick only the no.1 best item. That is, its probability is 1, all others probability 0.

      If there are m joint best items, we pick them with probability 1/m, all others with probability 0.

As   T -> 0   (example)

To see what happens as T -> 0 consider 2 items:

i     1    2
f(i)  1    2

If T=1/20, probabilities are:
e²⁰ / (e²⁰ + e⁴⁰)
and:
e⁴⁰ / (e²⁰ + e⁴⁰)
i.e. pretty much 0 and 1.

As   T -> 0   (in general)

In general:
Let us have any two items where one has a higher fitness value:

i     1    2
f(i)  c    d

p(1) = e^cN / ( e^cN + e^dN )

= 1 / ( 1 + e^(d-c)N )

→ 0
as N → ∞
since   (d-c) > 0

So   p(1) -> 0   as   T -> 0  

Q. Show   p(2) -> 1   as   T -> 0  

Q. Show it for any number of items (not just 2)

Q. Show it for joint winners