Hitting $k$ primes by dice rolls

Define $p(-5)=p(-4)=p(-3)=p(-2)=p(-1)=0$, $p(0)=1$ and note that for every $i\geq 1$,

$$p(i)=\frac{1}{6}\sum_{j=1}^{6}p(i-j).$$

Indeed, $S$ hits $i$ if and only if the last number it hits before $i$ is $i-j$ for some $j\in\{1,\ldots,6\}$, and the die rolled after that gives the value $j$. The probability of this event for each specific value of $j$ is $p(i-j)\cdot(1/6)$, providing the equation above. (Note that the definition of the initial values is consistent with this reasoning, as before any dice rolls the initial sum is $0$). Thus, the sequence $(p(i))$ satisfies the homogeneous linear recurrence relation given above. The characteristic polynomial of that is

$$P(z)=z^{6}-\frac{1}{6}(z^{5}+z^{4}+z^{3}+z^{2}+z+1).$$

One of the roots of this polynomial is $z=1$, and its multiplicity is $1$ as the derivative of $P(z)$ does not vanish at $1$. It is also easy to check that the absolute value of each of the other roots $\lambda_{j}$, $2\leq j\leq 6$ of $P(z)$ is at most $1-\mu$ for some absolute positive constant $\mu,\,0<\mu<1$. Therefore, there are constants $c_{j}$ so that

$$p(i)=c_{1}\cdot 1^{i}+\sum_{j=2}^{6}c_{j}\lambda_{j}^{i},$$

implying that

$$|p(i)-c_{1}|\leq C(1-\mu)^{i}$$

for some absolute constant $C$. It remains to compute the value of $c_{1}$. By the last estimate, for any positive $n$,

$$|\sum_{i=1}^{n}p(i)-c_{1}n|\leq C/(1-\mu).$$

Note that the sum $\sum_{i=1}^{n}p(i)$ is the expected number of integers in $[n]=\{1,2,\ldots,n\}$ hit by the sequence $S$.

For each fixed $f$, $d_{1}+d_{2}+\cdots+d_{f}$ is a sum of $f$ independent identically distributed random variables, each uniform on $\left\{1,2,\ldots,6\right\}$. By the standard estimates for the distribution of sums of independent bounded random variables, see., e.g., [2], Theorem A.1.16, this sum is very close to $7f/2$ with high probability. Therefore for large $n$ the expectation considered above is $(1+o(1))(2/7)n$. Dividing by $n$ and taking the limit as $n$ tends to infinity shows that $c_{1}=2/7$, completing the proof. ∎

The probability of the event $\left(S\,\,\,\text{hits}\,\,\,x_{i}\,\,\,\text{iff}\,\,\,\nu_{i}=H\right)$ is a product of $g$ terms. The first term is the probability that $S$ hits $x_{1}$ (if $\nu_{1}=H$) or the probability that $S$ does not hit $x_{1}$ (if $\nu_{1}=N$). Note that since $x_{1}>c\log g$ this probability is $\frac{2}{7}e^{\varepsilon_{1}}$ in the first case and $\frac{5}{7}e^{\varepsilon_{2}}$ in the second case, where both $|\varepsilon_{1}|$ and $|\varepsilon_{2}|$ are at most $1/g$.

The second term in the product is the conditional probability that $S$ hits $x_{2}$ (if $\nu_{2}=H$), or that it does not hit $x_{2}$ (if $\nu_{2}=N$), given the first value it hit in the interval $x_{1},x_{1}+1,\ldots,x_{1}+5$. If $\nu_{1}=H$, this first value is $x_{1}$ itself, and then the probability to hit $x_{2}$ is exactly $p(x_{2}-x_{1})$. If $\nu_{1}=N$, then this first value is one of the $5$ possibilities $x_{1}+j$ for some $1\leq j\leq 5$. Subject to hitting $x_{1}+j$, the conditional probability to hit $x_{2}$ is exactly $p(x_{2}-x_{1}-j)$, which by the assumption on the difference $x_{2}-x_{1}$, is very close to $\frac{2}{7}$. By the law of total probability it follows that in any case the conditional probability to hit $x_{2}$ is $\frac{2}{7}e^{\varepsilon^{\prime}}$ and the conditional probability not to hit it is $\frac{5}{7}e^{\varepsilon"}$ where the absolute value of $\varepsilon^{\prime}$ and of $\varepsilon"$ is at most $1/g$. Continuing in this manner we get a product of $g$ terms, $h$ of which are very close to $2/7$ and $g-h$ are very close to $5/7$, where the product of all error terms $e^{\varepsilon^{\prime\prime\prime}}$ is of the form $e^{\varepsilon}$ for some $|\varepsilon|\leq g\cdot(1/g)=1$. This completes the proof of the lemma. ∎

Split $x_{1},\ldots,x_{n}$ into $c\log(n)$ subsequences, where subsequence number $j$ consists of all $x_{i}$ with index $i\equiv j~{}\mbox{mod}~{}(c\log n)$ where $c$ is the constant from (1). Note that the difference between any two distinct elements in the same subsequences is at least $c\log n$ and that each of these subsequences can contain at most one element smaller than $c\log n$. Each one of the subsequences contains $r:=\frac{n}{c\log(n)}$ elements $x_{i}$. In each subsequence, the probability to deviate in absolute value from $\frac{2}{7}r$ hits by more than $\frac{a}{c\log(n)}$ can be bounded by the Chernoff’s bound for binomial distributions, up to a factor of $e$. Indeed, Lemma 2.2 shows that the contribution of each term does not exceed the contribution of the corresponding term for the binomial random variable with parameters $r$ and $2/7$ by more than a factor of $e$. Note that although each subsequence may contain one element smaller than $c\log n$, the contribution of this single element to the deviation is negligible and can be ignored. Plugging in the standard bound, see, e.g. [2], Theorem A.1.16, we get that the probability of the event considered is at most

$$2e\cdot e^{-c^{\prime}\left(\frac{a}{c\log(n)}\right)^{2}/\left(\frac{n}{c\log(n)}\right)}\leq e^{-c^{\prime\prime}\frac{a^{2}}{n\log(n)}}$$

for appropriate absolute constants $c^{\prime}$, $c^{\prime\prime}$. Here we used the fact that since $a$ is large the constant $2e$ can be swallowed by the choice of $c^{\prime\prime}$. Therefore, the probability to deviate in at least one of the subsequences by more than $a/(c\log n)$ is at most

$$c\log(n)e^{-c^{\prime\prime}\frac{a^{2}}{n\log(n)}}\leq e^{-c^{\prime\prime\prime}\frac{a^{2}}{n\log(n)}},$$

where in the last inequality we used again the fact that $a\geq\sqrt{n}\log(n)$. ∎

(1) The event ${\displaystyle\left\{Y_{m_{1}}\geq k\right\}}$ means that the number of primes that are at most $m_{1}$ and are hit by the infinite sequence of the initial sums of dice rolls is a least $k$. Therefore, if $\frac{2}{7}\pi(m_{1})\leq k-a$, we have

$\displaystyle P\left(Y_{m_{1}}\geq k\right)=P\left(Y_{m_{1}}-\frac{2}{7}\pi(m_{1})\geq k-\frac{2}{7}\pi(m_{1})\right)\leq P\left(\Big{|}Y_{m_{1}}-\frac{2}{7}\pi(m_{1})\Big{|}\geq a\right)\leq e^{-c^{\prime\prime\prime}\frac{a^{2}}{\pi(m_{1})\log(\pi(m_{1}))}},$

where the last inequality follows from Proposition 2.3.

(1) If both events ${\displaystyle\left\{d_{1}+\cdots+d_{i}\geq m_{1}\right\}}$ and ${\displaystyle\left\{Y_{m_{1}}\geq k\right\}}$ do not occur, then the event ${\displaystyle\left\{L_{k}\leq i\right\}}$ does not occur. Therefore, for $\frac{7}{2}i\leq m_{1}-a$ we have

	$\displaystyle P\left(L_{k}\leq i\right)\leq P\left(d_{1}+\cdots+d_{i}\geq m_{1}\right)+P\left(Y_{m_{1}}\geq k\right)\leq P\left(d_{1}+\cdots+d_{i}-\frac{7}{2}i\geq a\right)+P\left(Y_{m_{1}}\geq k\right)$
	$\displaystyle\leq e^{-c^{\prime\prime\prime\prime}\frac{a^{2}}{i}}+e^{-c^{\prime\prime\prime}\frac{k\log^{2}k}{\pi(m_{1})\log(\pi(m_{1}))}},$

where the last inequality follows from Chernoff’s bound and the first part of Corollary 2.4. Note that here $2\sqrt{k}\log k\geq\sqrt{\pi(m_{1})}\log(\pi(m_{1}))$ and therefore the corollary can be applied.

(2) Similarly, if both events ${\displaystyle\left\{d_{1}+\cdots+d_{i}\leq m_{2}\right\}}$ and ${\displaystyle\left\{Y_{m_{2}}\leq k\right\}}$ do not occur, then the event ${\displaystyle\left\{L_{k}>i\right\}}$ does not occur. Therefore, for $\frac{7}{2}i\geq m_{2}+b$, we have

$\displaystyle P\left(L_{k}\geq i\right)\leq P\left(d_{1}+\cdots+d_{i}-\frac{7}{2}i\leq-b\right)+P\left(Y_{m_{2}}\leq k\right)\leq e^{-c^{\prime\prime\prime\prime}\frac{b^{2}}{i}}+e^{-c^{\prime\prime\prime}\frac{a^{2}}{\pi(m_{2})\log(\pi(m_{2}))}},$

where the last inequality follows again from Chernoff’s bound and the second part of Corollary 2.4. Indeed the corollary can be applied since it is not difficult to check that for large $k$ and any $a\geq\sqrt{k}\log^{2}k$,

$$a\geq\sqrt{\pi(m_{2})}\log(\pi(m_{2}))=\sqrt{\lceil\frac{7}{2}(k+a)\rceil}\log(\lceil\frac{7}{2}(k+a)\rceil).$$

∎