Skip to main content
MathOverflow

Return to Question

small typo in F(X,Y)
Source Link
bigO6377
bigO6377
  • 211
  • 1
  • 5

Consider this simple 2-person game I just made up:

Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. However, if he draws all X times, he must keep his last draw as his score.

Player B goes second, and gets to draw up to Y times. Same rules apply to him.

The winner is the player with the highest score. Assuming both A and B play optimally, the probability that player A wins the game is given by F(X,Y). F(X,Y) can be given by the following recurrence relationship (I'll leave it as a separate exercise to derive this):

$F(0,Y) = 0$ $\forall$ Y>0

$F(X,Y) = \left(\frac{Y}{Y+1}\right)*\left(F(X-1,Y)\right)^{\frac{Y}{Y+1}} + \frac{1}{Y+1}$$F(X,Y) = \left(\frac{Y}{Y+1}\right)*\left(F(X-1,Y)\right)^{\frac{Y+1}{Y}} + \frac{1}{Y+1}$

Here's the question: Find the limit $\lim_{n\rightarrow \infty}$ $F(n,n)$. Obviously, this can be approximated numerically directly from the recurrence definition, but I'm wondering if this limit has an elegant closed-form solution (or perhaps can be derived as a unique root of an implicit equation).

The solution has a nice interpretation to it. Basically, as you let each player have more and more turns, how much does this neutralize B's advantage of getting to go second?

Consider this simple 2-person game I just made up:

Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. However, if he draws all X times, he must keep his last draw as his score.

Player B goes second, and gets to draw up to Y times. Same rules apply to him.

The winner is the player with the highest score. Assuming both A and B play optimally, the probability that player A wins the game is given by F(X,Y). F(X,Y) can be given by the following recurrence relationship (I'll leave it as a separate exercise to derive this):

$F(0,Y) = 0$ $\forall$ Y>0

$F(X,Y) = \left(\frac{Y}{Y+1}\right)*\left(F(X-1,Y)\right)^{\frac{Y}{Y+1}} + \frac{1}{Y+1}$

Here's the question: Find the limit $\lim_{n\rightarrow \infty}$ $F(n,n)$. Obviously, this can be approximated numerically directly from the recurrence definition, but I'm wondering if this limit has an elegant closed-form solution (or perhaps can be derived as a unique root of an implicit equation).

The solution has a nice interpretation to it. Basically, as you let each player have more and more turns, how much does this neutralize B's advantage of getting to go second?

Consider this simple 2-person game I just made up:

Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. However, if he draws all X times, he must keep his last draw as his score.

Player B goes second, and gets to draw up to Y times. Same rules apply to him.

The winner is the player with the highest score. Assuming both A and B play optimally, the probability that player A wins the game is given by F(X,Y). F(X,Y) can be given by the following recurrence relationship (I'll leave it as a separate exercise to derive this):

$F(0,Y) = 0$ $\forall$ Y>0

$F(X,Y) = \left(\frac{Y}{Y+1}\right)*\left(F(X-1,Y)\right)^{\frac{Y+1}{Y}} + \frac{1}{Y+1}$

Here's the question: Find the limit $\lim_{n\rightarrow \infty}$ $F(n,n)$. Obviously, this can be approximated numerically directly from the recurrence definition, but I'm wondering if this limit has an elegant closed-form solution (or perhaps can be derived as a unique root of an implicit equation).

The solution has a nice interpretation to it. Basically, as you let each player have more and more turns, how much does this neutralize B's advantage of getting to go second?

Source Link
bigO6377
bigO6377
  • 211
  • 1
  • 5

Limiting probabilities for two-player game drawing random uniform numbers

Consider this simple 2-person game I just made up:

Player A goes gets to draw a uniform U[0,1] number up to X times. At any time, he may either keep his number, or draw a brand new uniform number. However, if he draws all X times, he must keep his last draw as his score.

Player B goes second, and gets to draw up to Y times. Same rules apply to him.

The winner is the player with the highest score. Assuming both A and B play optimally, the probability that player A wins the game is given by F(X,Y). F(X,Y) can be given by the following recurrence relationship (I'll leave it as a separate exercise to derive this):

$F(0,Y) = 0$ $\forall$ Y>0

$F(X,Y) = \left(\frac{Y}{Y+1}\right)*\left(F(X-1,Y)\right)^{\frac{Y}{Y+1}} + \frac{1}{Y+1}$

Here's the question: Find the limit $\lim_{n\rightarrow \infty}$ $F(n,n)$. Obviously, this can be approximated numerically directly from the recurrence definition, but I'm wondering if this limit has an elegant closed-form solution (or perhaps can be derived as a unique root of an implicit equation).

The solution has a nice interpretation to it. Basically, as you let each player have more and more turns, how much does this neutralize B's advantage of getting to go second?