Exchange rates are USD to EUR 0.90, EUR to GBP 0.85 and GBP to USD 1.35. Compute the product around the cycle, say whether an arbitrage exists, and state the graph transformation that turns this into a shortest path problem.

Exchange rates are USD to EUR 0.90, EUR to GBP 0.85 and GBP to USD 1.35. Compute the product around the cycle, say whether an arbitrage exists, and state the graph transformation that turns this into a shortest path problem.

Approach: Multiply the rates around the cycle, then take logarithms so that products become sums and a profitable cycle becomes a cycle of negative total weight.

1.03275. The cycle product is 0.90 * 0.85 = 0.765 and then 0.765 * 1.35, giving 1.03275, so one dollar returns 1.03275 dollars and an arbitrage of 3.275% per round trip exists before costs. Set the weight of the edge from currency i to currency j as w(i,j) = -log(rate(i,j)). A cycle is profitable exactly when its product of rates exceeds 1, and the logarithm transform turns that product into a sum, so a profitable cycle becomes a cycle of negative total weight. Bellman ford over n currencies and m quoted pairs detects one in O(nm) by running n - 1 relaxation rounds and then testing whether any edge still relaxes on round n, which can happen only when a negative cycle is reachable. The cycle itself is recovered by walking predecessor pointers back from the vertex that relaxed until a vertex repeats. Using the executable bid or offer rather than the mid folds in transaction costs, which usually removes the apparent edge.

Follow-up: How do you find the most profitable cycle rather than any profitable one, and why is that problem harder?

Key concepts: negative cycle, logarithm transform, bellman ford, cycle product.