A Random Version of Shepp's Urn Scheme

In this paper, we consider the following random version of Shepp's urn scheme: A player is given an urn with n balls. p of these balls have value +1 and n-p have value -1. The player is allowed to draw balls randomly, without replacement, until he or she wants to stop. The player knows n, the total number of balls, but knows only that p, the number of balls of value +1, is a number selected randomly from the set {0, 1,2,...,n}. The player wishes to maximize the expected value of the sum of the balls drawn. We first derive the player's optimal drawing policy and an algorithm to compute the player's expected value at the stopping time when he or she uses the optimal drawing policy. Since the optimal drawing policy is rather intricate and the computation of the player's optimal expected value is quite cumbersome, we present a very simple drawing policy, which is asymptotically optimal. We also show that this random urn scheme is equivalent to a random coin tossing problem.