Chapter 9

Suppose \(A\) is a probabilistic algorithm that halts with probability 1 on input \(x,\) and let \(\mathrm{P}: \Omega \rightarrow[0,1]\) be the corresponding probability distribution. Let \(\lambda\) be an execution path of length \(\ell,\) and assume that no proper prefix of \(\lambda\) is exact. Let \(\mathcal{E}_{\lambda}:=\\{\omega \in \Omega: \omega\) extends \(\lambda\\} .\) Show that \(\mathrm{P}\left[\mathcal{E}_{\lambda}\right]=2^{-\ell}\).

Let \(A\) be a probabilistic algorithm that on a given input \(x,\) halts with probability \(1,\) and produces an output in the set \(T\). Let \(\mathrm{P}\) be the corresponding probability distribution, and let \(Y\) and \(Z\) be random variables representing the output and running time, respectively. For each \(k \geq 0,\) let \(\mathrm{P}_{k}\) be the uniform distribution on all execution paths \(\lambda\) of length \(k\). We define random variables \(Y_{k}\) and \(Z_{k},\) associated with \(\mathrm{P}_{k},\) as follows: if \(\lambda\) is complete, we define \(Y_{k}(\lambda)\) to be the output produced by \(A,\) and \(Z_{k}(\lambda)\) to be the actual number of steps executed by \(A\); otherwise, we define \(Y_{k}(\lambda)\) to be the special value " \(\perp\) " and \(Z_{k}(\lambda)\) to be \(k\). For each \(t \in T,\) let \(p_{t k}\) be the probability (relative to \(\mathrm{P}_{k}\) ) that \(Y_{k}=t,\) and let \(\mu_{k}\) be the expected value (relative to \(\mathrm{P}_{k}\) ) of \(Z_{k}\). Show that: (a) for each \(t \in T, \mathrm{P}[Y=t]=\lim _{k \rightarrow \infty} p_{t k}\).

Let \(A_{1}\) and \(A_{2}\) be probabilistic algorithms. Let \(B\) be any probabilistic algorithm that always outputs 0 or \(1 .\) For \(i=1,2,\) let \(A_{i}^{\prime}\) be the algorithm that on input \(x\) computes and outputs \(B\left(A_{i}(x)\right) .\) Fix an input \(x,\) and let \(Y_{1}\) and \(Y_{2}\) be random variables representing the outputs of \(A_{1}\) and \(A_{2},\) respectively, on input \(x,\) and let \(Y_{1}^{\prime}\) and \(Y_{2}^{\prime}\) be random variables representing the outputs of \(A_{1}^{\prime}\) and \(A_{2}^{\prime}\), respectively, on input \(x .\) Assume that the images of \(Y_{1}\) and \(Y_{2}\) are finite, and let \(\delta:=\Delta\left[Y_{1} ; Y_{2}\right]\) be their statistical distance. Show that \(\left|\mathrm{P}\left[Y_{1}^{\prime}=1\right]-\mathrm{P}\left[Y_{2}^{\prime}=1\right]\right| \leq \delta\).

Prove that if \(m\) is not a power of \(2,\) there is no probabilistic algorithm whose running time is strictly bounded and whose output distribution is uniform on \(\\{0, \ldots, m-1\\}\).

You are to design and analyze an efficient probabilistic algorithm \(B\) that takes as input two integers \(n\) and \(y,\) with \(n>0\) and \(0 \leq y \leq n,\) and always outputs 0 or 1 . Your algorithm should satisfy the following property. Suppose \(A\) is a probabilistic algorithm that takes two inputs, \(n\) and \(x,\) and always outputs an integer between 0 and \(n\). Let \(Y\) be a random variable representing \(A\) 's output on input \(n, x\). Then for all inputs \(n, x,\) we should have \(\mathrm{P}[\boldsymbol{B}(n, A(n, x))\) outputs 1\(]=\mathrm{E}[Y] / n\).

Design and analyze an efficient probabilistic algorithm that takes as input an integer \(n \geq 2,\) and outputs a random element of \(\mathbb{Z}_{n}^{*}\).

Consider the following probabilistic algorithm that takes as input a positive integer \(m\) : $$ S \leftarrow \emptyset$$ repeat $$\begin{array}{l} n \stackrel{\varnothing}{\leftarrow}\\{1, \ldots, m\\}, S \leftarrow S \cup\\{n\\} \\ \text { until }|S|=m \end{array}$$ Show that the expected number of iterations of the main loop is \(\sim m \log m .\)

Consider the following algorithm (which takes no input): \(j \leftarrow 1\) repeat $$\begin{aligned} j & \leftarrow j+1, n \stackrel{\phi}{\leftarrow}\\{0, \ldots, j-1\\} \\ \text { until } n &=0 \end{aligned}$$ Show that the expected running time of this algorithm is infinite (even though it does halt with probability 1 ).

Consider again Algorithm RN in \(\S\) 9.2. On input \(m,\) this algorithm may use up to \(\approx 2 \ell\) random bits on average, where \(\ell:=\left\lceil\log _{2} m\right\rceil .\) Indeed, each loop iteration generates \(\ell\) random bits, and the expected number of loop iterations will be \(\approx 2\) when \(m \approx 2^{\ell-1} .\) This exercise asks you to analyze an alternative algorithm that uses just \(\ell+O(1)\) random bits on average, which may be useful in settings where random bits are a scarce resource. This algorithm runs as follows:

Suppose Algorithm RP is implemented using an imperfect random number generator, so that the statistical distance between the output distribution of the random number generator and the uniform distribution on \(\\{2, \ldots, m\\}\) is equal to \(\delta\) (e.g., Algorithm \(\mathrm{RN}^{\prime}\) in \(\S\) 9.2). Assume that \(2 \delta<\pi(m) /(m-1)\). Also, let \(\mu\) denote the expected number of iterations of the main loop of Algorithm \(\mathrm{RP}\), let \(\Delta\) denote the statistical distance between its output distribution and the uniform distribution on the primes up to \(m,\) and let \(\ell:=\operatorname{len}(m)\). (a) Assuming the primality test is deterministic, show that \(\mu=O(\ell)\) and \(\Delta=O(\delta \ell)\) (b) Assuming the primality test is probabilistic, with one-sided error \(\varepsilon,\) as in \(\S 9.4 .1,\) show that \(\mu=O(\ell)\) and \(\Delta=O((\delta+\varepsilon) \ell) .\)

Show that every language recognized by a Las Vegas algorithm is also recognized by a Monte Carlo algorithm, and that every language recognized by a Monte Carlo algorithm is also recognized by an Atlantic City algorithm.

Show that if \(L\) is recognized by an Atlantic City algorithm that runs in expected polynomial time, then it is recognized by an Atlantic City algorithm that runs in strict polynomial time, and whose error probability is at most \(2^{-n}\) on inputs of size \(n\).

Show that a language is recognized by a Las Vegas algorithm if and only if the language and its complement are recognized by Monte Carlo algorithms.

Suppose that for a given language \(L,\) there exists a probabilistic algorithm \(A\) that runs in expected polynomial time, and always outputs either 0 or 1\. Further suppose that for some constants \(\alpha\) and \(c,\) where \- \(\alpha\) is a rational number with \(0 \leq \alpha<1,\) and \- \(c\) is a positive integer, and for all sufficiently large \(n,\) and all inputs \(x\) of size \(n,\) we have \- if \(x \notin L,\) then \(\mathrm{P}[A(x)\) outputs 1\(] \leq \alpha,\) and \- if \(x \in L,\) then \(\mathrm{P}[A(x)\) outputs 1\(] \geq \alpha+1 / n^{c}\) (a) Show that there exists an Atlantic City algorithm for \(L\). (b) Show that if \(\alpha=0,\) then there exists a Monte Carlo algorithm for \(L\).