# An algorithm for arbitrage in currency exchange

I found a really interesting problem and I wanted to hear people's opinion.

It has to do with currency exchange rate.

If we are give some coins $c_1,c_2,\dots,c_n$ and an array $R$ that keeps the selling price, where $R[i,j]$ is the selling price of one unit of currency $c_i$ to currency $c_j$.

a) We are trying to design an algorithm that will find a sequence of coins $(c_{i_1}, c_{i_2}, \dots, c_{i_k})$ ,$R[i_1, i_2] \cdot R[i_2, i_3] \cdots R[i_{k-1}, i_k] \cdot R[i_k, i_1] >1$.

b) Show how the algorithm you designed can find and print fast such a sequence $(c_{i_1}, c_{i_2}, \dots, c_{i_k})$ (if there is one).

If someone dives into that problem it would be also interesting to know the execution time of the algorithm.

Sorry if I did mistakes with the terminology of this scientific field.

• Sorry, this problem has little -- if at all -- to do with economics (and I retagged the post to reflect this). This problem is about finding positive (or negative) weight cycles in a directed graph, which can be solved using Bellman-Ford (e.g.). Dec 27, 2011 at 11:09
• @Srivatsan Is this problem related with graph theory? Dec 27, 2011 at 11:09
• This question is a trivial modification of Exercise 24-3 of Introduction to Algorithms by CLRS, 2nd ed., Chap. 24 Single Source Shortest Paths. Dec 27, 2011 at 11:17
• @Srivatsan Thank you. I will try to borrow this book. It must be very interesting to read. Dec 27, 2011 at 11:21
• @tasmer_k May I assume that this is not homework? If so, then I can give you the "reduction" to a standard graph theoretic algorithm, namely Bellman-Ford. Dec 27, 2011 at 11:24

Conceptually, it is easier to think of the “log-exchange rates” defined by $L[i, j] = - \log R [i, j]$. (The negative sign is just for the sake of convention.) Now imagine a directed graph with the currencies as the vertices where the weight of the edge $(i, j)$ is $L[i, j]$. In terms of the new quantity we just introduced, we are seeking a cycle $(i_1, i_2, \ldots, i_k)$ such that $$\sum_{t = 1}^{k-1} L[i_t, i_{t+1}] + L[i_k, i_1] \lt 0.$$ This equation is obtained by just taking the log of the given equation, and reversing the sign. That is, we are seeking a “negative weight cycle” in the graph, where the weight of a cycle is just the sum of the edges in the cycle.
Negative cycle detection is a standard problem in algorithmic graph theory, conventionally studied along with the shortest path problem. [The shortest path problem is the following: given a directed graph with a source and a sink terminal, find the path of least cost from the source to the sink.] A number of algorithms have been designed to solve these problems. The simplest one (in general graphs) is the Bellman-Ford algorithm which runs in $O(|V||E|)$.