Discontinuities in the expectation of a stopping time (Bayesian coin-tossing)

Question

Suppose a coin is either Unbiased ($P(\text{Head})=1/2$), or Biased with $P(\text{Head})=b\ne{1\over 2}$, where $b$ is a known value. To decide between Unbiased vs. Biased --assumed equally likely a priori-- we toss the coin until one alternative has a posterior probability at least $9$ times that of the other, deciding in favor of the more probable one.

Let $N$ be the number of tosses needed to reach a decision, and consider the expectation $EN(b)$ as a function of $b.$ (We can focus on $b\in(0,{1\over 2})$, since the function is symmetric about $b={1\over 2}$.) Here's a plot of Monte Carlo simulation results, with simulation errors less than the width of the "dots":

The above plot seems unremarkable, but closer inspection suggests that $EN(b)$ is neither monotonic nor continuous on $(0,{1\over 2})$. In the following plots, the very-light-grey lines give 3-sigma error bounds that vary with sample size from plot-to-plot:

These images show, row-wise from the top, apparent "jump discontinuities" at $b\approx 0.05054567564, 0.1339745962, 0.1666666666,$ and $0.28867513459.$ (The first is an instance of what seems to be a negative jump, where $EN(b)$ surprisingly decreases.)

Numerically, we notice -- and it seems intuitively clear -- that the jumps occur at the "threshold" values of polynomials appearing in the definition of $N$ (see the formulation below): $$N:=\inf\left\{n\ge 1:\ 2^nb^{S_n}(1-b)^{n-S_n}\not\in\left({1\over 9},\,9\right)\right\}.$$

Thus, for threshold value $t\in\{{1\over 9},9\}$, the set of candidate discontinuities is simply $$D_{t}:=\left\{b\in\left(0,{1\over 2}\right): 2^{n}\,b^s\,(1-b)^{n-s}=t,\ n\in\mathbb{Z^+},s\in\{0,\ldots,n\}\right\},$$ and indeed all of the apparent discontinuities that I've so far checked do seem to fall in the set $D_{1\over 9}\cup D_{9};\ $ e.g., the jumps in the top two plots above are at the points in $D_{9}$ with $(s,n)=(1,8)$ and $(0,4)$, respectively, and the bottom two plots are at the points in $D_{1\over 9}$ with $(s,n)=(2,2)$ and $(4,4)$, respectively.

Question #1: How to prove that $EN(b)$ is discontinuous at every $b\in D_{1\over 9}\cup D_{9}?$ Can a formula be found to estimate the size and/or direction of the jump?

Question #2: Is it the case that every nonempty open interval $I\subseteq(0,{1\over 2})$ contains an element of $D_{1\over 9}\cup D_{9}?$

Question #3: Presumably, for any $b\in(0,{1\over 2})$ there is a well-defined proportion of the value $EN(b)$ that's due purely to jump discontinuities at points $b'\in(0,b]$. What can be said about this quantity as $b\to{1\over 2}?$ (Asymptotically, can a nonzero proportion of the growth be attributed purely to "jumps"?)

---

Formulation: For $n=1,2,3,\ldots,$ $$\begin{align}(X_1,\ldots X_n)\mid p &\sim \text{i.i.d. Bernoulli($p$),}\\[3mm] p &\sim\text{Uniform$\left(\left\{{1\over 2},\,b\right\}\right)$},\end{align}$$ where $b\ne{1\over 2}.$ Given $(X_1,\ldots,X_n),$ we have the posterior odds for $\ p=b\ $ vs. $\ p={1\over 2}\ $ as follows (because of the uniform prior, this is the same as the Bayes factor, or likelihood ratio): $$R_n:={P(p=b\mid X_1,\ldots,X_n)\over P(p={1\over 2}\mid X_1,\ldots,X_n)}={P(p=b\mid X_1,\ldots,X_n)\over P(p={1\over 2}\mid X_1,\ldots,X_n)}=2^nb^{S_n}(1-b)^{n-S_n},\quad S_n=\sum_{i=1}^nX_i.$$ The number of tosses required to make a decision is then $$N:=\inf\left\{n\ge 1:\ R_n\not\in\left({1\over 9},\,9\right)\right\}.$$ Since the distribution of $R_n$ is invariant under $b\mapsto 1-b$, the function $EN(b)$ is symmetric about $b={1\over 2}$; hence, WLOG we can take $b\lt {1\over 2}.$

Answer 1

(I eventually worked out this answer to Question #1 only -- it doesn't address Questions #2 & #3.)

Following is a sketch of proof that $EN(b)$ has the countably infinite set of jump discontinuities described in the question:

• To study the behavior of $EN(b)$, we first linearize the problem by defining $Z_n:=\log R_n$:
  • For $x=(x_1..x_n)\in\{0,1\}^*$ (i.e. any finite binary sequence), and $b\in(0,1/2),$ define $$z(x,b) = \left(\sum_{i=1}^nx_i\right)\cdot\ell_1(b) + \left(n-\sum_{i=1}^nx_i\right)\cdot\ell_0(b),$$ where $\ell_1(b)=\log(2b),\ \ell_0(b)=\log(2(1-b)).$
  • Now $Z_n =z((X_1..X_n),b)$ is a type of random walk (with dependent increments -- because the $X_i$ are not independent) on the set $\{s\,\ell_1+(n-s)\,\ell_0:s\in\{0,...,n\},n\in\{1,2,...\}\}$.
  • The stopping time is now $N=\min\{n\ge 1:Z_n\not\in C\}$, where the interval $C:=(-c,c):=(-\log 9, \log 9).$
• Analysis of $E[N]$ is simplified when Wald's equation $\big(E[Z_N]=E[N]\,E[Z_1]\big)$ applies, but simulations show that it does not apply directly to $Z_N$ (presumably related to the fact that the $X_i$ are not independent); however, the $X_i$ are conditionally independent given $p$, and the conditions for Wald's lemma are then found to be satisfied, hence: $$EN = E\,E[N\mid p] = {1\over 2}E[N\mid p=1/2] + {1\over 2}E[N\mid p=b]= {1\over 2}\left({E[Z_N\mid p=1/2]\over E[Z_1\mid p=1/2]} + {E[Z_N\mid p=b]\over E[Z_1\mid p=b]} \right)\tag{1}$$
  • The denominators in (1) are given by $$E[Z_1\mid p]=p\,\ell_1(b)+(1-p)\,\ell_0(b)$$ which, for each $p$, is a continuous nonvanishing function of $b\in(0,1/2);$ consequently, any discontinuous behaviour of $EN(b)$ must arise from that of the numerators. Thus, $EN(b)$ has a jump discontinuity at $b$ iff $$\Delta EN(b):=\lim_{\epsilon\downarrow 0}\big( EN(b+\epsilon)-EN(b-\epsilon) \big)={1\over 2}\left({\Delta E[Z_N\mid p=1/2](b)\over E[Z_1\mid p=1/2](b)} + {\Delta E[Z_N\mid p=b](b)\over E[Z_1\mid p=b](b)} \right)\tag{2}\ne 0.$$
• Define a stopping sequence to be any $x\in\{0,1\}^*$ such that both (i) $z(x,b)\not\in C$, and (ii) $z(x',b)\in C$ for every proper prefix $x'$ of $x$. Denote by $\mathcal X$ the set of all stopping sequences.
• $E[Z_N\mid p]$ is a sum over all stopping sequences $x$: $$E[Z_N\mid p]=\sum_{x\in\mathcal X}z(x,b)\,P\pmb[X=x\mid p\pmb],\\ \quad\text{where }P\pmb[(X_1..X_n)=(x_1..x_n)\mid p\pmb]=p^{\sum_{i=1}^nx_i}(1-p)^{n-\sum_{i=1}^nx_i}.\tag{3}$$
• With $\sigma\in\{-1,+1\}$ as a sign indicator, denote by $\mathcal X_{\sigma\cdot c}(b)$ the set of stopping sequences for which $Z_N=\sigma\cdot c$, i.e. $\mathcal X_{\sigma\cdot c}(b):=\{x\in\mathcal X: z(x,b)=\sigma\cdot c\}.$
  • For any fixed $x$, $z(x,\cdot)$ is a concave function of $b$, with a maximum at $b = \bar{x}$, where $\overline {x_1..x_n}:=(x_1+...+x_n)/n.$ Thus, $z(x,\cdot)$ is increasing for $b<\bar{x}$ and decreasing for $b>\bar{x}$.
  • Therefore, if $x^*,b^*$ are such that $x^*\in\mathcal X_{\sigma\cdot c}(b^*)$ (i.e. $z(x^*,b^*)=\sigma\cdot c$), there will be three cases to consider for each choice of sign -- the entries in the following table show which conditions hold (for sufficiently small $\epsilon>0$) for the stated row- and column-conditions: $$\begin{array}{c|c|c|} & x^*\in\mathcal X_c(b^*) & x^*\in\mathcal X_{-c}(b^*) \\ \hline b^*<\overline{x^*} & x^*\not\in\mathcal X_c(b^*-\epsilon),\ \ x^*\in\mathcal X_c(b^*+\epsilon) & x^*\in\mathcal X_{-c}(b^*-\epsilon),\ \ x^*\not\in\mathcal X_{-c}(b^*+\epsilon) \\ \hline b^*=\overline{x^*} & x^*\not\in\mathcal X_c(b^*-\epsilon),\ \ x^*\not\in\mathcal X_c(b^*+\epsilon) & x^*\in\mathcal X_{-c}(b^*-\epsilon),\ \ x^*\in\mathcal X_{-c}(b^*+\epsilon) \\ \hline b^*>\overline{x^*} & x^*\in\mathcal X_c(b^*-\epsilon),\ \ x^*\not\in\mathcal X_c(b^*+\epsilon) & x^*\not\in\mathcal X_{-c}(b^*-\epsilon),\ \ x^*\in\mathcal X_{-c}(b^*+\epsilon) \\ \hline \end{array}$$ NB: If $z(x^*,b^*)=\pm c$ then $b^*\ne\overline{x^*}$, so there are really only the first and last rows in the above table. (For proof, specific to our $c:=\log 9$, see this MSE posting.)
  • Thus for sufficiently small $\epsilon$ -- except when (if ever) $b^*=\overline{x^*}$ -- it must happen that $x^*$, which is a stopping sequence when $b=b^*$, remains a stopping sequence for one case $(\pm)$ of $b^*\pm\epsilon$ but not the other. Consequently, the net effect of this upon $E[Z_N\mid p]$ is given by the following formula, which includes three different sign-change dependencies: $$\begin{align}&\Delta E[Z_N\mid p](b^*) \\ :&=\lim_{\epsilon\downarrow 0}\big(E[Z_N\mid p](b^*+\epsilon) - E[Z_N\mid p](b^*-\epsilon)\big)\\ &= \sigma\cdot(+1\text{ if }b^*<\overline{x^*}\text{ else }-1)\cdot(+1\text{ if }p=1/2\text{ else }-1 )\\ &\ \ \cdot\left(c\,|\mathcal X_{\sigma\cdot c}(b^*)|\,P[X=x^*\mid p]_{b^*} - \sum_{x^*x'\in\mathcal X(b^*)\\ x^*\in\mathcal X_{\sigma\cdot c}(b^*)}z(x^*x',b^*)\,P[X=x^*x'\mid p]_{b^*}\right)\tag{4}\end{align}$$ where the indicated probabilities are given by the formula in (3) evaluated for $b=b^*,$ and the notation $x^*x'$ denotes the sequence formed by appending $x'$ to $x^*.$
• Substituting (4) into (2) gives the jump at each point of discontinuity in $EN(b)$, these points being located at those $b^*$ for which there exist $x^*\in\mathcal X_{\sigma\cdot c}(b^*)$ for a $\sigma\in\{-1,+1\}$, i.e. such that $z(x^*,b^*)=\sigma\cdot c$ (precisely the jump locations given by the set $D_{1/9}\cup D_{9}$ described in the question).
  • Note that $z(x,b)$ depends on $x=(x_1..x_n)$ only via the quantities $n:=\text{length}(x)$ and $s:=\sum_{i=1}^nx_i.$ Thus, the stopping sequences in $\mathcal X_{\sigma\cdot c}(b^*)$ all have the same values for these quantities.