Consider the following game. Alice selects an integer $n$ from $[1,b]$, while Bob selects an integer $m$ from $(a,b]$ (for concreteness, you may choose $a=10^{10}$ and $b=10^{1000}$). Alice wins if $m-n$ is a positive prime, Bob wins otherwise. Both players are allowed to use mixed strategies (that is, select their integers at random according to any distribution they want). What is the value of this game? That is, what is the maximal winning probability $p^*$ Alice can achieve, no matter how Bob plays?

My preliminary calculation shows that, for $a$ fixed and $b$ large, $O((\log b)^{-2}) \leq p^* \leq O((\log b)^{-1})$. The problem is to significantly narrow the gap between these estimates.

Update (some details): If Bob selects $m$ uniformly at random from $(a,b]$, then, whatever $n$ Alice selects, her winning probability is at most $\frac{\pi(b-n)}{b-a} \leq \frac{\pi(b)}{b-a}$, where $\pi$ is the prime counting function, which is $O((\log b)^{-1})$ if $a$ fixed and $b$ large.

Next, let Alice select $n$ from $(2,b]$ with probability $q(n)=\frac{\log^2 n-\log^2(n-1)}{\log^2 b-\log^2 2}.$ Then, whatever $m$ Bob selects, Alice wins with probability $\sum\limits_{p\leq m}q(m-p)$, where the summation is over all primes $p$ not exceeding $m$. Because $q$ is non-increasing, $\sum\limits_{p\leq m}q(m-p) \geq \sum\limits_{i=0}^{\pi(m)-1}q(m-i)=\frac{\log^2 m-\log^2(m-\pi(m))}{\log^2 b-\log^2 2} > \frac{\log^2 m-\log^2(m-\pi(m))}{\log^2 b}=\frac{2}{\log^2 b}\int\limits_{m-\pi(m)}^m \frac{\log x}{x}dx > \frac{2}{\log^2 b}\int\limits_{m-\pi(m)}^m \frac{\log m}{m}dx = \frac{2}{\log^2 b}\pi(m) \frac{\log m}{m} > \frac{2}{\log^2 b}.$

  • 1
    $\begingroup$ As a first step, one may consider a simpler game: Alice wins with probability $(\log(m-n))^{-1}$ if $m-n>2$, and $0$ otherwise (that is, replace primes with random set of integers with approximately the same density). What is $p^*$ in this case? $\endgroup$ – Bogdan Feb 7 '18 at 17:50
  • 1
    $\begingroup$ What about negative primes? Does Alice win if, for example, $m-n=-13$? It would also help the reader if you showed your "preliminary calculation", to avoid duplication of effort. $\endgroup$ – Greg Martin Feb 7 '18 at 18:04
  • $\begingroup$ In the randomized version, Alice can pick $1$ and win with probability at least $1/\log(b)$. $\endgroup$ – Julian Rosen Feb 7 '18 at 23:27
  • $\begingroup$ In response to Greg Martin's comment, I have clarified that only positive prime counts, and displayed the calculation. $\endgroup$ – Bogdan Feb 8 '18 at 10:49
  • $\begingroup$ [−1.5,1] in Bounty description should of course be [−1.5,-1]. $\endgroup$ – Bogdan Feb 12 '18 at 10:04

Your Answer

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.