Why does Bellman-Ford need -log of each exchange rate to spot arbitrage?
answer
- rates compound, but route weights add
- which function turns products into sums
- profit means the loop product exceeds one
- you need minimisation, not maximisation
- sum below zero around a loop
basics
~20 sRates compound by multiplying while route costs add, and profit means a product above one. Taking the logarithm turns the product into a sum, and negating turns "above one" into "below zero" — exactly a negative cycle.
solid answer
~50 sModel each currency as a vertex and each quote as a directed edge. Trading around a loop multiplies the rates, and the loop is profitable when that product exceeds `1`; shortest-path algorithms, though, **add** weights and **minimise**. The logarithm bridges the two, since `log(a*b) = log(a) + log(b)` and it is monotone, so it preserves which loop is best. Weight each edge `-log(rate)`: the product exceeding `1` becomes a sum of logs above zero, becomes a sum of negated logs **below** zero. A profitable trade loop is now literally a negative-weight cycle, and Bellman-Ford's extra pass is the detector — with predecessor links giving you the trade sequence. Rates above `1` produce negative weights, so the greedy alternative is ruled out by assumption, not by speed. Initialise every distance to `0` so loops that avoid your base currency are still found.
go deeper
Remember the one identity that powers this: the logarithm of a product is the sum of the logarithms. That is what lets an additive route algorithm reason about compounding returns.
Explain both halves of the transform — the log for products to sums, the negation for maximise to minimise — and state the resulting equivalence: profitable loop if and only if negative-weight cycle.
Show you would search the whole market by zero-initialising all distances, recover the trade sequence from predecessor links, and fold spreads and fees into the rate before taking the logarithm.
Own the modelling call itself: name what the graph does and does not capture — staleness, quote depth, execution risk — and treat a detected loop as a signal to verify rather than an instruction to act on.
## Two arithmetics that do not match A currency market is naturally a directed graph: one vertex per currency, one edge per quote, and the edge `u -> v` labelled with how many units of `v` one unit of `u` buys. Chain three trades and the amount you hold is the **product** of the three rates. You have made money when a loop back to where you started leaves you with more than you began with — when the product of the rates around the loop is greater than `1`. Shortest-path machinery does not multiply and does not maximise. It **sums** edge weights along a route and looks for the **smallest** total. Handed the raw rates, relaxation would happily compute the loop whose rates *add up* smallest, which corresponds to nothing anyone trades on. The mismatch is the whole difficulty, and the fix is a change of coordinates rather than a change of algorithm. ## The transform, in two moves **Move one: logarithms turn products into sums.** For positive numbers, `log(r1 * r2 * ... * rk) = log(r1) + log(r2) + ... + log(rk)`. Weighting each edge with `log(rate)` makes the total weight of a loop equal the logarithm of the compounded return. Because the logarithm is strictly increasing, the ordering of outcomes survives: a better product is still a bigger sum. **Move two: negate to flip the objective.** Relaxation-based algorithms hunt for totals that are too *small*. Weight each edge `-log(rate)` and the chain reads: | trading fact | with weight `-log(rate)` | | --- | --- | | loop product > 1 (profit) | loop weight < 0 | | loop product = 1 (break even) | loop weight = 0 | | loop product < 1 (loss) | loop weight > 0 | So *"is there a sequence of trades that returns more than it consumed?"* becomes, with no remaining slack, *"does this weighted digraph contain a negative-weight cycle?"* — which is the exact question Bellman-Ford's one extra pass answers. ## Why this algorithm and not a greedy one Any quote with a rate above `1` gives a weight `-log(rate)` that is negative, and such quotes are ordinary — they merely say one unit of the first currency buys more than one unit of the second. The graph is therefore soaked in negative weights by construction. A greedy shortest-path algorithm that finalises the nearest unfinished vertex is unsound on negative weights, so it is disqualified by its own precondition, not because it would be too slow. Bellman-Ford does not merely tolerate negative weights; the object you are hunting *is* a negative cycle, and it is the algorithm whose termination condition names that object. A second reason to like it here: the graph is small. A market has hundreds of currencies and at most a few tens of thousands of quotes, so `O(V*E)` is trivial work, and the analysis is dominated by getting the data right, not the loop count. ## Getting the whole market, and getting the trades Run from a single source and you only detect loops reachable from that currency. Initialise `dist[v] = 0` for every vertex — the same as attaching a virtual source with zero-weight edges into all of them — and the detection pass finds a profitable loop wherever it sits, including one that never touches your base currency. To report the actual trades, keep `pred` links, take the vertex that relaxed on the extra pass, follow `pred` `V` times to land inside the loop, then walk it round until you return. ## Where the model leaks The reduction is exact; the data is not. - **Two-sided prices.** Real quotes come with a bid and an ask, and you cross the spread on every hop. Fold the effective rate you would actually receive — spread and commission included — into the number *before* taking the logarithm. Multiplicative costs stay multiplicative, so log-additivity survives; many apparent loops evaporate once each hop pays. - **Staleness.** By the time a loop is computed the quotes have moved. The output is a hypothesis to re-verify against live prices, never an instruction to send orders. - **Depth and limits.** A rate holds for a size. A loop that is profitable on a single unit may be worthless at the volume that would justify the trade. The interview-relevant lesson generalises past currencies: whenever a quantity **compounds along a route** and you must find a loop that gains, take logarithms to enter the additive world, negate to enter the minimising world, and the negative-cycle detector you already own answers the question.
- How do you find a profitable loop that never touches your starting currency?Initialise every vertex's distance to zero rather than only the source's. That is equivalent to attaching a virtual source with zero-weight edges into every currency, so every loop becomes reachable and the detection pass can see it. The distances stop meaning "cost from a source", which is fine — you only care about the existence and identity of the negative cycle.
- Where do bid/ask spreads and per-trade commissions go in this model?Into the rate, before the logarithm. Compute the rate you would genuinely receive on that hop after crossing the spread and paying any proportional fee, then take -log of that. Multiplicative costs stay multiplicative, so the sum-of-logs identity is untouched. Charging every hop honestly kills most loops that look profitable on mid-market quotes.
Logarithms are the old slide-rule trick: they turn multiplying into adding lengths. Once compounding becomes addition, a money-making loop is just a route that sums to less than nothing.
saying these in an interview costs you the question
- Uses the raw rate as the edge weight and adds
- Takes the log without negating, then hunts a positive cycle
- Calls any single negative -log weight an arbitrage opportunity
- Ignores spreads and fees when computing the effective rate
- Claims a greedy shortest-path algorithm would work here