Two-sided critical regions and two-sided P-value for discrete (integer-valued) negative binomial distribution Let $X$ be a Negative Binomial random variable, $X \sim \mbox{NB}(n, p)$, with $P(X=x) = {n+x-1 \choose x} p^n (1-p)^x, x = 0, 1, 2, \cdots$.  Suppose I do this experiment where I toss a coin until I got 8 heads. I got the 8th head on the 10th trial.  So, we have $n=8$ and $x=2$.  Now, I want to test the hypothesis that $p=0.5$ against a two-sided alternative of $p \ne 0.5$.  What would be the critical region for this test? How would I calculate a two-sided P-value?
P-value is defined as the probability, under the Null, of getting a result as extreme or more extreme than what was obtained in a particular experiment.  Here, it is obvious that $S=\{0,1,2\}$ constitute the critical region of extreme values.  Therefore, $P(X \in S) = 0.0547$.  However, this is only a one-sided P-value.  It is not obvious to me how to define the critical region for the other tail of the asymmetric distribution.  For instance, $P(X > 15) = 0.0466 $.  Would the two-sided P-value for my experiment be $p=P(S_2)$ where $S_2 = {\{0,1,2\}} \cup {\{16 , \cdots\}}$?

It depends on how you define your test statistic/how you decide to measure "more extreme"; there's multiple ways you might do so.
I urge you to frame decision rules in terms of choices of test statistics and rejection regions in relation to them first and foremost; many of the difficulties that tend to trip people up disappear, and then bring in p-values at the end. Once you understand what your chosen set of nested rejection regions are, p-values that go with them are a given.
One simple choice for measuring "deviation from the null" that admits a sense of more extreme might be in terms of the deviation from the expected count under $H_0$ (i.e. $|X-E_0(X)|$). That expected value is $8$, so for it the tail values in "$2$ and below" and "$14$ and above" would be "at least as extreme" as the observed $2$.
Of course one is free to choose some other measure of "deviation" from what you would see under the null.
A different choice would be in terms of the likelihood under the null (per Fisher, as we see in the Fisher-Yates-Irwin exact test); . This again gives "$14$" as the cut off in the upper tail in this case, because $p(14)$ is the largest pmf-value that's no larger than $p(2)$; the "more extreme" values are all the cases that are less probable than $p(2)$ - which for a unimodal distribution will be in the tails.

larger version
Another approach would be to construct a likelihood ratio statistic, and identify (equal or) smaller likelihood ratios than the one observed ($\Lambda=\hat{\mathcal{L}}_0(x)/\hat{\mathcal{L}}_1(x)$) as more extreme.
Finally, some people simply double the one-sided p-value of the 'nearest' side. (Personally I find this unsatisfying/problematic in several ways, but it's very common.)

While it discusses the continuous case, there's some discussion here that's at least somewhat relevant to this discussion: https://stats.stackexchange.com/a/341442/805

