颈脖Blog

【算法】外汇市场的套利与Bellman-Ford算法

前言

最近美元兑换人民币汇率跌破6.9(2022-09-04),蹭蹭热度来聊聊外汇市场的套利(Forex Arbitrage)算法,以及具体实现的限制。

问题概述

在外汇市场,如果货币A通过一系列货币兑换回到A,A数额竟然变大了,我们就认为该外汇市场存在套利。因为通过这一系列货币兑换,将获得更多A货币,无中生有。而且如果这些货币汇率保持不变,我们一直循环这样的兑换,那么理论上我们可以无限获取货币A。

如上图例子如果有100块人民币,先兑换成美元,再将美元兑换成欧元,最后将欧元再兑换回人民币,100/7.91*7.92 = 100.12,可以发现一顿操作后多了0.12人民币。

那如何判断一个外汇兑换市场有没有套利机会?如果有,具体套利策略是什么呢?要解决这个问题,我们可以先看看另一个相关的问题,如果想将货币A兑换成货币B有多种方法,那么最多能兑换多少货币B?

问题分析

我们可以将这个问题转换成一个图问题。每种货币为一个节点vertex,如果货币A能直接兑换货币B,则两种货币对应的节点间有一条有向边edge,同时该边有一定的权重weight表示从货币A到B的汇率(A->B的汇率不一定与B->A汇率相等)。这样我们就可以把整个外汇市场转换成一个有向边的图。

想知道货币A通过某个兑换路径能兑换多少货币B,只需要将A货币节点到B货币节点该兑换方法对应的路径上,边的权重相乘。

但如果货币A到货币B有多条路径,如何找到能获得最多货币B的兑换路径呢?

这个问题听起来很像经典的从A到B的最短路径,但是有两个不同点:

  1. 最短路径问题目标函数是将权重相加而不是相乘
  2. 最短路径问题是找目标函数的最小值而不是最大值

其实我们只需要针对这两个不同点做一定的转换就可以变成最短路径问题,最短路径问题我们就可以用最经典的Dijkstra算法来求解(计算机最基础的算法, 不展开解释):

  1. 从相乘变成相加,只需要取对数log就能将乘法变成加法 因为log(x*y) = log(x) + log(y)
  2. 最大值变成最小值,只需要将目标函数取负数

那么我们相当于把原始图的每条边权重改成new-weight(a,b) = -log(weight(a,b)),问题就转换成从A到B的最短路程。

但由于log(x)在x<1的时候为负值,那么我们转换的新图的每条边权重可能会有负值。很可惜Dijkstra算法只能解决所有边权重为正数的最短路径问题。如果图里面边权重为负数,一旦存在一个回路,路径和为负数,那么就A到B就不会有最小路径,因为可以一直走那个回路,让最小路径理论无穷小。

这是不是听起来和我们的套利问题很像?没错,套利问题其实就是在这个转换后的图里面,判断有没有存在路径和为负数的回路,并把这样的回路找出来。

Bellman-Ford算法

这个问题再简化一下其实就是一个存在负数权重边的图里面,找到路径和为负的回路。而这个问题也有一个专门的Bellman-Ford算法来解决。

Bellman-Ford算法说到底就是一个动态规划DP算法,来求从图里面的一点A,到其它所有点的最短路径。而算法的核心思想是:如果最短路径存在,那么这条路径最多有V个节点,V-1条边(V为图总节点个数),DP算法的状态即为distance(A,v,e) 意思为从节点A到节点v的最多包含e条边的最短路径。

def bellmanFord(graph, start):
	# Set initial dist and prev.
	for vertex in graph:
		vertex.dist = ∞
		vertex.prev = null
		start.dist = 0
		
	# Iterate |V| − 1 times.
	for iter in range(0, |V| − 1):
		# Look at each vertex.
		for v in vertex:
			# Check each neighbor of v.
			# neighbor means there is an edge from u to it
			for neigh of v:
				# Only update if the new value is better!
				if neigh.dist > v.dist + length(v, neigh):
					neigh.dist = v.dist + length(v, neigh)
					neigh.prev = v

	# Iterate One more time
	# If the neigh.dis changed for any vertex n
	# Then there is a negative cycle
	We found the arbitrage!!!
	Found the node v = neigh.dist changed in the last round
	Backtrack with v.prev to find the cycle

算法复杂度 : O(|V|^2*|E|)

最坏情况为全连接图那么E=V-1,所以算法复杂度是O(|V|*4)

具体实现限制

是不是掌握这个算法,一旦外汇市场出现了可套现的情况就一定能获利呢?那当然不是了。

佣金

外汇交易需要通过券商,而券商会收取佣金。

有的券商会直接将佣金反应在汇率上面,这样比较简单,因为汇率已经包括了所有的交易费用。

但有的券商会根据交易笔数和交易金额来收取佣金,这样的话就需要一些额外方法把这些交易费用反应在汇率上面,再用Bellman-Ford算法。

延迟Latency

汇率变化十分的快,即使汇率市场存在套利的机会,但是这个机会可能稍纵即逝,不同的延迟Latency会导致普通散户无法及时抓住这些机会。

获取数据的延迟

我们需要获取不同货币之间的汇率作为算法的输入。通常汇率数据由券商提供,需要用券商提供的API去获得,而不同API会有不同的延迟,延迟可能是由券商服务器或者网络导致,可能你得到数据的同时这些数据就已经过期了。

算法的复杂度

这个算法最差复杂度是O(|V|*4),所以算法的速度不快,可能算出结果的同时,该结果已经不可用。

交易的延迟

通常券商的交易匹配系统是通过买和卖两个队列做匹配,而这个过程也需要时间,很有可能汇率一变,导致你指定的买卖价格匹配一直不成功。而如果直接用市场价很有可能你的交易价格与你最初算法的输入价格不一样,导致最后结果与期望结果不一致。

结语

购买外汇,按需购买就好。

guest

0 Comments
Inline Feedbacks
View all comments