I recently learned about characteristic functions and in particular the Bochner Theorem which helps us ascertain when a given function is a characteristic function for some probability distribution.
The standard version of Bochner's theorem from Wikipedia states that: For any normalized continuous positive definite function $f$ on $G$ (normalization here means $f$ is $1$ at the unit of $G$), there exists a unique probability measure on ${\displaystyle {\widehat {G}}}$ such that
$${\displaystyle f(g)=\int _{\widehat {G}}\xi (g)d\mu (\xi )}$$
i.e. $f$ is the Fourier transform of a unique probability measure $\mu$ on ${\displaystyle {\widehat {G}}}$. In other words, any continuous positive-definite function on the real line is the Fourier transform (characteristic function) of a (positive) finite measure.
Another version, which combines Khinchine’s theorem is stated as follows:
Let $\phi: \mathbb{R} \to \mathbb{C}$ be a continuous function with $\phi(0) =1$. Then $\phi$ is a characteristic function $\iff$ $\forall n \in \mathbb{N}, t_i \in \mathbb{R}$ and $\lambda_i \in \mathbb{C}$ for $i = 1, \dots, n$, we have $$\sum_{i, j =1}^n \phi(t_i - t_j) \lambda_i \overline{\lambda_k} \geq 0$$
Wikipedia notes that the trouble with these theorems is that computational verification of the positive-definiteness is not easy. I'm curious to learn whether there is an effective/efficient way to check for positive definiteness of a function (or the condition in the second version provided below) because based on the definition of positive-definiteness for functions, it seems like we would have to prove the square matrices for all sizes and possible permutations are Hermitian.
I am also aware of Polya's criterion as an alternative to deal with the problem motivating Bochner's theorem but are there any easy ways to verify that there exists a distribution such that a given function corresponds to the characteristic function for it. Until now, I have defined appropriate random variables to solve relatively direct problems (convex combinations of characteristic functions and square of the absolute value of a characteristic function also define characteristic functions).
I think that the answer to your question will be heavily dependent on the group $G$. In the case of finite cyclic groups $G = \mathbb{Z}/n\mathbb{Z}$ you can apply the Fast Fourier Transform to get the Fourier coefficients of $\phi$ with a computational cost of $O(n \log n)$ and then you only have to check the positivity of $\hat\phi$. The same method will work for finite Abelian groups.
I do not think there is short answer for $G$ infinite.