This is a homework problem and I am not asking for a solution. Rather, I've been stuck for many hours and the professor has been no help. So
Consider the decision problem of whether a given positive integer is a prime or not. Suppose that we have our own algorithm that makes a decision at random and returns the correct answer with probability 1/2 + $\delta$, for some $\delta \in (0, 1/2)$, which is a bit better than a random guess. We run the algorithm 9 times independently and use the majority vote to make a decision.
(1) Construct a sample space and a probability law for our experiment. (2) Assume that a prime is chosen at random from a different machine with probability q, and $\delta$ depends on q by $\delta = q^2$. Find the probability that the experiment returns a correct answer.
I'm stuck with just the choices in modeling. The first guess was oh just model the decision $D$ with $D = \begin{cases} 1 \text{ if } X \geq 5\\ 0 \text{ otherwise}\end{cases}$, granted $X\sim Binom \left(9,\frac{1}{2}+\delta\right)$ (the amount of correct guesses in 9 trials with given probability). So then our sample space is $\Omega = \{$Majority Vote Prime=1, Majority Vote Not Prime=0$ \}$. And the probability law might be $\mathbb{P}(Correct)=\sum_{n=5}^9 \binom{9}{n}(\frac{1}{2}+\delta)^n(\frac{1}{2}-\delta)^{9-n}$, which I am sure is not the best decision. I saw some stuff here but its not helping: Boosting randomized algorithms with Hoeffding's inequality.
But then I started thinking, there seem to be 4 cases {(the number is prime, guess prime), (number is prime, guess not prime), (the number is not prime, guess prime), (the number is not prime, guess not prime)} = $\{(p,g_p),(p, g_{\not p}),(\not p, g_p),(\not p, g_{\not p})\}$ where I'm seeking to formulate a probability law $\mathbb{P}(\text{Correct Guess by Majority Vote}) = \mathbb{P}(\{(\not p, g_{\not p}),(p,g_p)\})$ where $g_p$ and $g_{\not p}$ are the majority vote (0 or 1), so a Bernoulli random variable, presumably conditioned on the 9 trials (so conditioned on a binomial random variable).
I just really don't know where to go from here, I feel I'm at an impass I really just want to understand why my intuition seems to be missing the mark here. Do I setup a conditional probability to find the probability of a correct answer?
I'm guessing the second part is to set up a conditional probability now that we know $q$ is from a random process, so like $\mathbb{P}(D = correct \vert Y = 1/2 + q^2), q \in \left(0,\frac{1}{\sqrt{2}}\right)$for a random variable $Y$ that is a linear transformation of the randomly given prime with probability $q$. I dont understand how to incorporate this new dependence on $q$ as a random variable so again some hint or chapter of some book I can read to learn more about this whole process would be a help. I'm a struggling math undergrad if it helps. A hint, a definition, a name for this whole modeling process you can turn me to for further study would be appreciated. Full answers are not sought. I'm just really interested in why this is so hard for me to figure out...