[HN Gopher] Trading with BDDs
___________________________________________________________________
Trading with BDDs
Author : taeric
Score : 75 points
Date : 2022-12-22 20:57 UTC (1 days ago)
(HTM) web link (taeric.github.io)
(TXT) w3m dump (taeric.github.io)
| worik wrote:
| Really? More technical analysis?
|
| It does not work, in the general case.
|
| Simply put the efficient market hypothesis is true, in most
| cases, for most people, in most markets.
|
| It is possible (I know of two cases: pairs trading in stock
| markets and momentum trading in bond markets) where it has had
| success for finite periods of time.
|
| What ever goodness can be found is traded away by very sharp and
| well resources actors before anybody else can get to them.
|
| It is a zero sum game, and the game has some very well resourced
| actors in it that want very much for you to put all your money
| into technical trading, thank you. They are crooks and thieves,
| and include some of the richest people on the planet.
|
| This is like astrology, homoeopathy, aroma therapy... If it seems
| it works it s for some other reason.
|
| Stay well clear of this hocus pocus. So many computer people gone
| down this road. The only way to make money out of technical
| trading is to get paid a salary to implement some one else's
| algorithm.
| 323 wrote:
| One big conceptual problem is that you can't use the technology
| of today to trade on 1980 prices.
|
| So showing big profits on decades old prices is meaningless, the
| market was much "softer" back than since there was little machine
| learning, large clean datasets, very accessible computation
| power, and so on.
| taeric wrote:
| Agreed. And, in general, I don't like this toy problem. Largely
| because of how silly it is. I did like getting a fast solution
| using a technique new to me, though.
| MuffinFlavored wrote:
| > Binary Decision Diagrams (BDDs)
|
| where does intraday/momentum/swing trading fit into this? like
| little "algorithms" looking at indicators or
| "open/high/low/close" candles + volume to pick direction, entry,
| stop loss/limit?
|
| i've seen something that looks at things like VWAP/EMA fast/slow
| crossover and then pours into 0 days to expiration.
| "guessing/following" the market along for a 0.5% move in the
| index can turn into 100-500% ROI in options. obviously has its
| drawbacks/isn't perfect.
|
| i always felt the results with "trading" (given how market the
| random is overall) aren't worth it.
|
| i'd be curious how the results of this compare to basic
| "technical analysis".
| taeric wrote:
| Agreed that this isn't worth much as a legit trading algorithm.
| That is the framing I was given to the puzzle.
|
| With how fast this answers the question of the boolean linear
| program, I suspect it could be used for some neat tricks. That
| said, if you try to make the decision diagram smarter, it tends
| to explode in size. (At least, I think it does?)
| [deleted]
| taeric wrote:
| I didn't post this as a "show hn," as I wasn't sure it counted
| for that. I'd be delighted to know if anything I did wrong in
| this. Was fun, regardless.
| vlovich123 wrote:
| There's a bug in the first diagram for the rightmost node 6. Left
| edge everywhere else represents true but it ends in false.
| taeric wrote:
| The dotted line is false for the variable. If you have an
| outstanding trade, puzzle is you have to sell on the last day.
| So, false for that day would not be allowed if you have an open
| buy, right?
| scaredginger wrote:
| It would be nice to understand what you're trying to find here.
| What are the constraints?
|
| Do I have to start and end with a neutral position? Am I allowed
| to short; i.e. do I have to buy before I sell? What are the
| limits on liquidity? Do I have unlimited access to margin? Is
| there a limit on holding time? Are there any borrowing costs? Are
| there any transaction costs?
|
| All these should be addressed in the problem definition
| taeric wrote:
| Ah, apologies. I will try to get that added today
|
| Basic answer is that you can only have one outstanding buy, and
| must end with no open trade. My understanding is this is/was a
| common interview style question.
| derriz wrote:
| Your terminology is confusing as I think you're using
| technical terms ("trade", "open", etc) in a way that does not
| reflect their usual meaning. A "trade" generally refers to an
| event not state, while I think you want to refer to
| "position" which is a component of trading state. E.g. by
| "ending with no open trade", you mean ending with no position
| or "flat".
| taeric wrote:
| That makes sense. I thought I lifted the words from others,
| such that I didn't think I was making up any terms. Will
| try to scrub all terms and describe things directly.
| svat wrote:
| I enjoyed this post, thank you! For the benefit of anyone else
| reading, some context that I felt would have helped: The toy
| problem being considered is the following. You are given a
| sequence of historical prices (of a single stock or index or
| whatever), one for each day: day 1 2 3 ...
| n price p1 p2 p3 ... pn
|
| The task is to annotate each day i with a (retroactive) decision
| z_i [?] {buy, sell, do nothing}, and do this optimally, subject
| to the constraint that you cannot sell before you buy, cannot
| "buy" twice without an intervening "sell" and vice-versa, etc.
| And there are indeed dynamic-programming algorithms to solve this
| quickly, which you can find on Leetcode writeups and whatnot.
|
| (Whether or not this has any resemblance to real-world trading is
| not the point of the toy problem, which is about computational
| techniques. See e.g. Knuth's article "Are toy problems useful?"
| from Chapter 10 of https://cs.stanford.edu/~knuth/cs.html, or
| "Puzzles versus the real world" on pages 7-9 of TAOCP Vol 4A.)
|
| Another way to model it is with two-valued y_i [?] {do nothing,
| "change state"}, where "change state" means buy if you haven't
| bought and sell if you have, with the last day's decision forced
| (you have to end in the sold state), which shows why there are
| 2^{n-1} possibilities to optimize over.
|
| But there's yet another way of modeling the problem, presented in
| this post, where we have 2n-2 _boolean_ variables x1, x2, x3, x4,
| ... denoting respectively the choices of whether or not to "buy
| on day 1", "sell on day 2", "buy on day 2", "sell on day 3", and
| so on, and now the problem becomes one of the form:
| maximize w1x1 + w2x2 + w3x3 + ... such that f(x1, x2, x3,
| ...) = 1
|
| where f is a boolean function denoting whether the 0-1 values
| assigned to the x_i variables is "valid" (does not have both buy
| and sell on the same date, has a buy before a sell, etc).
|
| Now, this may seem hard to optimize over, but BDDs (binary
| decision diagrams) are a data structure that can represent such
| functions compactly, and in this case (because of the problem
| structure) the entire truth table (over all possible 2^{2n-2}
| assignments to xi, with 2^{n-1} "true" values among them) can be
| represented as a BDD with 2.5n nodes, and with a standard
| algorithm can be optimized over.
|
| This gives an algorithm that is just as fast as the dynamic
| programming algorithm (almost? asymptotically?), and is a fun
| exercise to play with BDDs, which this post describes very well.
| taeric wrote:
| Thanks! Better description of the toy than I put on the page.
| :)
|
| I haven't used a bdd before, so I was surprised this worked as
| well as it did. I haven't tried this with DP, but the solutions
| I saw that did weren't able to handle this much data. I'm
| assuming I just saw sub optimal solutions?
| vitus wrote:
| I might be misunderstanding the problem statement, but my
| take:
|
| My impression is that for N max trades and M days of data,
| the "obvious" DP solution should be 2*N entries and O(NM)
| time, by tracking best profit for n trades whether you have
| the stock, where your update looks something like
| profit[trade_count=n, day=m, has_stock] =
| max(profit[trade_count=n, day=m-1, has_stock],
| profit[trade_count=n-1, day=n-1, has_stock] +
| transaction_cost[day=n, has_stock]) -- namely, as you've
| described in the article, either do nothing, or make a trade.
| Of course, you wouldn't store the full history -- you'd only
| need yesterday's data and today's update.
|
| Adding accounting to track the trade history is doable
| without bloating runtime too much, but it does increase space
| usage substantially.
|
| That said, if you don't have to keep to a strict number of
| trades, the DP solution should be able to fit in constant
| space (well, linear in number of days if you want to keep
| track of history for the best sequence of trades).
|
| I really like the idea in the article of adding a transaction
| cost and varying that to constrict the number of trades -- it
| reminds me of a cooling schedule for simulated annealing, and
| it's definitely not an approach I see interview candidates
| reaching for regularly.
| taeric wrote:
| That all sounds reasonable. I'm not sure what the solutions
| I saw were trying. They definitely went slower, though.
| Hours for one of the solutions I saw.
| leethargo wrote:
| A great resource for optimization with decision diagrams is the
| website by Willem-Jan van Hoeve from Carnegie Mellon [1].
|
| They go beyond binary (the M in MDD stands for multi-valued) and
| they derive primal heuristics and relaxations from cropped/merged
| diagrams of bounded size.
|
| [1] https://www.andrew.cmu.edu/user/vanhoeve/mdd/
___________________________________________________________________
(page generated 2022-12-23 23:01 UTC)