How to define a rejection region? This has always troubled me a bit. When I choose my hypothesis, do I define in some way the rejection region [RR], or, do I do that by choosing the test statistic I want to use?
By fixing the significance level, I'm in a way determining the area/volume of the RR.
In two different contexts(different null hypothesis), I've seen the same statistic being used with two different RR. In some books, the authors give the sense that once we decide the hypothesis, we've chosen the RR. Others, state explicitly that at least in some hypothesis, the RR is not completely defined, and we need other criteria... I would like to structure this as best as possible.
Any help would be appreciated
 A: @fcop's answer talks about the choice of a region such that the power is maximized. In this illustration, I want to point out that even when we have tests that are considered "the most powerful tests" (so, the power isn't an issue here), the rejection region depends on more than just the hypothesis.
I'll use the definition from the Neyman-Pearson Lemma to test $H_0: \theta = \theta_0$ vs. $H_1:\theta=\theta_1$. As pointed out by @fcop, this Lemma holds only in the case of simple hypothesis. However, my purpose is to provide examples to illustrate my point, so my answer is bounded to have a narrower scope.
From the Wikipedia article:
"(...) the likelihood-ratio test which rejects $H_0$ in favour of $H_1$ when
$$\frac {L(x\mid \theta _{0})}{L(x\mid \theta _{1})} \leq \eta$$
where
$$P(\Lambda (X)\leq \eta \mid H_{0})=\alpha$$
is the most powerful test at significance level $\alpha$ for a threshold $\eta$."
And in the proof of this lemma, we can see how the rejection region is defined for this specific case:
"Define the rejection region of the null hypothesis for the NP test as
$R_{NP}=\left\{x:{\frac {L(x\mid \theta _{0})}{L(x\mid \theta _{1})}}\leq \eta \right\}$ 
where $\eta$  is chosen so that $P(R_{{NP}},\theta _{0})=\alpha \,.$"

Example 1
Now, suppose we have that $X_1,\ldots,X_n \overset{iid}{\sim} \mathcal{N}(\theta,1)$, and we want to test $H_0: \theta = 3$ vs. $H_1:\theta=5$.
So,
$$L(\mathbf{x} \mid \theta) = (2 \pi)^{-n/2} \exp \left\{-\frac{(\sum x_i - \theta)^2}{2} \right\} = (2 \pi)^{-n/2} \exp \left\{-\frac{(\sum x_i - \bar{x})^2 -n(\bar{x}-\theta)^2}{2} \right\}$$
And, calculating $\frac {L(\mathbf{x} \mid \theta _{0})}{L(\mathbf{x}\mid \theta _{1})}$ yields
\begin{align}
\frac {L(\mathbf{x} \mid \theta _{0})}{L(\mathbf{x}\mid \theta _{1})} 
= \frac {L(\mathbf{x} \mid 3)}{L(\mathbf{x}\mid 5)} 
&= \frac{(2 \pi)^{-n/2} \exp \left\{-\frac{(\sum x_i - \bar{x})^2 -n(\bar{x}-3)^2}{2} \right\}}{(2 \pi)^{-n/2} \exp \left\{-\frac{(\sum x_i - \bar{x})^2 -n(\bar{x}-5)^2}{2} \right\}} \\
&= \exp\left\{- n(\bar{x}-3)^2 +n(\bar{x}-5)^2 \right\} \\
&= \exp\left\{ -n(4 \bar{x}-16)\right\}
\end{align}
Therefore, the rejection region is defined in terms of
\begin{align}
\frac {L(\mathbf{x} \mid \theta _{0})}{L(\mathbf{x}\mid \theta _{1})} = \exp\left\{ -n(4 \bar{x}-16)\right\} \leq \eta
\end{align}
Simplifying it, we have that
\begin{align}
\exp \left\{ -n(4 \bar{x}-16)\right\} \leq \eta &\iff -n(4 \bar{x}-16) \leq \log(\eta) \\
&\iff \bar{x} \geq \underbrace{4 - \frac{\log(\eta)}{4 n}}_{\mbox{call this }\eta^{*}} \\ \\
&\iff \bar{x} \geq \eta^{*}
\end{align}
So now we can define our rejection region in terms of the statistic $\bar{X}$:
$$R_{NP}=\left\{x:\bar{x} \geq \eta^{*} \right\}$$
where $\eta$  is chosen so that $P(\bar{X} \geq \eta^{*} \, | \theta_0)=\alpha.$
Now, under $H_0$ (or given $\theta_0=3$) we know that $\bar{X} \sim \mathcal{N}(3,1/n)$, to the above probability becomes:
\begin{align}
\alpha &= P(\bar{X} \geq \eta^{*} \, | \theta_0) \\
&= P \left(\frac{\bar{X}-3}{1\ \sqrt{n}} \geq \frac{\eta^{*}-3}{1\ \sqrt{n}}\right) \\
&= P \left(Z \geq \frac{\eta^{*}-3}{1\ \sqrt{n}}\right) \, \mbox{where } Z\sim \mathcal{N}(0,1)\\
\end{align}
Therefore, $\eta^{*} = \frac{z_{1-\alpha/2}}{\sqrt{n}}+3$, and we 
$$\mbox{reject } H_0 \mbox{ iff } \bar{X} \geq \frac{z_{1-\alpha/2}}{\sqrt{n}}+3$$
So, in this case our rejection region depends on our test statistic ($\bar{X}$), the distribution associated to it (represented by $z_{1-\alpha/2}$, where $z$ is the critical value for a standard Normal), the sample size (n), and the value of our null hypothesis ($\theta=3$).

Example 2
Now, suppose we have the same setting from Example 1, but now $H_0: \theta = 4$ v.s. $H_1: \theta = 5$.
Using the same argument as above, we can see that $\eta^{*} = \frac{z_{1-\alpha/2}}{\sqrt{n}}+4$, and we 
$$\mbox{reject } H_0 \mbox{ iff } \bar{X} \geq \frac{z_{1-\alpha/2}}{\sqrt{n}}+4$$
We changed the value of our null hypothesis, but everything else remained the same. The same way, our rejection region depends on our test statistic ($\bar{X}$), the distribution associated to it (represented by $z_{1-\alpha/2}$, where $z$ is the critical value for a standard Normal), the sample size (n), and the value of our null hypothesis ($\theta=4$).

Example 3
Suppose now that $X_1,\ldots,X_n \overset{iid}{\sim} \mbox{Exp}(\theta)$, and we wish to test the hypothesis $H_0: \theta = 3$ vs. $H_1:\theta=5$.
As pointed out by @Scortchi, this hypothesis is not the same as the previous one because on our first example we devised a test for the mean of our normal distribution, and now we are testing a value for the rate of our exponential distribution.
Using the same argument, one can show that we reject $H_0$ iff $\bar{X} \leq \eta^{*}$, where 
$\eta^{*}$ is such that (under $H_0$)
$$P(\bar{X} < \eta^{*})=\alpha, \, \, \mbox{with} \,\, \bar{X} \sim \mbox{Gamma}(n,3n)$$
In this case our rejection region depends on our test statistic ($\bar{X}$), the distribution associated to it (Gamma, in this case), the sample size (n), and the value of our null hypothesis ($\theta=3$).
A: For an explanation of the concept of power I refer to What follows if we fail to reject the null hypothesis?. 
Assume the we want to test a one-sided hypothesis about the mean of a normal population, using a sample $x_1, x_2, \dots x_n$ and for simplicity assume that the standard deviation $\sigma$ is known, so we want to test $H_0: \mu \le \mu_0$ versus $H_1: \mu > \mu_0$. We choose a significance level $\alpha$.  
The test statistic is $\bar{x}=\frac{1}{n}\sum_{i=1}^n x_i$. For another sample we will find another $\bar{x}$, so $\bar{x}$ is a random variable and it is known that it has a normal distribution with mean equal to the population mean $\mu$ and standard deviation equal to $\frac{\sigma}{\sqrt{n}}$. 
We can choose infinitely many rejection regions such that the probability of a type I error (i.e. the probability mass above the rejection region) is $\alpha$. So the question is , which of these infinitely many rejection regions shall we choose ?
Obviously, it makes sense to chose that region that minimises the probability of a type II error (or equivalently, the region that maximises power). A type II error occurs when we accept $H_0$ in cases where $H_1$ is true, or in case where $\bar{x}$ falls outside the rejection region (i.e. accept $H_0$) when $H_1$ is true. 
So we wish to choose the rejection region (RR) that minimises the probability that $\bar{x} \not \in RR$ when $H_1$ is true. i.e. find $RR$ such that $P(\bar{x} \not \in RR|_{H_1})$ is as small as possible. 
So let us look at the cases where $H_1$ is true, i.e. $\mu > \mu_0$. Let us look at the picture below: 

The green density is the one when $H_0$ is true, the rejection region is the one between the two vertical lines, so the surface under the green curve and between the two vertical lines is $\alpha$. 
The red density is the one when $H_1$ is true (note that the mean of the red curve is larger than the one of the green curve to reflect $H_1: \mu > \mu_0$. 
$P(\bar{x} \not \in RR|_{H_1})$ is the area under the red curve and outside of the two vertical lines.  So we have to choose the two vertical lines such that under the green curve we have $\alpha$ between these two lines and such that the area under the red curve, outside of these two lines is as small as possible.  Obviously this will happen when the vertial lines cover the right tail of the green distribution. 
