Question

Please answer d,e,f and g, thank you!

roblem 1. Let (U common p.d.f. i 1 be a sequence of ii.d. discrete random variables with f(k) for k = 1, 2, 3 and for n 21 let Sn = Σ,u. (a) Find the probability that S2 is even. (b) Find the probability that Sn is even given that S,-1 is even. (e) Find the probability that Sn is even given that S-1 is odd. (d) Let pn P(Sn is even). Find pn in terms of pn-1. (e) Find the generating function for the pn's. (f) Show that limn pn = 1 /2. (g) Suppose that the probability mass function of the U,'s is not necessarily uniform but instead satisfies f(k) = Pk for k = 1 , 2, 3 where each Pk > 0 and Σ 1p.-1. What does the generating function for the pn's look like now? In this more general setting does limn Pn 1/2?

Answer 1

(a) S₂ will be even if both U₁ and U₂ are even or both U₁ and U₂ are odd.

$P(S_2\texttt{ even}) = P(U_1\texttt{ even})\cdot P(U_2\texttt{ even}) + P(U_1\texttt{ odd})\cdot P(U_2\texttt{ odd}) \\ = \frac{1}{3}\cdot \frac{1}{3} + \frac{2}{3}\cdot \frac{2}{3} = \frac{5}{9}$

(b) If S_n-1 is even, then we need U_n to be even to make S_n even.

$P(S_n\texttt{ even}|S_{n-1}\texttt{ even}) = P(U_n\texttt{ even}) = \frac{1}{3}$

(c) If S_n-1 is odd, then we need U_n to be odd to make S_n even.

$P(S_n\texttt{ even}|S_{n-1}\texttt{ odd}) = P(U_n\texttt{ odd}) = \frac{2}{3}$

(d) The probability of S_n being even will depend on the probability of S_n-1 being even.

$\rho_n = \frac{1}{3}\cdot\rho_{n-1} + \frac{2}{3}\cdot(1-\rho_{n-1}) = \frac{2}{3}-\frac{1}{3}\cdot\rho_{n-1}=\frac{2-\rho_{n-1}}{3}$

(e) We can calculate the few initial elements of this series. We get:

$\rho_n = \left\{\frac{1}{3}, \frac{5}{9}, \frac{13}{27}, \frac{41}{81}, \cdots\right\}$

We can observe that the denominators increase by a factor of 3 for every n. Also, the numerators are alternating between (3ⁿ-1)/2 for odd n and (3ⁿ+1)/2 for even n. From this, we get the generating functions as:

$\rho_n = \left\{\begin{matrix} \frac{3^n-1}{2\cdot 3^n}=\frac{1}{2}-\frac{1}{2\cdot 3^n}, & n\texttt{ is odd}\\ \\ \frac{3^n+1}{2\cdot 3^n}=\frac{1}{2}+\frac{1}{2\cdot 3^n}, & n\texttt{ is even} \end{matrix}\right.$

(f) We know that:

$\lim_{n\to \infty}\frac{1}{3^n} = 0$

Thus, both the series for $\rho_n$ converge and we get:

$\lim_{n\to\infty}\rho_n = \left\{\begin{matrix} \frac{1}{2}-\frac{1}{2}\lim_{n\to\infty}\frac{1}{3^n}=\frac{1}{2}, & n\texttt{ is odd}\\ \\ \frac{1}{2}+\frac{1}{2}\lim_{n\to\infty}\frac{1}{3^n}=\frac{1}{2}, & n\texttt{ is even} \end{matrix}\right.$

So, both the series converge to the same limit and we get:

$\lim_{n\to\infty}\rho_n = \frac{1}{2}$

(g) In this case, the recursion formula will be:

$\rho_n = p_2\cdot\rho_{n-1} + (p_1+p_3)\cdot(1-\rho_{n-1}) = p_2\cdot\rho_{n-1} + (1-p_2)\cdot(1-\rho_{n-1})\\ = (1-p_2)-(1-2\cdot p_2)\cdot\rho_{n-1}$

We can see that the series converges by taking the difference between the successive terms:

$\rho_n - \rho_{n-1} = \left[(1-p_2) - (1-2p_2)\rho_{n-1} \right ] -\left[(1-p_2) - (1-2p_2)\rho_{n-2} \right ] \\ = -(1-2p_2)(\rho_{n-1}-\rho_{n-2})$

So, this series will be oscillating and will converge only if (1-2p₂>0), i.e. if p₂<1/2.