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. See Simulated Annealing.

---

Bounds

T exactly = 0 will cause divide by 0 error.
Also, in software:

• Too low T, close to 0, may cause floating point overflow error.
• Too high fitness f may also cause floating point overflow error, when we do e to the power of f/T.

• IEEE floating point format. (Different implementations have different max and min values.)
• Floating point number max and min values in Java

Have to figure out safe T ranges and f ranges 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 + e²)
and:
e² / (e + e²)
i.e. 0.27 and 0.73

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

where   d > c  
Let   T = 1/N  
Then:

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)

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

---

Q. Show it for joint winners

ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.      New 250 G VPS server.

Note: Links on this site to user-generated content like Wikipedia are highlighted in red as possibly unreliable. My view is that such links are highly useful but flawed.