probability - Is a Markov process uniquely determined?

Let

• $E$ be a Polish space and $\mathcal E$ be the Borel $\sigma$-algebra on $E$


• $I\subseteq[0,\infty)$ be closed under addition and $0\in I$

Please consider the following result:

Let $(\kappa_t:t\in I)$ be a Markovian semigroup on $(E,\mathcal E)$ $\Rightarrow$ There is a measurable space $(\Omega,\mathcal A)$ and a Markov process $X$ with distributions $(\operatorname P_x)_{x\in E}$ such that $$\operatorname P_x\left[X_t\in B\right]=\kappa_t(x,B)\;\;\;\text{for all }x\in E,B\in\mathcal E\text{ and }t\in I\;.\tag 1$$ Conversely, given a Markov process $X$ with distributions $(\operatorname P_x)_{x\in E}$ on a measurable space $(\Omega,\mathcal A)$, a Markovian semigroup $(\kappa_t:t\in I)$ is defined by $(1)$.

It turns out that $X$ in the first part of the statement can be constructed as the family of coordinate maps on $(\Omega,\mathcal A)=(E^I,\mathcal E^{\otimes I})$.

I've seen that many authors assume that Markov processes are such coordinate maps. Why can they do that?

The statement above doesn't state, that given $(\Omega,\mathcal A)$ there is one unique Markov process, does it? However, the finite-dimensional distributions of $X$, i.e. $$\operatorname P_x\left[X\in\;\cdot\;\right]\circ\pi_J^{-1}\;\;\;\text{for }J\subseteq I\text{ with }|J|<\infty\;,\tag 2$$ where $\pi_J:E^I\to E^J$ are the canonical projections, are uniquely determined by $(1)$.

Maybe $(\operatorname P_x)_{x\in E}$ (not only the finite-dimensional distributions) are uniquely determined by $(1)$, if $I\subseteq \mathbb N_0$ or $I$ is at least almost countable or when $E$ is almost countable.

So, why does the stated result allows us to think about $X$ as being uniquely determined?

integration - Evaluate $int_{-infty}^infty frac{1}{sqrt{z^2 + 1}}frac{1}{z - alpha} dz$.

Evaluate $$\int_{-\infty}^\infty \frac{1}{\sqrt{z^2 + 1}}\frac{1}{z - \alpha} dz\,.$$

What is an elegant way to evaluate this integral for Im $\alpha >0$? I imagine using residue theorem will lead to an elegant solution, such as in these related questions [1,2,3]. However I've been unable to adapt them to this line integral.

One requirement is that $\frac{1}{\sqrt{z^2 + 1}}$ be analytic in a strip around the real line $(-\infty,\infty)$. In my eyes this implies that the branch cuts can not cross the real line. For example the principal branches (parallel to the real line) or the branches $[\mathrm{i},\mathrm{i}\infty)$ and $(-\mathrm{i} \infty, -\mathrm{i}]$.

Answer

This is probably not elegant, but you can probably find a place to use the residue theorem. Let $I$ denote the integral
$$\int_{-\infty}^{\infty}\frac{1}{\sqrt{x^2+1}\ (x-\alpha)}dx.$$
Then, $I$ equals
$$\int_0^\infty\frac{1}{\sqrt{x^2+1}}\left(\frac{1}{x-\alpha}-\frac{1}{x+\alpha}\right)dx=2\alpha\int_0^\infty\frac{1}{\sqrt{x^2+1}\ (x^2-\alpha^2)}dx$$

Take $x$ to be $\sinh(t)$. Then
$$I=2\alpha\int_0^\infty\frac{1}{\sinh^2(t)-\alpha^2}dt.$$
Since $\sinh(t)=\frac{e^t-e^{-t}}{2}$, by setting $s=e^t$, we have
$$I=2\alpha\int_1^\infty\frac{1}{\frac{1}{4}\left(s-\frac1s\right)^2-\alpha^2}\frac{ds}{s}=2\alpha\int_0^1\frac{1}{\frac{1}{4}\left(s-\frac1s\right)^2-\alpha^2}\frac{ds}{s}.$$
That is,
$$I=4\alpha\int_0^\infty\frac{s}{s^4-(4\alpha^2+2)s^2+1}ds.$$
Using partial fractions,
$$I=\int_0^\infty\left(\frac{1}{s^2-2\alpha s-1}-\frac{1}{s^2+2\alpha s-1}\right)ds.$$
(This is probably the place you can use the residue theorem but I am not too competent with that. Maybe you need to use a logarithm factor, and something like a keyhole contour.)

Since $$s^2-2\alpha s-1=(s-\alpha-\sqrt{\alpha^2+1})(s-\alpha+\sqrt{\alpha^2+1})$$ and $$s^2+2\alpha s-1=(s+\alpha-\sqrt{\alpha^2+1})(s+\alpha+\sqrt{\alpha^2+1})$$ (using the principal branch of $\sqrt{\phantom{a}}$), we get
\begin{align}I&=\frac{1}{2\sqrt{\alpha^2+1}}\int_0^\infty\left(\frac{1}{s-\alpha-\sqrt{\alpha^2+1}}-\frac{1}{s-\alpha+\sqrt{\alpha^2+1}}\right)ds\\
&\phantom{aaa}-\frac{1}{2\sqrt{\alpha^2+1}}\int_0^\infty\left(\frac{1}{s+\alpha-\sqrt{\alpha^2+1}}-\frac{1}{s+\alpha+\sqrt{\alpha^2+1}}\right)ds
\\&=-\frac{1}{2\sqrt{\alpha^2+1}}\ln\left(\frac{\alpha+\sqrt{\alpha^2+1}}{\alpha-\sqrt{\alpha^2+1}}\right)+\frac{1}{2\sqrt{\alpha^2+1}}\ln\left(\frac{\alpha-\sqrt{\alpha^2+1}}{\alpha+\sqrt{\alpha^2+1}}\right)\\&=\frac{1}{\sqrt{\alpha^2+1}}\ln\left(\frac{\alpha-\sqrt{\alpha^2+1}}{\alpha+\sqrt{\alpha^2+1}}\right)=-\frac{2\ln(\alpha+\sqrt{\alpha^2+1})}{\sqrt{\alpha^2+1}}=-\frac{2\operatorname{arccosh}(-i\alpha)}{\sqrt{\alpha^2+1}}.\end{align}
The particular case $\alpha=i$ yields $I=2i$.

elementary number theory - General method for solving $axequiv bpmod {n}$ without using extended Euclidean algorithm?

Consider the linear congruence equation $$ax\equiv b\pmod { n}.$$ One way to solve it is solving a linear Diophantine equation
$$
ax+ny=b.
$$

I saw somebody solved it by another method somewhere I don't remember:

Solve $144x\equiv 22\pmod { 71}$.
$$\begin{align}
144x\equiv 93 &\pmod { 71}\\
48x\equiv 31&\pmod { 71}\\
48x\equiv -40&\pmod { 71}\\
6x\equiv -5&\pmod { 71}\\
6x\equiv 66&\pmod { 71}\\
x\equiv 11&\pmod { 71}
\end{align}
$$

Instead of solving a Diophantine equation using extended Euclidean algorithm, he uses the rules of congruence such as

If $a_1\equiv b_1\pmod {n}$ and $a_2\equiv b_2\pmod {n}$, then $a_1\pm a_2\equiv b_1\pm b_2\pmod {n}$.

Here are my questions:

• Does the second method always work?


• What's the general algorithm for solving $ax\equiv b\pmod {n}$ in this way?

Answer

For this example it is simpler to note that

$$\rm mod\ 71\!:\ \ \frac{22}{144}\: \equiv\: \frac{11}{72}\:\equiv\: \frac{11} 1 $$

When the modulus is prime one can employ Gauss's algorithm, for example

$$\rm mod\ 29\!:\ \ \frac{1}8\: \equiv \frac{4}{32}\: \equiv\: \frac{4}{3}\:\equiv\: \frac{40}{30}\: \equiv\: \frac{11}{1}$$

I.e. scale $\rm A/B\ \to AN/BN\ $ by the least $\rm\:N\:$ so that $\rm\ BN > 29\:.\ $ Then reduce the numerator and denominator $\rm\ mod\ 29,\:$ and iterate. You will eventually obtain a denominator of $1$ since each step reduces the denominator. Isn't that sweet? That's they key idea that led Gauss to the first proof of the Fundamental Theorem of Arithmetic, i.e. unique factorization of integers.

soft question - Reference for Engineering Mathematics

I am a graduate Engineer looking to qualify a post graduate entrance examination (for Master's degree) where I have 'Engineering Mathematics' as one of my Subjects.I hereby paste my course syllabus:

ENGINEERING MATHEMATICS

Linear Algebra: Matrix algebra, Systems of linear equations, Eigen values and eigen vectors.

Calculus: Functions of single variable, Limit, continuity and differentiability, Mean value theorems, Evaluation of definite and improper integrals, Partial derivatives, Total derivative, Maxima and minima, Gradient, Divergence and Curl, Vector identities, Directional derivatives, Line, Surface and Volume integrals, Stokes, Gauss and Green’s theorems.

Differential equations: First order equations (linear and nonlinear), Higher order linear

differential equations with constant coefficients, Cauchy’s and Euler’s equations, Initial and boundary value problems, Laplace transforms, Solutions of one dimensional heat and wave equations and Laplace equation.

Complex variables: Analytic functions, Cauchy’s integral theorem, Taylor and Laurent series.

Probability and Statistics: Definitions of probability and sampling theorems, Conditional
probability, Mean, median, mode and standard deviation, Random variables, Poisson,Normal and Binomial distributions.

Numerical Methods: Numerical solutions of linear and non-linear algebraic equations Integration by trapezoidal and Simpson’s rule, single and multi-step methods for differential
equations.

Hence, I am actually looking for some standard textbooks to cover up the syllabus very well.I would actually prefer to refer to some proper textbooks for each of the portions separately instead of following a general textbook covering up all the topics.

I went through 'Advanced Engineering Mathematics' by Erwin Kreszig and also the book with the exact same title by Michael Greeberg.To be honest I found both of them quite satisfactory but not thrilling to learn the subject with a solid foundation and in depth understanding that would make me feel comfortable enough.I am precisely looking for books that would be quite easy to follow as some self teaching guides yet complete with regards to both the content and concepts.Any suggestions?

probability theory - Application of Strong Markov Property

Theorem SMP (Strong Markov Property)

Let $X$ be a time homogenous Markov process with $T=\mathbb R_+$ or
$\mathbb Z_+$ and let $\tau$ be a stopping time taking countably many
values. Then $$P[\theta _{\tau}X\in A\mid \mathscr
F_{\tau}]\overset{\text {a.s on }\left\{ \tau <\infty \right\}
}{=}P_{X_\tau}(X\in A)$$

Assume from now on $T=\mathbb{Z}_+$ and that $X$ is canonical. Define the first hitting time of state $y$ as $\tau=\inf \left\{ n\geq 0:X_n=y \right\} $. Now define recursively $$\tau_y ^{k+1}=\tau_y^k+\tau_y\circ \theta_{\tau^k_y},\;\;\;k\geq 0$$ starting from $\tau^0_y=0$.

Why does the SMP imply the following equality?$$P_x \left\{ \tau^k_y<\infty,\;\tau_y\circ\theta_{\tau^k_y} \right\}=P_x \left\{ \tau^k_y<\infty \right\} P_y \left\{ \tau_y<\infty \right\}$$

Answer

The missing step has nothing in particular to do with Markov processes - it uses the decomposition $P(A\cap B)=P(B\mid A)P(A)$. Thus $$\begin{align} P_x \left\{ \tau^k_y<\infty,\;\tau_y\circ\theta_{\tau^k_y} \right\} & =P_x \left\{ \tau_y\circ\theta_{\tau^k_y} \mid \tau _y^k<\infty \right\} P_x \left\{ \tau^k_y<\infty \right\}\\ & =P_x \left\{ \tau^k_y<\infty \right\} P_y \left\{ \tau_y<\infty \right\} \end{align}$$ where the strong Markov property is used in the final transition.

Can all limits be solved without L'Hopital?

Is there any type of limit that requires L'Hopital's rule to solve or can all limits be solved without using it?

If all limits can be solved without L'hopitals, is there some sort of proof or intuition for this?

Answer

Usually Taylor's expansion has the same strength. However, if you prohibit both L'Hopital and Taylor, then I doubt that $\lim_{x\to 0} \frac{\sin x-x}{x^3}$ or $\lim_{x\to 0} \frac{\sin x-x+x^3/6}{x^5}$ can be solved elementary, without using the ideas of L'hopital or Taylor in some sense.

abstract algebra - Characterising the irreducible polynomials in positive characteristic whose roots generate the (cyclic) group of units of the splitting field

For a nonzero element $\alpha \in \mathbb F_{p^n}$ (the finite field of cardinality $p^n$) is there a simple criterion to tell whether $\alpha$ is a generator of the cyclic group $\mathbb F_{p^n}^\times$ by looking at the minimal polynomial of $\alpha$ over $\mathbb F_p$?

Here is what I know so far:
Let $n\ge 1$ be an integer, $p$ be a prime and $\mathbb F_p = \mathbb Z/p\mathbb Z$ be the prime field of characteristic $p$. It is known that there is a unique (upto isomorphism) field $\mathbb F_{p^n}$ of cardinality $p^n$ which is the splitting field of $g (x) = x^{p^n} - x$.

If $f (x) \in \mathbb F_p [x]$ is monic irreducible of degree $n$ then $f (x)$ is separable and $\mathbb F_{p^n} \cong \mathbb F_p [t]/(f (t))$ is also the splitting field of $f (x)$.
Further if $\alpha$ is any root of $f (x)$ in $\mathbb F_{p^n}$ then

• $\mathbb F_{p^n} = \mathbb F_p (\alpha)$ (so $\alpha$ is a primitive element of the field extension $\mathbb F_{p^n}/\mathbb F_p$)


• $m_{\alpha, \mathbb F_p} (x) = f (x)$ (the minimal polynomial of $\alpha$ over $\mathbb F_p$)


• $f (x) = \prod\limits_{i = 0}^{n - 1} (x - \alpha^{p^i})$

Also, there are exactly

• $M (n, p)/n$ distinct degree $n$ monic irreducible polynomials in $\mathbb F_p [x]$


• $M (n, p) = \sum\limits_{d \mid n} p^{n/d} \mu (d)$ distinct primitive elements $\beta$ of $\mathbb F_{p^n}/\mathbb F_p$


• $p^n - 1$ elements in the cyclic group $\mathbb F_{p^n}^\times$


• $\phi (p^n - 1)$ generators of the cyclic group $\mathbb F_{p^n}^\times$

It is clear that each generator $\beta$ of the cyclic group $\mathbb F_{p^n}^\times$ is an element of degree $n$ over $\mathbb F_{p}$, i.e. $\deg m_{\beta, \mathbb F_p} (x) = n$, and hence is a primitive element of the field extension. It is also clear that all the other roots $\beta^{p^i}$ of the minimal polynomial $m_{\beta, \mathbb F_p} (x)$ are also generators of the cyclic group since $\gcd (p^i, p^n - 1) = 1$.

However in general the number of cyclic generators $\phi (p^n - 1)$ is much less than the number of primitive elements of the extension $M (n, p)$ (for example, for $n = 2$, $\phi (p^2 - 1)$ will be much less than $M (2, p) = p^2 - p$.

So now the question is:

1. Characterise all the monic irreducible polynomials $f (x) \in \mathbb F_p [x]$ whose roots are cyclic generators of $\mathbb F_{p^n}^\times$.


2. If $\beta$ is a cyclic generator of $\mathbb F_{p^n}^\times$ what are the indices $0 \le k < p^n$ for which the degree of $\beta^k$ over $\mathbb F_p$ is $n$ (or in general any $d \mid n$)?

P.S. I don't know any Galois theory, so if you use any of that, then I would appreciate if a reference is given.