Maximum sum for step-limited random walk

Question

There are two urns with $n$ balls each from which we draw without replacement. Each of the $t=2 \cdot n$ has equal probability to be selected. All balls from the first urn have value $-1$ while all balls from the second urn have value $+1.$

Initially, we set sum $S_0=0$ and then we cumulatively add the value of the last drawn ball. In total, we select $r \leq t$ balls. At which value of $r$ should we stop to maximize $S,$ or what is the minimum threshold value for $S_r$ to stop at draw $r$ as a function of either $n$ or $t,$ respectively?

An example sequence for $n=5$ is as follows:

$$ [x_1,\ldots,x_{10}] = [-1, 1, -1, 1, -1, -1, 1, 1, 1, -1]$$

with cumulative sum

$$ [S_1,\ldots,S_{10}] = [-1, 0, -1, 0, -1, -2, -1, 0, 1, 0]$$

So for this particular sequence the optimal stopping rule would be after $r=9$ to yield a maximum sum of $S_9 = 1.$

FYI I included a simulation-based solution below. Can I have an analytical solution please?

Answer 1

I did a Monte Carlo Simulation for different values of $t \in \{2,4,\ldots, 1000\}.$ For each $t$ I ran 1,000 simulations where I exhausted/emptied all balls in both urns, and I recorded the average maximum value of $S$ and the corresponding average position $r$ where this maximum occurred. From the simulations it appears than the optimal r is roughly at $r = 0.45 *t$ and some optimal values for $S$ as as follows:

$$n=10,t=20: S_5 = 2.3$$ $$n=13,t=26: S_{12} = 2.8$$ $$n=50,t=100: S_{45} = 6$$

Some R-code:

f<-function(n) {
tn <- 2*n
vect <- c(rep(1,n),rep(-1,n))   
iterations <- 1000
maxVect <- vector()
maxPosVect <-  vector()
for(count1 in 1:iterations) {
 ord <- sample(x=1:tn,size=tn,replace=FALSE)
 vecto <- vect[ord]
 csumvecto <- cumsum(vecto)
 maxcsum <- max(csumvecto)
 maxVect <- c(maxVect,maxcsum)
 posmax <- which.max(csumvecto)
 maxPosVect <- c(maxPosVect,posmax)
}
meanMaxVect <- mean(maxVect)
meanMaxPosVect <- mean(maxPosVect)
#print(meanMaxVect)
#print(meanMaxPosVect)
return(c(meanMaxVect,meanMaxPosVect))
}

nVect <- 1:500
tnVect <- 2*nVect
maxSumVect <- vector()
maxPosVect <- vector()
for(val in nVect) {
  res <- f(val)
  maxSumVect <- c(maxSumVect,res[1])
  maxPosVect <- c(maxPosVect,res[2])
}
maxPosVectRatio = maxPosVect / tnVect

plot(tnVect,maxSumVect,main="Avg. max. sum value")
plot(tnVect,maxPosVect,main="Avg. max. sum position")
plot(tnVect,maxPosVectRatio,main="Avg. max. sum position / tn ratio")