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.

Bounds

T exactly = 0 will cause divide by 0 error.
In fact, in software, T close to 0 will cause floating point maximum overflow error.
Have to figure out minimum safe T for your software system.
We will be keeping T > 0 and looking at T -> 0

If T > 0, and all f(i) are finite (positive or negative),
then f(i)/T is finite (positive or negative).
all e(f(i)/T) > 0
all probabilities are in range:
0 < p(i) < 1
i.e. This is a probability distribution.

As T -> 0 a probability can -> 0
but as long as T > 0 all probabilities are > 0

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, probabilities are:
e / (e + e2)
and:
e2 / (e + e2)
i.e. 0.27 and 0.73

If T=1/20, probabilities are:
e20 / (e20 + e40)
and:
e40 / (e20 + e40)
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
where   d > c  
Let   T = 1/N  
Then:

p(1) = ecN / ( ecN + edN )

= 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)

Clue: p(1) is even smaller than above p(1), which goes to zero.

Q. Show it for joint winners