Suppose you are playing a game which contains $N$ rounds ($N$ is large enough). At each round you pick one from $K$ different strategies. The probability you win at a round depends on the strategy you pick and the number of rounds you have already taken. Denote the probability you win at $n$th round by picking $k$th strategy as $P_n(k), k = 1 ... K, n = 1 ... N$. The probability satisfies the following conditions:

  1. $P_{n_1}(k_1)$ and $P_{n_2}(k_2)$ are independent when $k_1 \neq k_2$.
  2. $|P_n(k) - P_{n+1}(k)| < \delta$. $\delta$ is known and small. Let's say $\delta = 0.01$.
  3. $P_n(k)$ is independent to all the previous strategies you take at $1 ... n - 1$ th round.

Now suppose you don't know the values of $P_n(k)$. How do you pick strategies to maximize the total number of rounds you win?

New contributor
Hao Jiang is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $\begingroup$ In this form your problem is unsolvable, its much too general. As an example, since $N$ shall be large assumption 2. can be fulfilled if f.i. $P_n(k) = 0$ for $n \leq 900$ and $P_n(k) = 1$ for $n \geq 1000$. And then, what is the meaning of 1. and 3.? I don't know independent probabilities. Maybe you mean independent realisations at each stage. $\endgroup$ – Dieter Kadelka 2 days ago
  • 1
    $\begingroup$ I understand what 3) means, though it's already implicit in the notation. 1) is incomprehensible. The question basically comes down to: "What's my optimal strategy in a game where I don't know the payoffs?" Whatever the answer, can you really expect it to still be optimal if all $P_n(k)$ are replaced with $1-P_n(k)$ ? $\endgroup$ – Steven Landsburg 2 days ago

Your Answer

Hao Jiang is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.