exact-kantorovich: Exact Kantorovich distance between finite probability measures.

[ bsd3, library, math, optimization ] [ Propose Tags ]

This small package allows to compute the exact Kantorovich distance between two finite probability measures. This assumes that the probability masses are rational numbers and that the distance function takes rational values only.


[Skip to Readme]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0
Change log CHANGELOG.md
Dependencies base (>=4.7 && <5), containers (>=0.6.5.1 && <0.7), extra (>=1.7 && <1.8), matrix (>=0.3.6.0 && <0.4), monad-logger (>=0.3.40 && <0.4), simplex-method (>=0.2.0.0 && <0.3) [details]
License BSD-3-Clause
Copyright 2024 Stéphane Laurent
Author Stéphane Laurent
Maintainer laurent_step@outlook.fr
Category Math, Optimization
Home page https://github.com/stla/exact-kantorovich#readme
Source repo head: git clone https://github.com/stla/exact-kantorovich
Uploaded by stla at 2024-05-08T06:40:23Z
Distributions NixOS:0.1.0.0
Downloads 21 total (4 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2024-05-08 [all 1 reports]

Readme for exact-kantorovich-0.1.0.0

[back to package description]

exact-kantorovich

Stack-lts Stack-nightly

Exact Kantorovich distance between finite probability measures.

This small package allows to compute the exact Kantorovich distance between two finite probability measures. This assumes that the probability masses are rational numbers and that the distance function takes rational values only.


Let's say you have the two probability measures with masses \((1/7, 2/7, 4/7)\) and \((1/4, 1/4, 1/2)\), both distributed on the set \(\{1, 2, 3\}\), and you want to get the Kantorovich distance between them when this set is endowed with the distance function \(d(i, j) = |i - j|\). To get it with this package, you will use the kantorovich function. It has four arguments. The first two ones are the two random variables corresponding these probability measures, and a random variable is defined as a map from its states set to the rational numbers; this map assigns to each element its probability mass:

import Data.Map.Strict ( fromList )
import Data.Ratio ( (%) )
mu, nu :: RandomVariable Int
mu = fromList $ zip [1, 2, 3] [1%7, 2%7, 4%7]
nu = fromList $ zip [1, 2, 3] [1%4, 1%4, 1%2]

The third one is the distance function; it must return a positive rational number:

dist :: (Int, Int) -> Rational
dist (i, j) = toRational $ abs (i - j)

And the fourth one is a Boolean value that you set to True if you want to print to the stdout stream some details of the simplex algorithm performed by the kantorovich function:

import Math.Optimization.Kantorovich
result <- kantorovich mu nu dist False

The output of the kantorovich function has type IO (Maybe (KantorovichResult a b)) where here a = b = Int and the type KantorovichResult a b is the pair of types (Rational, RandomVariable (a, b)). The first element of an object of a KantorovichResult object represents the value of the Kantorovich distance and the second element represents a solution of the underlying linear programming problem, that is to say a joining of the two probability measures that achieves the Kantorovich distance.

Here is the value of the Kantorovich distance for our example:

import Data.Maybe ( fromJust )
fst $ fromJust result
-- 5 % 28

You can display the solution in the style of a matrix with the help of the prettyKantorovichSolution function:

putStrLn $ prettyKantorovichSolution result

This prints:

┌                      ┐
│  1 % 7  0 % 1  0 % 1 │
│ 3 % 28 5 % 28  0 % 1 │
│  0 % 1 1 % 14  1 % 2 │
└                      ┘

That's all. There is no other function exported by this package.