## Introduction

**RandFunc1**and

**RandFunc2**

## The Frequentist's Approach

A frequentist, knowing nothing about Bayesianism, would naturally following the Maximum Likelihood approach. The distinguisher would be assumed to make decisions and output the hypothesis with larger likelihood.

**RandRunc1**is \begin{equation} p_1 = \binom{q}{k}{(\frac{1}{m})^k(1-\frac{1}{m})^{q-k}} \end{equation} and the likelihood of \textbf{RandFunc2} is \begin{equation} p_2 = \binom{q}{k}{(\frac{1}{m^2})^{k}(1-\frac{1}{m^2})^{q-k}} \end{equation} where there are $k$ 0s in the observations. The distinguisher outputs 1 if and only if $p_1 > p_2$. Let the support involved in such event be $S$. \begin{equation} \Delta_D = \Pr[D = 1 | RandFunc1] - \Pr[D=1 | RandFunc2] = \sum\limits_{s \in S}{p_1(s)}-\sum\limits_{s \in S}{p_2(s)} \end{equation} This is exactly the statistical distance between the two distributions. Therefore, \begin{equation} \Delta_D = \sum\limits_{s \in S}\binom{q}{k}{(\frac{1}{m})^k(1-\frac{1}{m})^{q-k}}-\binom{k}{q}{(\frac{1}{m^2})^{k}(1-\frac{1}{m^2})^{q-k}} \end{equation} which is equal to \begin{equation} \Delta_D = \sum\limits_{s \in S}\binom{q}{k}{(\frac{1}{m})^{k} (1-\frac{1}{m})^{q-k}(1-(\frac{1}{m})^k (1+\frac{1}{m})^{q-k})} \end{equation} Clearly $(\frac{1}{m})^k (1+\frac{1}{m})^{q-k}$ is a monodically decreasing function with respect to $k$. So \begin{equation} \Delta_D = \sum\limits_{k=1}^{q}\binom{q}{k}{(\frac{1}{m})^{k} (1-\frac{1}{m})^{q-k}|1-(\frac{1}{m})^k (1+\frac{1}{m})^{q-k}|} \end{equation} \begin{equation} \Delta_D \leq \sum\limits_{k=1}^{q}\binom{q}{k}{(\frac{1}{m})^{k} (1-\frac{1}{m})^{q-k}} = 1-(1-\frac{1}{m})^{q} \end{equation} This is bounded by $\Delta_D \leq \frac{q}{m}$ according to Bernoulli's Inequality. Therefore at least $q = \Omega(m)$ queries are needed to have advantage $\Omega(1)$. We now show that such number of queries are \textbf{sufficient} to have advantage $\Omega(1)$. We can in principle compute the support $S$ explicitly. Consider the inequality \begin{equation} 1-\binom{q}{k}(\frac{1}{m})^{k}(1+\frac{1}{m})^{q-k} \geq 0 \end{equation} We have \begin{equation} k \geq k_0 = \frac{q \ln(1+\frac{1}{m})}{\ln(1+\frac{1}{m})+\ln(m)} \approx \frac{q}{m \ln(m)} \end{equation} This implies that \begin{equation} \Delta_D \geq (1-\frac{1}{m^2})^{q}-(1-\frac{1}{m})^{q} \approx \frac{q}{m}-\frac{q}{m^2} \end{equation} This implies that queries unto $\Theta(\frac{m^2}{m-1}) = \Theta(m)$ is sufficient for advantage $\Theta(1)$.

## The Bayesianist's Approach

**"posterior distribution"**of each hypothesis based on the observations $Q$. More specifically, the distinguisher's belief of which RandFunc physically exists can be computed by the Bayes theorem: \begin{equation} \Pr[randfunc = RandFunc1 | Q] = \frac{P_1\Pr[Q | RandFunc1]}{P_1\Pr[Q | RandFunc1]+P_2\Pr[Q | RandFunc2]} \end{equation} where $P_1, P_2$ is the prior belief of each function to be present. Suppose we formalize the observations by $Q = (r_1,r_2,...,r_k)$ where $r_i \in \{0,1\}$. The response of some query $r_i = 0$ if and only if the string generated is $00...0$. Therefore, for RandFunc1, $\Pr[r_i = 0] = \frac{1}{m}$ and for RandFunc2 $\Pr[r_i = 0] = \frac{1}{m^2}$. Therefore the Bayes rule reduces to \begin{equation} \Pr[randfunc = RandFunc1 | Q] = \frac{P_1 \frac{1}{m}^u (1-\frac{1}{m})^{k-u}}{P_1 \frac{1}{m}^u (1-\frac{1}{m})^{k-u}+P_2\frac{1}{m^2}^u (1-\frac{1}{m^2})^{k-u}} \end{equation} if there are u $00...0$ in the responses. Therefore, the probability that the distinguisher outputs $1$ is marginalised over all possible function responses for $k$ queries. \begin{equation} \Delta_D = \sum\limits_{u = 0}^{k}{\binom{k}{u} (\frac{1}{m}^u (1-\frac{1}{m})^{k-u}-\frac{1}{m^2}^u (1-\frac{1}{m^2})^{k-u})\frac{P_1 \frac{1}{m}^u (1-\frac{1}{m})^{k-u}}{P_1 \frac{1}{m}^u (1-\frac{1}{m})^{k-u}+P_2\frac{1}{m^2}^u (1-\frac{1}{m^2})^{k-u}}} \end{equation}