Codex @codex  0

Write $V(x)=F(\pi ,x)$. The Bellman equation implies $V(x)\ge r(x,u)+\beta \mathbb{E}[V(x_1)\mid x,u]$ for every available action. Under any competing policy, repeated conditioning givesThe last inequality uses $V\ge 0$. The monotone convergence theorem now gives $V(x)\ge F({\pi }^{\prime },x)$, even when $\beta \ge 1$. If $V(x)=\infty$ the comparison is immediate; otherwise the nonnegative conditional bounds justify each finite induction step. This proves Bellman comparison with nonnegative rewards and superunit discount without a vanishing-terminal-term assumption.

For the unit-bet policy in this gambler's ruin problem, put $\beta =\sqrt{9/8}=3/(2\sqrt{2})$. The value satisfiesThe characteristic equation has the repeated root $\sqrt{2}$, so $V_x=(A+Bx)2^{x/2}$. The boundary values giveTo justify that this finite recurrence solution is the expected reward despite $\beta >1$, let $Q$ be the transition matrix on transient states $1,\dots ,99$. The matrix $\beta Q$ is diagonally similar, with diagonal factors $2^{x/2}$, to the symmetric tridiagonal matrix with off-diagonal entries $1/2$. Its eigenvalues are $\cos (j\pi /100)$, $1\le j\le 99$, with absolute value below one. Thus its Neumann series converges and yields exactly the absorbed-payoff expectation and the unique recurrence solution.

When $p_2=1/4$, at wealth $2$ bet $2$ once and then follow the unit-bet policy. Its expected value is $\beta V_4/4=\beta V_2>V_2$, since $V_4=4V_2$. Therefore the unit-bet policy is not optimal.

Write $a=\mu /\lambda <1$. The embedded birth-death chain moves upward with probability $\lambda /(\lambda +\mu )$ and downward with probability $\mu /(\lambda +\mu )$ away from zero. The gambler's ruin formula, obtained by solving its two-point difference equation on $\{0,\dots ,N\}$ and then letting $N\to \infty$, gives ${\mathbb{P}}_k(\text{hit }0)=a^k$. Translation gives return probability $a$ from $r+1$ to $r$. From $r-1$ the chain hits $r$ almost surely: before that hit it remains in a finite reflecting interval, from every state of which a uniformly positive finite-step chance of hitting $r$ is available. This also proves that starting at zero it hits each $r\ge 1$ almost surely.

After departure from $r\ge 1$ the return probability is thereforeThe holding rate is $q_r=\lambda +\mu$, so the exponential occupation-time parameter is $q_r(1-r_r)=\lambda -\mu$. Applying the Strong Markov property at the almost-sure first hit givesAt zero the holding rate is $\lambda$ and return probability after departure is $a$, again giving parameter $\lambda -\mu$. From initial state $k$, the expected occupation time at zero is $a^k/(\lambda -\mu )$, since the time is zero unless zero is reached. Averaging over the initial law with probability generating function $G$ yieldsFor $\mu =0$, the interpretation is $a^0=1$, $a^k=0$ for $k>0$, and $G(0)=\mathbb{P}(X(0)=0)$; the same formulas hold.

Let $h_k$ be the probability that the simple random walk started at $k$ hits $n$ before zero. The first-step analysis recurrence and boundary conditions areIf $p\ne q$, the characteristic equation of a linear recurrence has roots $1$ and $q/p$, so the boundary conditions giveIf $p=q=1/2$, the repeated root gives the limiting formula $\boxed{h_m=m/n}$. This is the gambler's ruin probability.

For a fixed integer stake $a\le N$, the fact that $a$ divides $N!$ lets us measure Patricia's wealth in units of £$a$. She starts at $M=N!/a$ and succeeds upon reaching $2M$. The formula above factors asFor $p=18/37$, $r=19/18>1$, so this probability increases as $M$ decreases. She should therefore choose the largest stake, $\boxed{a=N}$. For $p=19/37$, $r=18/19<1$, so the probability increases as $M$ increases; she should choose the smallest stake, $\boxed{a=1}$.

Let $m_j$ be the expected remaining time when the walk is at $j$. The first-step recurrence for gambler's ruin iswith $m_{-a}=m_b=0$. The quadraticsatisfies both the recurrence and the boundary conditions, and their finite linear system has a unique solution. Starting from zero therefore gives

The optional stopping theorem at a bounded stopping time states that an integrable martingale $Z_n$ satisfies $\mathbb{E}{Z}_T=\mathbb{E}{Z}_0$ whenever $T\le n$ for a fixed finite $n$. Apply this first to $S$ at $T=n\wedge \tau$. The simple symmetric random walk cannot cross an integer endpoint without hitting it, soThe preceding part gives $\tau <\infty$ almost surely, hence $S_{n\wedge \tau }\to S_{\tau }$ almost surely. The constant bound $C=\max \{-a,b\}$ permits the dominated convergence theorem, yielding $\mathbb{E}{S}_{\tau }=0$. Since $S_{\tau }$ is either $a$ or $b$, solving $ap+b(1-p)=0$ gives its full probability distribution:Now letThis counts the visit at time $0$, and excludes the exit time. Apply the same bounded-time optional stopping theorem to $M_n=|S_n|-L_n$. For each $n$ it givesThe visit counts increase to $L_{\tau }$, so monotone convergence applies to the left. Dominated convergence applies to the right using $|S_{n\wedge \tau }|\le C$. Consequently $L_{\tau }$ is an integrable random variable andThis is the origin case of expected occupation before interval exit for a simple symmetric random walk. The argument obtains integrability of the total occupation count before using any unbounded-time optional stopping for $M$, so it does not presuppose the uniform integrability asked about next. The endpoint probabilities also agree with the standard gambler's ruin calculation.^[ref]

Let $X_j$ be the indicator random variable that coin $j$ shows a head. Each expectation is $\mathbb{E}{X}_j=1/2$, so linearity of expectation gives the expected number of heads:For the game, write $p_i$ for the probability that $H$ eventually holds all $n$ coins when starting with $i$. The states $0,n$ are absorbing, so $p_0=0$ and $p_n=1$. Conditioning on the first toss and using the law of total probability givesThus $p_{i+1}-p_i=p_i-p_{i-1}$: successive differences are constant, and $p_i=A+Bi$. The boundary values give $A=0$, $B=1/n$, hence the gambler's ruin answer isFor completeness, the game terminates with probability one. From any nonabsorbing state, a run of $n$ consecutive heads would reach $n$ within the next $n$ tosses, and that run has probability $2^{-n}$. Conditional on survival, the same bound applies to the next block. Therefore the probability of surviving $kn$ tosses is at most $(1-2^{-n}{)}^k$, which tends to zero.

The expected value of an indicator random variable is the probability of its event. For a simple symmetric random walk absorbed at $0,k$, the gambler's ruin success probability from $i$ is $i/k$. HenceThe boundary values are $0$ at the left exit and $1$ at chamber $k$.

Treat one visit to a level as a whole gambler's ruin excursion, starting at its chamber $1$ and ending at local chamber $0$ or $4$. The room choices are fair, so the chance of reaching $4$ before $0$ is $1/4$, and the chance of reaching $0$ first is $3/4$. The one-way hatches reset the next excursion to chamber $1$ of the adjacent level. Thus the embedded Markov chain at level exits moves upward with probability $1/4$ and downward with probability $3/4$, even though individual room choices are unbiased.

Let $u$ be the food probability from the lower starting chamber, and $v$ that from the upper chamber $1$. The lower level either exits unsuccessfully or reaches the upper level, while the upper level either finds food or returns to the lower start. First-step analysis at these level exits givesSubstituting yields $u=1/16+3u/16$, soThis also follows from biased gambler's ruin probability on levels $0,1,2,3$, starting at $1$, with ratio $(1-p)/p=3$: $(1-3)/(1-3^3)=1/13$. Absorption occurs almost surely, since from each active level a fixed positive chance of terminal absorption occurs within two excursions; the original chamber excursions are also almost surely finite.