bellman_ford forex arbitrage.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Forex Arbitrage\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "The classic arbitrage in forex trading is triangular arbitrage. For instance, if we wanna short GBP long DKK, we can short GBP long PLN then short PLN long DKK, which may give us more DKK in some rare cases. We can use dijkstra/bellman-ford algorithm to solve the problem. However, high frequency trading is already a major player in forex market. Triangular arbitrage opportunity is like a needle in the haystack. Even if it exists, it would only last for a millisecond or even less. It would have been exploited long before any human knows. Unfortunately, I have never found any triangular arbitrage opportunity throughout my time of trading.\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "os.chdir('K:/ecole/github')\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "#graph adt\n",
    "#check the below link for more details\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/graph.py\n",
    "import graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#forex data can be downloaded in the data subfolder\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/data/forex.csv\n",
    "df=pd.read_csv('forex.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>currency</th>\n",
       "      <th>ask</th>\n",
       "      <th>bid</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>AUDJPY</td>\n",
       "      <td>83.8930</td>\n",
       "      <td>83.8610</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>AUDUSD</td>\n",
       "      <td>0.7599</td>\n",
       "      <td>0.7596</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>CHFJPY</td>\n",
       "      <td>112.0830</td>\n",
       "      <td>112.0370</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>EURCHF</td>\n",
       "      <td>1.1604</td>\n",
       "      <td>1.1601</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>EURGBP</td>\n",
       "      <td>0.8809</td>\n",
       "      <td>0.8806</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>EURJPY</td>\n",
       "      <td>130.0160</td>\n",
       "      <td>129.9680</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>EURUSD</td>\n",
       "      <td>1.1778</td>\n",
       "      <td>1.1773</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>GBPCHF</td>\n",
       "      <td>1.3177</td>\n",
       "      <td>1.3172</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>GBPJPY</td>\n",
       "      <td>147.6490</td>\n",
       "      <td>147.5770</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>GBPUSD</td>\n",
       "      <td>1.3375</td>\n",
       "      <td>1.3367</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>USDCHF</td>\n",
       "      <td>0.9856</td>\n",
       "      <td>0.9852</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>USDJPY</td>\n",
       "      <td>110.4430</td>\n",
       "      <td>110.3760</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   currency       ask       bid\n",
       "0    AUDJPY   83.8930   83.8610\n",
       "1    AUDUSD    0.7599    0.7596\n",
       "2    CHFJPY  112.0830  112.0370\n",
       "3    EURCHF    1.1604    1.1601\n",
       "4    EURGBP    0.8809    0.8806\n",
       "5    EURJPY  130.0160  129.9680\n",
       "6    EURUSD    1.1778    1.1773\n",
       "7    GBPCHF    1.3177    1.3172\n",
       "8    GBPJPY  147.6490  147.5770\n",
       "9    GBPUSD    1.3375    1.3367\n",
       "10   USDCHF    0.9856    0.9852\n",
       "11   USDJPY  110.4430  110.3760"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#the tricky part of forex graph is its computation\n",
    "#for instance, assume we have EURGBP,GBPUSD\n",
    "#to get EURUSD, we need to multiply EURGBP by GBPUSD\n",
    "#however, dijkstra doesnt accept multiplication\n",
    "#hence, we apply a logarithm transformation\n",
    "#cuz log(a)+log(b)=log(a*b)\n",
    "#additionally, some forex rate such as EURGBP is smaller than 1\n",
    "#after logarithm transformation we get negative numbers(cuz e**0=1)\n",
    "#we should use negative logarithm transformation to solve it\n",
    "#the good news is everything kind of clicks through\n",
    "#since we wanna get an indirect forex rate larger than a direct one\n",
    "#after negative logarithm transformation\n",
    "#the objective changes to the smallest transformed rate\n",
    "#which is consistent with dijkstra!\n",
    "#to make our life easier, we ignore bid ask spread\n",
    "forex=graph.graph()\n",
    "\n",
    "#there is limitation for negative logarithm transformation\n",
    "#some forex rate such as EURJPY is larger than 100\n",
    "#after logarithm transformation we end up with positive numbers\n",
    "#in order to apply dijkstra, we avoid negative weights\n",
    "for i in df.index:\n",
    "    if np.log(df['bid'][i])<0:\n",
    "        forex.append(df['currency'][i][:3],\n",
    "                     df['currency'][i][3:],-np.log(df['bid'][i]))\n",
    "    if np.log(1/df['bid'][i])<0:\n",
    "        forex.append(df['currency'][i][3:],\n",
    "                     df['currency'][i][:3],-np.log(1/df['bid'][i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'JPY': {'AUD': 4.429160666307817,\n",
       "  'CHF': 4.718829173882046,\n",
       "  'EUR': 4.867288266308598,\n",
       "  'GBP': 4.994350073465887,\n",
       "  'USD': 4.703892718905732},\n",
       " 'AUD': {'USD': 0.27496330004400615},\n",
       " 'USD': {'EUR': 0.16322368110201413,\n",
       "  'GBP': 0.29020388999529034,\n",
       "  'CHF': 0.01491061273575424},\n",
       " 'CHF': {'EUR': 0.14850620829922395, 'GBP': 0.2755082715200721},\n",
       " 'EUR': {'GBP': 0.12715178566048355},\n",
       " 'GBP': {}}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#this graph adt has excluded negative cycles\n",
    "forex.reveal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/forex.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bellman-Ford Algorithm\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Bellman-Ford algorithm is somewhat similar to Dijkstra's algorithm. Yet, it doesn't require a queue to do Breadth-First-Search traversal. The algorithm iterates through each vertex in the structure multiple times. To be more precise, the number of the iterations equal to the order of the graph structure minus two. Thus, it does not need to keep track of which vertices have been visited. It has one extra round of iteration to detect if there is a negative cycle and raise error if there is one. If there is negative weight, the one last traversal cannot bring convergence. We would end up with a ridiculously small distance caused by several rounds of deduction. Without negative cycle, the algorithm works just like dijkstra to return the optimal steps. With 3 layers of loops, we can easily tell Bellman-Ford has higher time complexity than Dijkstra.\n",
    "\n",
    "Details of Dijkstra are in the following link\n",
    "\n",
    "https://github.com/je-suis-tm/graph-theory/blob/master/dijkstra%20shortest%20path.ipynb\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#bellman ford is basically quid pro quo\n",
    "#it trades higher time complexity for lower space complexity\n",
    "def bellman_ford(ADT,start,end):\n",
    "    \"\"\"Bellman-Ford Algorithm,\n",
    "    a modified Dijkstra's algorithm to detect negative cycle\"\"\"\n",
    "    \n",
    "    #distance is a dictionary\n",
    "    #it keeps track of distance from starting vertex to any vertex\n",
    "    #before we start any iteration\n",
    "    #we initialize all distances from start to any vertices to infinity\n",
    "    #we set the distance[start] to zero\n",
    "    distance={}\n",
    "    for i in ADT.vertex():\n",
    "        distance[i]=float('inf')            \n",
    "    distance[start]=0  \n",
    "    \n",
    "    #pred is a dict as well\n",
    "    #it keeps track of how we get to the current vertex\n",
    "    #each time we update distance, we update the predecessor vertex\n",
    "    #in the end, we can obtain the detailed path from start to end\n",
    "    pred={}\n",
    "    \n",
    "    #dynamic programming\n",
    "    for _ in range(1,ADT.order()-1):\n",
    "        for i in ADT.vertex():\n",
    "            for j in ADT.edge(i):\n",
    "                try:\n",
    "                    if distance[i]+ADT.weight(i,j)<distance[j]:\n",
    "                        distance[j]=distance[i]+ADT.weight(i,j)\n",
    "                        pred[j]=i\n",
    "                \n",
    "                except KeyError:\n",
    "                    pass\n",
    "    \n",
    "    #detect negative cycle\n",
    "    for k in ADT.vertex():\n",
    "        for l in ADT.edge(k):\n",
    "            try:\n",
    "                assert distance[k]+ADT.weight(k,l)>=distance[l],'negative cycle exists!'\n",
    "            except KeyError:\n",
    "                pass\n",
    "    \n",
    "    #create the shortest path by backtracking\n",
    "    #trace the predecessor vertex from end to start\n",
    "    previous=end\n",
    "    path=[]\n",
    "    while pred:\n",
    "        path.insert(0, previous)\n",
    "        if previous==start:\n",
    "            break\n",
    "        previous=pred[previous]\n",
    "     \n",
    "    return distance[end],path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#without negative cycle\n",
    "#dijkstra vs bellman ford\n",
    "answer=graph.dijkstra(forex,'USD','EUR')\n",
    "\n",
    "answer2=bellman_ford(forex,'USD','EUR')\n",
    "\n",
    "answer==answer2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8494011721736175"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#we revert the answer back to non-logarithm forex rate\n",
    "np.e**(-answer[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['USD', 'EUR']"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#the shortest route is direct route USDEUR\n",
    "answer[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6    0.849401\n",
       "Name: bid, dtype: float64"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#which is consistent with the inverse of EURUSD bid price\n",
    "1/df['bid'][df['currency']=='EURUSD']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8492552012803153"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#if we try a triangular arbitrage\n",
    "#USD to JPY to EUR\n",
    "#we would obtain a smaller number\n",
    "#it proves that dijkstra delivers the optimal forex rate\n",
    "step1=float(df['bid'][df['currency']=='EURJPY'])\n",
    "step2=float(df['bid'][df['currency']=='USDJPY'])\n",
    "step2/step1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/direct.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#say there is a glitch in EURCHF bid price\n",
    "#what will happen?\n",
    "glitch=df['bid'][df['currency']=='EURCHF'].item()-0.0011\n",
    "forex.append('CHF','EUR',-np.log(1/glitch))\n",
    "\n",
    "#reset status for dijkstra\n",
    "forex.clear(whole=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#consistency check\n",
    "answer=graph.dijkstra(forex,'USD','EUR')\n",
    "\n",
    "answer2=bellman_ford(forex,'USD','EUR')\n",
    "\n",
    "answer==answer2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The triangular arbitrage path is ['USD', 'CHF', 'EUR']\n"
     ]
    }
   ],
   "source": [
    "#voila, riskless arbitrage\n",
    "print(f'The triangular arbitrage path is {answer[1]}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/arbitrage.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "#lets build a complete graph adt and implement bellman ford algorithm\n",
    "forex=graph.graph()\n",
    "for i in df.index:\n",
    "    forex.append(df['currency'][i][:3],\n",
    "                 df['currency'][i][3:],-np.log(df['bid'][i]))\n",
    "    forex.append(df['currency'][i][3:],\n",
    "                 df['currency'][i][:3],-np.log(1/df['bid'][i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'AUD': {'JPY': -4.429160666307817, 'USD': 0.27496330004400615},\n",
       " 'JPY': {'AUD': 4.429160666307817,\n",
       "  'CHF': 4.718829173882046,\n",
       "  'EUR': 4.867288266308598,\n",
       "  'GBP': 4.994350073465887,\n",
       "  'USD': 4.703892718905732},\n",
       " 'USD': {'AUD': -0.27496330004400615,\n",
       "  'EUR': 0.16322368110201413,\n",
       "  'GBP': 0.29020388999529034,\n",
       "  'CHF': 0.01491061273575424,\n",
       "  'JPY': -4.703892718905732},\n",
       " 'CHF': {'JPY': -4.718829173882046,\n",
       "  'EUR': 0.14850620829922395,\n",
       "  'GBP': 0.2755082715200721,\n",
       "  'USD': -0.01491061273575428},\n",
       " 'EUR': {'CHF': -0.14850620829922395,\n",
       "  'GBP': 0.12715178566048355,\n",
       "  'JPY': -4.867288266308598,\n",
       "  'USD': -0.16322368110201407},\n",
       " 'GBP': {'EUR': -0.1271517856604836,\n",
       "  'CHF': -0.2755082715200721,\n",
       "  'JPY': -4.9943500734658866,\n",
       "  'USD': -0.2902038899952903}}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#the complete graph adt\n",
    "forex.reveal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "negative cycle exists!",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-17-3d24cc3aba9b>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;31m#there is a negative cycle\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[1;31m#we got error message\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 3\u001b[1;33m \u001b[0mbellman_ford\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mforex\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;34m'USD'\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;34m'EUR'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-6-2a67b7f0fe74>\u001b[0m in \u001b[0;36mbellman_ford\u001b[1;34m(ADT, start, end)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[1;32mfor\u001b[0m \u001b[0ml\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mADT\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0medge\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mk\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m             \u001b[1;32mtry\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m                 \u001b[1;32massert\u001b[0m \u001b[0mdistance\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mk\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mADT\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mweight\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mk\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0ml\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m>=\u001b[0m\u001b[0mdistance\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0ml\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;34m'negative cycle exists!'\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mexcept\u001b[0m \u001b[0mKeyError\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mpass\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mAssertionError\u001b[0m: negative cycle exists!"
     ]
    }
   ],
   "source": [
    "#there is a negative cycle\n",
    "#we got error message\n",
    "bellman_ford(forex,'USD','EUR')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}