在线交易最优停止算法：从秘书问题到竞争比3.523与2的实现

1. 项目概述当在线交易遇上经典秘书问题如果你做过量化交易或者玩过股票、加密货币肯定对“何时买入何时卖出”这个灵魂拷问深有体会。市场瞬息万变价格走势图就像一条蜿蜒的河流你永远不知道下一个浪头是涨是跌。经典的“秘书问题”Secretary Problem给了我们一个优雅的数学框架来思考这类“最优停止”难题面对一系列依次到来的候选人或价格你必须在每次面试或观察价格后立刻决定是否选择他或进行交易一旦错过就无法回头目标是最大化选到最佳人选或获得最大收益的概率。但把秘书问题直接套用到在线交易上会发现有点“水土不服”。在交易中我们通常有两次决策机会一次买入一次卖出。这就催生出了“在线交易秘书问题变体”Online Trading Variant of the Secretary Problem。这个变体的目标不再是选一个人而是要在价格序列中选出一个“低点”买入并在之后的一个“高点”卖出目标是最大化卖出价与买入价的比率即收益。而衡量一个在线算法好坏的核心指标就是“竞争比”Competitive Ratio即使在最坏情况下比如市场被一个恶意的对手操纵你的算法获得的收益与一个能预知未来的“先知”算法获得的最优收益之比也不会低于这个比值。最近算法理论界在这个问题上取得了激动人心的进展有人设计出了强竞争比3.523和弱竞争比2的算法。这里的“强”和“弱”指的是对输入序列的假设不同。强竞争比算法假设价格序列是任意的甚至是对手生成的而弱竞争比算法通常假设价格序列是随机生成的例如顺序是随机排列的。3.523和2这两个数字就像是给在线交易者提供了两把不同特性的“武器”一把追求在最恶劣环境下的稳健保底3.523倍于最优解的损失上限另一把则在平均情况下追求更优的表现2倍于最优解的损失上限。今天我们就来深入拆解这两个算法背后的精巧设计看看理论如何照亮现实的交易决策。2. 问题定义与模型建立从抽象到交易场景在深入算法之前我们必须先把游戏规则讲清楚。理解模型是理解一切的基础。2.1 经典秘书问题回顾假设你要招聘一位秘书有n个候选人依次前来面试。每面试完一个人你必须立刻决定是否录用他。一旦拒绝此人永不回头一旦录用面试立即终止。你不知道后面的人会不会更好你的目标是最大化选到绝对最佳即排名第一候选人的概率。最优策略是“观察再选择”先面试前k个人但不录用只记录其中最优秀的那位作为基准从第k1个人开始一旦遇到比之前所有记录都优秀的人就立刻录用。理论证明当k ≈ n/e (约37% n)时选到最佳的概率最高约为1/e ≈ 36.8%。2.2 在线交易变体SPVT的精确定义我们将价格序列建模为一个长度为n的数字序列p1, p2, ..., pn依次到来。算法在观察到价格pi后必须立即做出不可撤销的决策买入决策如果尚未买入可以选择以当前价格pi买入。买入后状态变为“持有”。卖出决策如果处于“持有”状态可以选择以当前价格pi卖出。卖出后交易结束算法获得收益pi / p_buy卖出价除以买入价。跳过也可以选择什么都不做。目标设计一个在线算法ALG使其对于任意或随机价格序列其获得的收益与离线最优收益的比值尽可能好。离线最优收益OPT假设先知可以预知整个价格序列他会在最低价p_min买入在之后出现的最高价p_max且p_max在p_min之后卖出获得最优收益OPT p_max / p_min。如果序列一直下跌没有p_max在p_min之后则最优收益为1即不交易。竞争比CR对于任意或随机输入序列算法收益ALG满足ALG (1/CR) * OPT。也就是说CR越小算法性能相对先知越接近但通常我们说“竞争比为CR”指的是这个比值常数CR3.523意味着算法收益至少是先知最优收益的1/3.523 ≈ 28.4%。强竞争比与弱竞争比强竞争比Adversarial/Strong Competitive Ratio假设价格序列由一个恶意的对手生成他知晓你的算法逻辑并试图构造最坏序列来最小化你的收益。在这种“最坏情况分析”下取得的竞争比就是强竞争比。它保证的是算法在任何情况下的性能下限极其稳健。弱竞争比Random Order/Weak Competitive Ratio假设价格序列的值是固定的但到来的顺序是均匀随机排列的。对手无法控制顺序。在这种“平均情况分析”下取得的竞争比就是弱竞争比。它通常比强竞争比更优数值更小但保证力度稍弱。我们的目标就是分别针对这两种场景设计出具有理论保证的算法。3. 核心算法思想与设计哲学面对这样一个两次决策的序列决策问题直觉的策略往往行不通。比如“看到历史最低就买看到历史最高就卖”很容易被对手设套先给你一个极低的价格诱使你买入然后价格一路阴跌再也不回头。因此算法必须引入“随机化”和“阈值”来对抗不确定性。3.1 随机化与阈值对抗未知的核心武器在在线算法领域随机化是打破对手优势的关键。一个确定的算法对手可以精准预测并构造最坏序列。而一个随机化的算法其行为有一定的不确定性对手无法精确针对从而有望获得更好的竞争比。阈值Threshold是另一个核心概念。我们不会在第一个历史最低点就买入而是设定一个动态或静态的“门槛”。只有当价格足够好低于某个阈值时才考虑买入。这个阈值通常基于已观测到的价格信息来计算。对于卖出决策同样如此不会在第一个历史最高点就卖出而是会等待价格超过某个更高的阈值。这两个阈值的设置本质上是在“等待更好机会”和“避免错过所有机会”之间进行概率博弈。3.2 强竞争比3.523算法的设计骨架达到强竞争比3.523的算法其核心思想可以概括为“分阶段观察与随机化阈值”。算法不会从一开始就积极交易而是将整个序列划分为不同的阶段在不同阶段采用不同的、随机化的决策规则。一个典型的设计框架可能包含以下阶段初始观察期算法会拒绝前一部分样本比如前n/e个价格这段时间的唯一目的是收集市场信息建立一个对价格分布范围的初步估计。这个阶段绝不买入。随机化买入阶段在观察期之后算法会生成一个随机的买入阈值。这个阈值通常基于观察期内看到的最低价格乘以一个大于1的随机因子。例如设观察期最低价为m随机选择一个因子r1从某个特定分布中抽取则买入阈值为T_buy m * r1。当后续出现第一个价格低于T_buy时立即买入。注意这里的随机因子r1是关键。如果r1是固定的对手可以设置一个略高于T_buy的价格诱使你错过真正的低点然后一路下跌。随机化使得对手无法精确猜到你的买入阈值。随机化卖出阶段买入之后算法进入卖出决策。同样它会设定一个卖出阈值。这个阈值可能基于买入后的历史最高价或者全局历史最高价再乘以一个小于1的随机因子r2。例如买入后看到的最高价为M则卖出阈值T_sell M * r2。当价格跌破T_sell时立即卖出。注意卖出阈值因子r2 1这创造了一个“止盈回撤”机制。它不追求卖在绝对最高点而是允许从高点回撤一定比例后卖出以此锁定大部分利润避免因贪婪而错失卖出时机。通过精心设计观察期的长度、随机因子r1和r2的概率分布经过复杂的概率分析可以证明该算法在任何对手生成的序列下都能保证ALG (1/3.523) * OPT。数字3.523正是这些参数优化后的结果。3.3 弱竞争比2算法的设计骨架在随机顺序模型下由于输入序列是随机排列的问题变得“友好”一些。此时一个更简单、更激进的策略往往能取得更好的竞争比例如“基于排名的单阈值策略”。其核心思想是我们不再关注价格的具体数值而是关注其在全局序列中的相对排名。买入决策设定一个固定的排名阈值R_buy。例如R_buy √nn的平方根。算法持续追踪已看到的价格中的最低价即当前排名第一的价格。当看到的价格其全局排名在随机排列假设下其排名期望是均匀分布的足够好比如是当前看到中的历史最低并且满足某种与R_buy相关的条件时例如这是自开始以来第k个历史最低价且k与R_buy有关则买入。 在随机顺序下全局最低价大概率会出现并且均匀地出现在序列的各个位置。通过设置合适的R_buy可以以高概率在全局最低价附近买入。卖出决策买入后设定一个卖出阈值。这个阈值可以是一个固定的收益倍数例如α倍。一旦当前价格达到买入价的α倍立即卖出。或者也可以采用一个基于买入后价格排名的动态阈值。为什么弱竞争比能到2因为在随机顺序下算法有很高的概率以接近全局最低价买入。之后只要设置一个合理的卖出阈值α就能以高概率捕获一个不错的收益。通过优化R_buy和α可以进行概率分析证明算法的期望竞争比可以达到2。也就是说在平均情况下算法的收益至少是最优收益的一半。这个证明通常利用了随机排列的对称性和性质比对抗情形下的分析更简洁。实操心得从这两个算法骨架可以看出对抗环境下的算法强竞争比更注重防御通过随机化来增加对手的破坏成本策略偏保守。而随机环境下的算法弱竞争比更注重进攻利用输入分布的友好性采取更积极的策略追求更高的平均收益。在实际应用中你需要根据对市场“恶意程度”的判断来选择合适的模型。4. 强竞争比3.523算法的详细实现与参数推导理论是优美的但实现需要具体的步骤和参数。我们来详细拆解一个能达到强竞争比3.523的经典算法范式。请注意以下参数是经过理论推导优化的结果。4.1 算法步骤详解假设总时间窗口价格数量n已知。如果n未知也有相应的扩展技术这里我们先讨论已知的情况。初始化设定观察期长度t floor(n / e)。这里e是自然常数floor是向下取整。这大约占总数量的37%。在观察期内只记录看到的历史最低价格m_t。阶段一随机化买入观察期结束后从区间[1, β]上按照某个特定概率密度函数f(x)随机采样一个因子r。这里的β是一个大于1的常数具体值后续确定。计算买入阈值T_buy m_t * r。从第t1个价格开始检查每个到来的价格p_i如果p_i T_buy且算法尚未买入则立即以价格p_i买入。记买入价为p_buy p_i并进入阶段二。如果直到序列结束都未触发买入则算法不进行任何交易收益为1。阶段二随机化卖出买入后初始化M p_buy记录买入后的历史最高价。从某个区间[γ, 1]上按照另一个概率密度函数g(y)随机采样一个因子s。这里γ是一个小于1的常数。计算动态卖出阈值T_sell M * s。注意M是动态更新的每当看到新的价格p_j M时更新M p_j并重新计算T_sell M * s。对于买入后到来的每一个价格p_j更新M max(M, p_j)。重新计算T_sell M * s。如果p_j T_sell则立即以价格p_j卖出。记卖出价为p_sell p_j算法结束收益为p_sell / p_buy。如果直到序列结束都未触发卖出则以最后一个价格p_n卖出或视为收益为1如果p_n p_buy。4.2 关键参数的选择与优化算法性能完全取决于四个关键参数观察期比例1/e、买入随机因子r的分布f(x)及其上限β、卖出随机因子s的分布g(y)及其下限γ。经过理论上的优化分析通常涉及求解一系列积分方程或优化问题可以得到一组近似最优参数观察期比例t/n ≈ 1/e ≈ 0.367。这与经典秘书问题一脉相承是信息收集与行动机会的最佳平衡点。买入阈值参数β的优化值大约在2.0左右。这意味着你的买入阈值最高可能设为观察期最低价的2倍。f(x)通常选择为[1, β]区间上的某种幂律分布例如f(x) ∝ 1/x^2使得选择较低阈值接近1的概率更高这符合尽早买入好价格的直觉。卖出阈值参数γ的优化值大约在0.6左右。这意味着你的卖出阈值最低可能设为买入后历史最高价的60%。g(y)的分布可能更倾向于接近1的值例如g(y) ∝ 1/(1-y)在[γ, 1]上使得卖出阈值更可能贴近高点以获取更大收益。竞争比3.523的推导 竞争比CR由以下不等式保证E[ALG] (1/CR) * OPT。通过分析算法在最坏情况序列下的表现来推导CR。 最坏序列通常具有“锯齿”或“陷阱”结构。例如先给一个极低的价格在观察期内引诱你设定一个较低的m_t然后给一个略高于m_t*r对于大多数r的价格让你错过买入最后价格一路走低。或者在你买入后价格先飙升到一个高点然后迅速暴跌考验你的卖出阈值s。通过计算算法在所有可能随机选择(r, s)下面对最坏序列时能获得的最小收益与OPT的比值并最大化这个最小值就可以反推出最优的CR以及对应的参数分布。3.523就是这个优化过程得到的下界。具体的推导涉及复杂的概率论和最坏情况分析是理论计算机科学的研究范畴。注意事项这个算法是理论上的存在性证明它告诉我们“可以做到多好”。实际编码实现时你需要为f(x)和g(y)指定具体的、可采样的概率分布。论文中通常会给出这些分布的精确数学形式。直接使用上述近似参数β2, γ0.6实现的算法其竞争比可能略差于3.523但通常仍在同一个数量级例如4左右这已经是一个非常强的保证了。5. 弱竞争比2算法的详细实现与概率分析现在我们转向更乐观的随机顺序模型。这里介绍一个概念清晰、易于理解且能达到竞争比2的算法。5.1 算法描述基于排名的阈值策略这个算法不需要复杂的随机化它本质上是确定性的但其优秀性能依赖于输入序列是随机排列的这一假设。算法步骤设定排名阈值令k floor(√n)。我们将关注那些“打破历史记录”的价格即当前看到的历史最低价对于买入或买入后的历史最高价对于卖出。买入阶段初始化一个计数器counter 0记录我们看到历史最低价的次数。从左到右扫描价格序列p1, p2, ..., pn。维护一个变量current_min记录至今看到的历史最低价。当遇到一个价格p_i使得p_i current_min时即新的历史最低价出现更新current_min p_i。计数器counter 1。如果这是第k次出现新的历史最低价即counter k则立即以价格p_i买入。记p_buy p_i。如果扫描完整个序列出现历史最低价的次数仍不足k次则算法不买入收益为1。卖出阶段一旦买入算法目标变为获得至少α倍的收益。α是一个待优化的常数。继续扫描买入之后的价格。如果遇到一个价格p_j使得p_j α * p_buy则立即以价格p_j卖出。算法结束收益为p_j / p_buy α。如果直到序列结束都未达到α倍收益则以最后一个价格p_n卖出收益为p_n / p_buy可能小于1。5.2 为什么竞争比是2概率分析直观解释算法的分析依赖于随机排列的一个关键性质均匀随机排列中元素的顺序是均匀随机的。这意味着全局最低价p_min等可能地出现在n个位置中的任何一个。全局最高价p_max也等可能地出现在n个位置中的任何一个。买入分析 我们设定k √n。在随机排列中全局最低价p_min有很高的概率出现在序列的前半部分并且它很可能也是我们观察到的前√n个“历史最低价”之一。更精确的分析表明当n很大时算法在全局最低价p_min处买入的概率是一个常数大约为1/e当k n/e时经典秘书问题的成功概率。但我们这里选择k √n是为了与卖出阶段耦合分析。实际上通过调整k和α可以优化竞争比。卖出分析 假设我们成功以价格p_buy买入且p_buy接近p_min。我们的目标是获得α倍收益即卖出价至少为α * p_buy。离线最优收益是OPT p_max / p_min。 我们需要分析在随机排列中在买入点之后出现一个价格至少为α * p_buy的概率。由于p_buy ≈ p_min这近似于要求出现一个价格至少为α * p_min。通过计算概率并权衡“买入成功概率”和“卖出成功概率”我们可以将算法的期望收益E[ALG]表示为一个关于k和α的函数。然后我们证明对于所有可能的输入集合固定数值随机排列都有E[ALG] (1/2) * OPT。参数选择 要达到竞争比2需要精心选择k和α。一个经典的选择是k n / e沿用经典秘书问题的最优观察点数α e自然常数约2.718在这种情况下可以证明E[ALG] (1/e) * OPT不这里需要更精细的分析。实际上对于“买入后等待固定倍数收益”的策略其竞争比下界是2。具体的证明会展示无论对手如何固定价格集合但随机排列算法的期望收益至少是OPT/2。实操心得弱竞争比算法实现起来非常简单几乎没有任何复杂的随机操作。它的强大完全建立在“随机顺序”的假设上。在真实的金融市场中价格序列显然不是均匀随机排列的它存在趋势、自相关和波动聚集性。因此这个算法更像一个理论基准告诉我们当市场没有记忆、没有恶意操纵时简单策略能达到多好的效果。它可以作为检验市场是否具备“弱有效性”的一个理论参照。6. 两种算法的对比、应用场景与实战调优理解了原理和实现我们最终要回到应用层面。这两个算法给我们带来了什么启示又该如何在现实世界中参考它们6.1 强竞争比 vs. 弱竞争比理念与适用场景对比特性维度强竞争比算法 (CR≈3.523)弱竞争比算法 (CR2)核心假设对抗性序列最坏情况随机顺序序列平均情况设计哲学稳健优先。假设对手存在且强大通过随机化增加其破坏难度保证性能下限。收益优先。利用输入分布的友好性采取更积极、简单的策略追求更好的平均表现。算法复杂度较高。需要维护动态阈值、进行随机采样逻辑相对复杂。较低。主要是比较和计数逻辑清晰简单。参数敏感度高。随机因子的分布、观察期长度等需要精细调优参数设置直接影响理论保证。较低。主要参数是排名阈值k和收益倍数α有较宽泛的优值区间。实战启示适用于高风险、波动剧烈、可能存在操纵的市场环境如小市值加密货币、流动性不足的标的。它教你如何通过“不可预测性”来保护自己。适用于有效性较强、噪声为主、趋势不明显的震荡市场。它教你如何利用市场的“随机性”来制定简单规则。心理映射像一名谨慎的狙击手。大部分时间在观察和隐藏随机化阈值只有机会完全符合预设的、经过计算的苛刻条件时才出手。像一名纪律性的趋势跟踪者。设定明确的入场第k个新低和出场固定盈亏比信号机械执行。6.2 从理论到实战参数调优与风控融合理论算法提供了骨架实战中我们需要为其注入血肉。1. 时间窗口n的动态估计 理论算法假设总时间n已知。实战中交易是连续不断的。我们可以采用滑动窗口法定义你关注的交易周期例如“过去30个交易日”、“本季度”、“本次趋势波段”。将n定义为这个窗口的预期长度并随着时间推移动态更新。或者使用“遗忘因子”或指数加权的方式来计算观察期内的统计量如历史最低价让算法适应无限序列。2. 随机因子分布的工程化 理论上的最优分布可能不易采样。我们可以用近似分布替代买入因子r可以尝试从[1, 2]的均匀分布或1 Beta(1,2)分布中采样。后者会让概率密度向1倾斜更倾向于设定较低的买入阈值。卖出因子s可以尝试从[0.6, 1]的均匀分布或0.6 0.4*Beta(2,1)分布中采样。后者会让概率密度向1倾斜更倾向于设定较高的卖出阈值。注意替换分布后原有的理论竞争比保证可能不再严格成立但算法框架依然有效。可以通过历史数据回测来验证新参数集的效果。3. 融入基本面与风险管理 纯技术面的算法交易是危险的。必须将算法作为执行工具而非圣杯。买入条件叠加仅在算法发出买入信号且标的符合基本面筛选如财报健康、行业景气时执行。硬性止损无论算法的卖出信号如何必须设置绝对止损线例如买入价下跌10%强制卖出。这是对抗算法失效和黑天鹅事件的最后防线。头寸管理根据算法的历史胜率、波动率通过凯利公式或其他方法动态计算单次投入资金比例避免因连续亏损而爆仓。6.3 常见陷阱与排查清单即使算法设计精妙实战中也会踩坑。以下是一些常见问题及应对思路问题现象可能原因排查与解决思路强竞争比算法频繁踏空从未触发买入1. 观察期m_t过低市场处于长期下跌趋势的初期。2. 买入随机因子r的分布过于保守值太小导致T_buy设得太低。1. 检查观察期数据是否具有代表性。可考虑使用更长历史数据或滚动中位数而非最低价来计算m_t。2. 调整r的分布增加其期望值如改用均匀分布。强竞争比算法买入后立即被套买入后价格持续低于买入价1. 对手市场在观察期制造了虚假低点m_t。2. 卖出因子s分布导致卖出阈值T_sell初始值过低无法有效止损。1. 接受这是对抗性算法的固有风险。可结合趋势指标过滤避免在明确下跌趋势中买入。2. 引入独立于算法的硬性百分比止损如-5%。弱竞争比算法在牛市中卖飞刚达到α倍收益就卖出错过后面大涨算法设计本就是锁定α倍收益不追求卖在最高点。这是其纪律性也是局限性。1. 采用分步卖出策略达到α倍时卖出一半剩余部分采用更宽松的卖出规则如跟踪止盈。2. 动态调整α在牛市环境中根据市场情绪指标适当调高α。弱竞争比算法在震荡市中反复挨打频繁触发第k个新低买入然后小幅反弹达不到α倍又下跌市场处于无趋势震荡状态价格频繁创局部新低但无持续动能。1. 增加买入过滤条件如要求价格必须低于某个长期均线如200日均线。2. 增大k值降低买入频率只捕捉更重要的低点。3. 降低α值追求更小但更频繁的收益。两种算法回测表现均远差于理论1. 市场不符合算法假设如强趋势、高自相关。2. 交易成本手续费、滑点未计入。3. 参数未针对当前市场风格优化。1. 进行市场状态识别。在趋势市考虑使用趋势跟踪策略而非均值回归/最优停止策略。2. 在回测中精确计入交易成本α倍收益必须能覆盖成本并有盈余。3. 使用滚动窗口或机器学习方法动态优化参数k,α,β,γ等。理论上的竞争比是一个最坏情况或平均情况的下界保证。它告诉你“至少不会差于”。在实际表现良好的市场阶段算法的收益完全可能接近甚至超过OPT。这些算法提供的真正价值是一种系统化的、有数学依据的决策框架帮助交易者克服贪婪与恐惧将复杂的择时问题转化为可执行、可分析、可优化的规则。