% Probablity that random variable divisibility

\input fontmac
\input mathmac

\classicmode

\def\Res{\op{Res}}

\font\eightsl=cmsl8

\maketitle{On the divisibility of a random variable\footnote{$^*$}{\eightpt This is a generalisation of an assignment
question given by Prof. Luc Devroye in his COMP 690 class, Fall 2020.}}
{by}{Marcel K. Goh (\rm Montr\'eal, Qu\'ebec)}{11 September 2020}

\medskip

\noindent If $X$ is an integer-valued random variable and $n$ is a positive integer, we might want to know
the probability that $n$ divides $X$. To this end, we will make use of the probability generating
function
$$p(z) = \sum_{j=0}^\infty p_jz^j.$$
We have the following result:

\proclaim Theorem A. Let $X$ be a nonnegative integer-valued random variable whose probability generating function
$p(z)$ has radius of convergence $R>1$. Let $n$ be a positive integer and let $\zeta_1,\ldots,\zeta_n$ denote the
$n$th roots of unity. The probability that $n$ divides $X$ is given by two equivalent formulas:
$$\pr\big\{X \equiv 0 \!\!\!\!\pmod{n}\big\}
   = {1\over n}\sum_{k=1}^n p(\zeta_k) = {1\over n}\sum_{k=1}^n \Re\,p(\zeta_k)$$

\proof
Let $p_j = \pr\{X = j\}$ for all positive integers $j$. We are trying to compute the sum
$$p^* = p_0 + p_n + p_{2n} + \cdots.$$
Consider the generating function
$$f(z) = \bigg(1 + {1\over z^n} + {1\over z^{2n}} + \cdots\bigg) p(z).$$
For any multiple of $kn$ of $n$, there is some term of the infinite sum that will pull $p_{kn}$ into the constant
term of $f(z)$. So it is clear that $[z^0] f(z) = p_0 + p_n + p_{2n} +\cdots = p^*$.
We can rewrite $f(z)$ as
$$f(z) = {p(z)\over 1 - z^{-n}} = {z^np(z) \over z^n - 1}.$$
Letting $g(z) = f(z)/z$ and applying Cauchy's Integral Formula, the constant coefficient is given by
$$[z^0]f(z) = [z^{-1}] g(z) = {1\over 2\pi i}\oint g(z)\,dz,$$
where the path of integration is taken in the annulus of convergence.
The function
$$g(z) = {z^{n-1}p(z)\over z^n - 1}$$
has only $n$ singularities on the unit circle: a pole of order 1 at each of the $n$ roots of unity.
So we may take
our path of integration to be any positively-oriented loop around the origin that stays outside the closed unit disk
and inside the disk $|z| < R$.
By the Residue Theorem, this is the sum of the residues at each of the $n$ poles, so we have
$$p^* = {1\over 2\pi i}\oint g(z) \,dz =
    {1\over 2\pi i}\cdot 2\pi i\big(\Res(g;\zeta_1) + \cdots + \Res(g; \zeta_n)\big).$$
We let $g(z) = a(z)/b(z)$, and since $a(z) = z^{n-1}p(z)$ and $b(z) = z^n - 1$ are both holomorphic in neighbourhoods
around each of the poles, for any pole $\zeta_i$ of $g$ we have
$$\Res(g;\zeta_k) = {a(\zeta_k)\over b'(\zeta_k)} = {{\zeta_k}^{n-1}p(\zeta_k)\over n{\zeta_k}^{n-1}}
            = {p(\zeta_k)\over n}.$$
Plugging the $n$th roots of unity into the formula, we have
$$p^* = \sum_{k=1}^n \Res(g;\zeta_k) = \sum_{k=1}^n {p(\zeta_k)\over n}$$
Note if $\zeta_k$ is not real, then $\overline{\zeta_k}$ is also an $n$th root of unity. Using the identity
$\Re z + \Re(\overline z) = (z + \overline z)$, we find that
$$p^* = {1\over n}\sum_{k=1}^n p(\zeta_k) = {1\over n}\sum_{k=1}^n \Re\,p(\zeta_k),$$
assuring us that $p^*$ is real and proving the theorem statement.\slug

\end