91Ó°ÊÓ

We will condition on \(X_1\). There are two possibilities: either \(X_1 < x\) and \(N=1\), or \(X_1 \geq x\) and the sequence starts at \(X_2\). So, we can write the expected value \(f(x)\) as follows: $$ f(x) = P[X_1 < x] + E[N | X_1 \geq x] \cdot P[X_1 \geq x] . $$ Now, notice that since \(X_1 \sim U(0, 1)\), we have \(P[X_1 < x] = x\) and \(P[X_1 \ge x] = 1-x\). Also, given \(X_1 \ge x\), the sequence starting at \(X_2\) is the same as the original sequence starting at \(X_1\), so \(E[N | X_1 \geq x] = 1 + f(x)\). Therefore, $$ f(x) = x + (1 + f(x))(1-x) . $$

Now we need to differentiate both sides of the equation \(f(x) = x + (1 + f(x))(1-x)\). The derivative of \(f(x)\) is \(f'(x)\), and by using the product and chain rule, we get $$ f'(x) = 1 - (1 + f(x)) + (1-x)f'(x) $$.

We can now solve the resulting equation \(f'(x) = 1 - (1 + f(x)) + (1-x)f'(x)\). We will first isolate \(f'(x)\) terms on one side of the equation: $$ f'(x) - (1-x)f'(x) = 1 - (1 + f(x)) $$ Factor out \(f'(x)\) on the left-hand side: $$ f'(x)(1-(1-x)) = -f(x) $$ We notice that the left-hand side simplifies to: $$ f'(x)x = -f(x) . $$ Now, we will solve this first-order linear differential equation. One way of solving this is by multiplying both sides of the equation by the integrating factor \(\mu(x) = e^{\int\frac{1}{x}dx} = x\) $$ x^2f'(x) + xf(x) = 0 . $$ Now, we notice that the left-hand side of the equation is the derivative of the product \(x^2f(x)\). So, integrating both sides with respect to \(x\) we get $$ \int d(x^2f(x)) = \int 0 dx $$ $$ x^2f(x) = c , $$ where \(c\) is the constant of integration. We will find the constant \(c\) by plugging in the boundary condition \(f(1) = 1\). This gives: $$ 1 = c \Rightarrow x^2f(x) = 1 . $$ Finally, we have $$ f(x) = \frac{1}{x^2} . $$

Now we will argue that $$ P[N \geq k] = \frac{(1-x)^{k-1}}{(k-1)!} $$ To start, notice that \(N \geq k\) is equivalent to the first \(k-1\) pairs of consecutive random variables \((X_1, X_2), (X_2, X_3),..., (X_{k-2}, X_{k-1})\) satisfying \(X_i \le X_{i+1}\). This is because \(N \geq k\) implies that the first time \(X_n < X_{n-1}\) occurs is at \(n \ge k\), and therefore, \(X_i > X_{i+1}\) does not occur for any \(i < k - 1\). Consider the first \(k-1\) terms of the sequence \((X_1, X_2, ..., X_{k-1})\). We can think of this sequence as a random walk in \([0,1]\). Notice that the steps of the random walk are uniform random variables in \((0,1)\), so the probability that the first \(k-1\) terms are all less than \(x\) is given by the volume of the simplex defined by the constraints \(0\le X_i \le X_{i+1} \le x, 1 \le i \le k-2\). This volume can be computed as: $$ V_k = \int_0^x \int_0^{x_1} ... \int_0^{x_{k-2}} dx_{k-2} ... dx_{1} $$ Now we notice that this integral represents the probability of the event \(N \geq k\) as $$ P[N \geq k] = \frac{V_k}{(k-1)!} $$ where \(V_k\) can be obtained using the formula \( V_k = x^{k-1}(1-x)\). Substituting this in the above equation, we have $$ P[N\geq k] = \frac{(1-x)^{k-1}}{(k-1)!} . $$

Now we will use the result from part (d) to find \(f(x)\). $$ f(x) = E[N] = \sum_{k=1}^{\infty} kP[N=k] $$ The probability \(P[N=k]\) can be expressed in terms of \(P[N\geq k]\) as follows: $$ P[N=k] = P[N\geq k] - P[N\geq k+1] , $$ which allows us to rewrite the expression for \(f(x)\): $$ f(x) = \sum_{k=1}^{\infty}\left( P[N\geq k] - P[N\geq k+1] \right) $$ Using properties of infinite sums, this expression can be rearranged as: $$ f(x) = P[N\geq 1] = \frac{(1-x)^{1-1}}{(1-1)!} = 1 $$ Thus, our second approach gives us \(f(x)=1\) for the given problem. However, this second approach is wrong by construction, since our result contradicts the correct solution (f(x) = 1/x^2) obtained in part (c).