在线交易最优停止算法：从秘书问题到竞争比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个人（但不录用），只记录其中最优秀的那位作为基准；从第k+1个人开始，一旦遇到比之前所有记录都优秀的人，就立刻录用。理论证明，当k ≈ n/e (约37% n)时，选到最佳的概率最高，约为1/e ≈ 36.8%。

2.2 在线交易变体（SPVT）的精确定义

我们将价格序列建模为一个长度为n的数字序列p1, p2, ..., pn，依次到来。算法在观察到价格pi后，必须立即做出不可撤销的决策：

1. 买入决策：如果尚未买入，可以选择以当前价格pi买入。买入后，状态变为“持有”。
2. 卖出决策：如果处于“持有”状态，可以选择以当前价格pi卖出。卖出后，交易结束，算法获得收益pi / p_buy（卖出价除以买入价）。
3. 跳过：也可以选择什么都不做。

目标：设计一个在线算法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”，指的是这个比值常数，CR=3.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的算法，其核心思想可以概括为“分阶段观察与随机化阈值”。算法不会从一开始就积极交易，而是将整个序列划分为不同的阶段，在不同阶段采用不同的、随机化的决策规则。

一个典型的设计框架可能包含以下阶段：

1. 初始观察期：算法会拒绝前一部分样本（比如前n/e个价格），这段时间的唯一目的是收集市场信息，建立一个对价格分布范围的初步估计。这个阶段绝不买入。
2. 随机化买入阶段：在观察期之后，算法会生成一个随机的买入阈值。这个阈值通常基于观察期内看到的最低价格乘以一个大于1的随机因子。例如，设观察期最低价为m，随机选择一个因子r1（从某个特定分布中抽取），则买入阈值为T_buy = m * r1。当后续出现第一个价格低于T_buy时，立即买入。

   注意：这里的随机因子r1是关键。如果r1是固定的，对手可以设置一个略高于T_buy的价格诱使你错过真正的低点，然后一路下跌。随机化使得对手无法精确猜到你的买入阈值。

3. 随机化卖出阶段：买入之后，算法进入卖出决策。同样，它会设定一个卖出阈值。这个阈值可能基于买入后的历史最高价，或者全局历史最高价，再乘以一个小于1的随机因子r2。例如，买入后看到的最高价为M，则卖出阈值T_sell = M * r2。当价格跌破T_sell时，立即卖出。

   注意：卖出阈值因子r2 < 1，这创造了一个“止盈回撤”机制。它不追求卖在绝对最高点，而是允许从高点回撤一定比例后卖出，以此锁定大部分利润，避免因贪婪而错失卖出时机。

通过精心设计观察期的长度、随机因子r1和r2的概率分布，经过复杂的概率分析，可以证明该算法在任何对手生成的序列下，都能保证ALG >= (1/3.523) * OPT。数字3.523正是这些参数优化后的结果。

3.3 弱竞争比2算法的设计骨架

在随机顺序模型下，由于输入序列是随机排列的，问题变得“友好”一些。此时，一个更简单、更激进的策略往往能取得更好的竞争比，例如“基于排名的单阈值策略”。

其核心思想是：我们不再关注价格的具体数值，而是关注其在全局序列中的相对排名。

1. 买入决策：设定一个固定的排名阈值R_buy。例如，R_buy = √n（n的平方根）。算法持续追踪已看到的价格中的最低价（即当前排名第一的价格）。当看到的价格其全局排名（在随机排列假设下，其排名期望是均匀分布的）足够好（比如是当前看到中的历史最低），并且满足某种与R_buy相关的条件时（例如，这是自开始以来第k个历史最低价，且k与R_buy有关），则买入。 在随机顺序下，全局最低价大概率会出现，并且均匀地出现在序列的各个位置。通过设置合适的R_buy，可以以高概率在全局最低价附近买入。
2. 卖出决策：买入后，设定一个卖出阈值。这个阈值可以是一个固定的收益倍数，例如α倍。一旦当前价格达到买入价的α倍，立即卖出。或者，也可以采用一个基于买入后价格排名的动态阈值。

为什么弱竞争比能到2？因为在随机顺序下，算法有很高的概率以接近全局最低价买入。之后，只要设置一个合理的卖出阈值α，就能以高概率捕获一个不错的收益。通过优化R_buy和α，可以进行概率分析，证明算法的期望竞争比可以达到2。也就是说，在平均情况下，算法的收益至少是最优收益的一半。这个证明通常利用了随机排列的对称性和性质，比对抗情形下的分析更简洁。

实操心得：从这两个算法骨架可以看出，对抗环境下的算法（强竞争比）更注重防御，通过随机化来增加对手的破坏成本，策略偏保守。而随机环境下的算法（弱竞争比）更注重进攻，利用输入分布的友好性采取更积极的策略，追求更高的平均收益。在实际应用中，你需要根据对市场“恶意程度”的判断来选择合适的模型。

4. 强竞争比3.523算法的详细实现与参数推导

理论是优美的，但实现需要具体的步骤和参数。我们来详细拆解一个能达到强竞争比3.523的经典算法范式。请注意，以下参数是经过理论推导优化的结果。

4.1 算法步骤详解

假设总时间窗口（价格数量）n已知。如果n未知，也有相应的扩展技术，这里我们先讨论已知的情况。

初始化：

• 设定观察期长度t = floor(n / e)。这里e是自然常数，floor是向下取整。这大约占总数量的37%。
• 在观察期内，只记录看到的历史最低价格m_t。

阶段一：随机化买入

1. 观察期结束后，从区间[1, β]上按照某个特定概率密度函数f(x)随机采样一个因子r。这里的β是一个大于1的常数，具体值后续确定。
2. 计算买入阈值：T_buy = m_t * r。
3. 从第t+1个价格开始，检查每个到来的价格p_i：
   • 如果p_i < T_buy且算法尚未买入，则立即以价格p_i买入。记买入价为p_buy = p_i，并进入阶段二。
   • 如果直到序列结束都未触发买入，则算法不进行任何交易，收益为1。

阶段二：随机化卖出

1. 买入后，初始化M = p_buy（记录买入后的历史最高价）。
2. 从某个区间[γ, 1]上按照另一个概率密度函数g(y)随机采样一个因子s。这里γ是一个小于1的常数。
3. 计算动态卖出阈值：T_sell = M * s。注意，M是动态更新的：每当看到新的价格p_j > M时，更新M = p_j，并重新计算T_sell = M * s。
4. 对于买入后到来的每一个价格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 算法描述：基于排名的阈值策略

这个算法不需要复杂的随机化，它本质上是确定性的，但其优秀性能依赖于输入序列是随机排列的这一假设。

算法步骤：

1. 设定排名阈值：令k = floor(√n)。我们将关注那些“打破历史记录”的价格，即当前看到的历史最低价（对于买入）或买入后的历史最高价（对于卖出）。
2. 买入阶段：
   • 初始化一个计数器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。
3. 卖出阶段：
   • 一旦买入，算法目标变为获得至少α倍的收益。α是一个待优化的常数。
   • 继续扫描买入之后的价格。
   • 如果遇到一个价格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. 弱竞争比：理念与适用场景对比

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 常见陷阱与排查清单

即使算法设计精妙，实战中也会踩坑。以下是一些常见问题及应对思路：

理论上的竞争比是一个最坏情况或平均情况的下界保证。它告诉你“至少不会差于”。在实际表现良好的市场阶段，算法的收益完全可能接近甚至超过OPT。这些算法提供的真正价值，是一种系统化的、有数学依据的决策框架，帮助交易者克服贪婪与恐惧，将复杂的择时问题转化为可执行、可分析、可优化的规则。