论文标题
使用加泰罗尼亚三角
Exact Solution to the Chow-Robbins Game for almost all n, using the Catalan Triangle
论文作者
论文摘要
Chow-Robbins硬币游戏中的回报是您停止时的比例。 Chow and Robbins（1965）知道何时停止以最大化的期望，他们证明存在整数存在$ {k_n} $，因此当Heads减去尾巴达到这一点时，停止是最佳的。找到$ {k_n} $的确切无法解决，除了计算机有限的情况下。我们显示$ {k_n} = \ left \ lceil {α\ sqrt n \，\， - 1/2 \，\，\，\， + \，\，\ frac {{\ left（{ - { - 2ζ（ - 2ζ（ - 1/2）} \ right） 1/4}}}} \ right \ rceil $几乎是所有n，其中$α$是shepp -walker consance。这来自我们的估计$ {β_n} =α\ sqrt n \，\， - \， - 1/1/2 \，\，\，\，\， + \ ,, \，\，\，\，\，\，\，\，\，\，\ frac { - { - \ right）\sqrtα}} {\sqrtπ} {n^{ - 1/4}} + o \ left（{n^{ - 7/24}} \ right）由Dvoretzky（1967）（1967）定义的实数定义的实数（1967）所定义的实数的$更加普遍的价值函数，该函数的第一个参数更容易分析，并且可以分析和分析。 Christensen and Fischer（2022）从数值证据中猜想了一个$ O（{n^{ - 1/4}}）$依赖性。我们的证明利用涉及加泰罗尼亚和加泰罗尼亚三角形数字的时刻，这些数字出现在向后诱导的树中出现，以及广义的向后诱导原理。这是由Häggström和Wästlund（2013）的想法的动机，它是利用地平线上的上和下值边界的向后诱导，他们用数值来解决一些情况。克里斯滕森（Christensen）和菲舍尔（Fischer）的范围更好，解决了更多案件。我们使用Skorohod的嵌入来从Brownian类似物中获得简单的上和下限。我们的上限是克里斯滕森（Christensen）和菲舍尔（Fischer）以不同的方式发现的界限。我们首先将它们用于更多示例，但是新想法是在树上使用代数使用它们，并以反馈来获得边界附近的较尖锐的价值估算，以解决几乎所有n。
The payoff in the Chow-Robbins coin-tossing game is the proportion of heads when you stop. Knowing when to stop to maximize expectation was addressed by Chow and Robbins(1965), who proved there exist integers ${k_n}$ such that it is optimal to stop when heads minus tails reaches this. Finding ${k_n}$ exactly was unsolved except for finitely many cases by computer. We show ${k_n} = \left\lceil {α\sqrt n \,\, - 1/2\,\, + \,\,\frac{{\left( { - 2ζ( - 1/2)} \right)\sqrt α}}{\sqrt π}{n^{ - 1/4}}} \right\rceil$ for almost all n, where $α$ is the Shepp-Walker constant.This comes from our estimate ${β_n} = α\sqrt n \,\, - 1/2\,\, + \,\,\frac{{\left( { - 2ζ( - 1/2)} \right)\sqrt α}}{\sqrt π}{n^{ - 1/4}} + O\left( {n^{ - 7/24}} \right)$ of real numbers defined by Dvoretzky(1967) for a more general Value function which is continuous in its first argument and easier to analyze. An $O({n^{ - 1/4}})$ dependence was conjectured by Christensen and Fischer(2022) from numerical evidence. Our proof uses moments involving Catalan and Catalan triangle numbers which appear in a tree resulting from backward induction, and a generalized backward induction principle. It was motivated by an idea of Häggström and Wästlund(2013) to use backward induction of upper and lower Value bounds from a horizon, which they used numerically to settle a few cases. Christensen and Fischer, with much better bounds, settled many more cases. We use Skorohod's embedding to get simple upper and lower bounds from the Brownian analog; our upper bound is the one found by Christensen and Fischer in a different way. We use them first for many more examples, but the new idea is to use them algebraically in the tree, with feedback to get a sharper Value estimate near the border, to settle almost all n.
