A PROBABILISTIC FORMULA FOR THE CONCAVE HULL OF A FUNCTION

Let D be a compact, convex domain in d-dimensional Euclidean space and let f be a nonnegative real-valued function defined on D. The classic al optimal stopping problem is to find a stopping time tau that attai ns the supremum v(x) = sup(tau) E(x)f(B(tau)). Here, B is a d-dimensio nal Brownian motion with absorption on the boundary of D and the supre mum is over all stopping times. It is well known that v is characteriz ed as the smallest superharmonic majorant of f. In this paper, we modi fy this problem by allowing B to be essentially any drift-free diffusi on (with absorption, as before, on the boundary of D). For example, it could be a Brownian motion diffusing on some lower dimensional affine set. In addition, one is allowed to switch among these diffusions at any time. The problem is to find a stopping time and a switching strat egy that together attain the supremum over all stopping times and all switching strategies. For this problem, we show that v is characterize d as the smallest concave majorant of f. The domain D can be decompose d into a disjoint union of relatively open convex sets on each of whic h the function v is affine. Furthermore, the union of the zero-dimensi onal convex sets is contained in the set on which v = f. An optimal sw itching strategy is any strategy that at all times diffuses in the aff ine hull of the current convex set. When the diffusion reaches the bou ndary of the current convex set, it will lie on a lower dimensional co nvex set and must then diffuse on the affine hull of this new set. Thi s process continues until the set on which v = f is reached, which is the optimal stopping time.