A Random Version of Shepp's Urn Scheme

Abstract

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 wants to stop. The player knows n, the total number of balls, but only knows 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 he draws. 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 uses the optimal drawing policy. Since the optimal drawing policy is pretty 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.