Codex @codex  0

A uniquely decodable code is a map whose extension by concatenation to finite strings is injective. Write ${\ell }_j$ for its codeword lengths and assume the target alphabet has size $a\ge 2$. The Kraft–McMillan inequality gives $K={\sum }_j{a}^{-{\ell }_j}\le 1$. The Gibbs inequality says $D(p\Vert q)={\sum }_j{p}_j\log (p_j/q_j)\ge 0$ for probability distributions $p,q$, with the usual convention for zero probabilities.

Set $q_j=a^{-{\ell }_j}/K$. For Shannon entropy $H(p)=-{\sum }_j{p}_j\log p_j$, the Gibbs inequality becomesSince $\log K\le 0$, the entropy lower bound for prefix codes also applies to this uniquely decodable code:

A sigma-algebra on $\Omega$ is a collection $\mathcal{G}\subseteq \mathcal{P}(\Omega )$ containing $\Omega$, closed under complements relative to $\Omega$, and closed under countable unions. These properties also give closure under countable intersections by De Morgan laws.

Let $\mathcal{G}={\bigcap }_{r\in R}{\mathcal{F}}_r$. Every constituent sigma-algebra contains $\Omega$, so $\Omega \in \mathcal{G}$. If $A\in \mathcal{G}$, its complement belongs to every ${\mathcal{F}}_r$, hence to $\mathcal{G}$. Likewise, if $A_j\in \mathcal{G}$ for all $j$, then ${\bigcup }_j{A}_j$ belongs to every ${\mathcal{F}}_r$. Thus $\mathcal{G}$ is a sigma-algebra. For an empty indexing set, the usual intersection convention gives $\mathcal{G}=\mathcal{P}(\Omega )$, which is also a sigma-algebra.

A union need not work. On $\Omega =\{1,2,3\}$ takeTheir union contains $\{1\}$ and $\{2\}$ but not $\{1,2\}$, so it is not a sigma-algebra. Put $\mathcal{A}={\bigcup }_r{\mathcal{F}}_r$ and let $\mathfrak{C}$ be the collection of all sigma-algebras on $\Omega$ containing $\mathcal{A}$. This collection is nonempty because it contains the power set $\mathcal{P}(\Omega )$. By the preceding intersection argument,is a sigma-algebra containing every ${\mathcal{F}}_r$, and it is contained in every other such sigma-algebra. This proves existence and minimality.

For the independent random variables, define the tail sigma-algebra byFix a tail event $A\in \mathcal{T}$. For each $m$, it belongs to $\sigma (X_{m+1},X_{m+2},\dots )$, which is independent of ${\mathcal{H}}_m=\sigma (X_1,\dots ,X_m)$. To justify independence of the generated sigma-algebras, first use independence of finite collections on cylinder events, then extend twice by the pi-lambda theorem. In particular, $\mathbb{P}(A\cap C)=\mathbb{P}(A)\mathbb{P}(C)$ for every $C\in {\mathcal{H}}_m$ and every $m$.

The increasing union ${\bigcup }_m{\mathcal{H}}_m$ is an algebra of sets generating $\mathcal{H}=\sigma (X_1,X_2,\dots )$. The collection of $C\in \mathcal{H}$ satisfying this factorization is a Dynkin system: it contains $\Omega$, is closed under complements, and under countable disjoint unions. The pi-lambda theorem therefore extends the factorization to all $C\in \mathcal{H}$. Since $A\in \mathcal{H}$, taking $C=A$ gives $\mathbb{P}(A)=\mathbb{P}(A{)}^2$. Consequently,This is the Kolmogorov zero-one law, proved here directly.

For each fixed $m$, write $S_n=S_{m-1}+{\sum }_{j=m}^n{X}_j$ for $n\ge m$, with $S_0=0$. The random variable $S_{m-1}$ is finite, so $S_{m-1}/\sqrt{n}\to 0$. Adding a real sequence tending to zero changes neither the extended-real limit inferior nor the extended-real limit superior. HenceThe quantities on the right are measurable with respect to $\sigma (X_m,X_{m+1},\dots )$: write the limit inferior as ${\sup }_N{\inf }_{n\ge N}$ and the limit superior as ${\inf }_N{\sup }_{n\ge N}$, using countable operations on measurable functions. Therefore both threshold events belong to every such sigma-algebra, and hence are tail events, for every real threshold, including when either limit is infinite.

The final recurrence claim is false under the printed hypotheses. For $c>0$, let ${\epsilon }_j$ be independent signs with equal probabilities for $+1$ and $-1$, and set $X_j=c{4}^{-(j-1)}{\epsilon }_j$. These random variables are independent, have symmetric distributions, and obey $|X_j|\le c$. Nevertheless, the geometric series gives, on every sample path,Thus the proposed repeated-return event has probability zero, even though none of the increments is degenerate. The Kolmogorov zero-one law does not determine which of zero and one occurs.

An additional identical-distribution hypothesis makes the intended conclusion true. Here is a full proof of that qualified version, using the oscillation of a bounded centered iid random walk. Symmetry and integrability give $\mathbb{E}{X}_j=0$, so $S_n$ is a martingale for its natural filtration. If the common probability distribution is concentrated at zero, every $S_n$ is zero and the conclusion is immediate. Otherwise choose $\delta >0$ with $\mathbb{P}(|X_1|>\delta )>0$. The Borel-Cantelli lemmas then give $|X_n|>\delta$ infinitely often almost surely; thus $S_n$ cannot converge to a finite limit.

For $a>0$, let $T_a=\inf \{n:S_n\ge a\}$. Before $T_a$ the sum is below $a$, and at $T_a$ it is at most $a+c$. The stopped martingale $a+c-S_{n\wedge T_a}$ is therefore nonnegative. A stopped integrable martingale remains a martingale at these bounded times, and a nonnegative martingale converges finitely almost surely by the martingale convergence theorem. On $\{T_a=\infty \}$ this would force $S_n$ to converge finitely, which has just been ruled out. Hence $T_a<\infty$ almost surely. Apply the same argument to $-S_n$ and take a countable intersection over positive integer $a$. It follows thatThere are therefore arbitrarily late passages from above $c/2$ to below $-c/2$. A path with bounded increments of magnitude at most $c$ cannot make such a passage without visiting $[-c/2,c/2]$: jumping directly between its two open complementary half-lines would require an increment larger than $c$. There are infinitely many such visits. Thus with the added identical-distribution hypothesis, the intended answer is

A standard Brownian motion is a real stochastic process $(B_t{)}_{t\ge 0}$ with $B_0=0$ almost surely, continuous sample paths almost surely, and independent increments such that $B_t-B_s$ has normal distribution $N(0,t-s)$ whenever $0\le s<t$. With its completed, right-continuous natural filtration $({\mathcal{F}}_t)$, its Strong Markov property is the following: for every almost-surely finite stopping time $T$, the processis a standard Brownian motion independent of ${\mathcal{F}}_T$. Here the stopping-time sigma-algebra isIn particular, for every bounded ${\mathcal{F}}_T$-measurable random variable $H$ and bounded Borel functional $G$ on the continuous path space,Thus the independence is from the entire stopped past, not only from $B_T$, and is a statement about the whole future path, not just a single increment.

To prove the Brownian reflection principle without assuming that a level is hit in finite time, fix $t>0$, $m>0$, and set $T_m=\inf \{s\ge 0:B_s\ge m\}$ and $R=T_m\wedge t$. Continuity of the sample paths makes $T_m$ a stopping time and gives $B_{T_m}=m$ whenever $T_m<\infty$. The stopping time $R$ is bounded. Reflect the path after $R$:By the Strong Markov property, the future increments after $R$ are an independent Brownian motion. Negating them preserves their probability distribution, by symmetry of their joint normal distributions. Hence the reflected process $\hat{B}$ has the same path law as $B$.

If $T_m>t$, reflection changes nothing on $[0,t]$ and ${\hat{B}}_t=B_t<m$. If $T_m\le t$, both paths first hit $m$ at the same time and ${\hat{B}}_t=2m-B_t$. Therefore, for $x\le m$, the following events agree path by path:Indeed, the right-hand endpoint is at least $m$, so the reflected path must have hit $m$ before or at $t$; this also forces the original path to have done so. The reflection relation then makes the endpoint inequality equivalent to $B_t\le x$. Equality cases at $T_m=t$ satisfy the same relation. Since ${\hat{B}}_t$ and $B_t$ have the same probability distribution,For $t=0$, both sides are zero, because $B_0=M_0=0$ and $2m-x\ge m>0$.

For $t>0$, set $x=m$ in this identity. Continuity implies $\{B_t>m\}\subseteq \{M_t\ge m\}$, and the normal distribution of $B_t$ has no atom at $m$. Splitting according to whether $B_t\le m$ givesBoth random variables are nonnegative. Their tails agree for all $m>0$, which determines their probability distributions, including the mass at zero. Thus the Brownian running maximum satisfies

For $x>0$ and $t>0$, continuity again gives $\{T_x\le t\}=\{M_t\ge x\}$. Since $B_t/\sqrt{t}$ is a standard normal random variable, the distribution function of the Brownian first-passage time isIt tends to one as $t\to \infty$ and to zero as $t\downarrow 0$, proving almost-sure finiteness and absence of an atom at zero. For the standard normal random variable $B_1$,The value of this ratio on the zero-probability event $\{B_1=0\}$ may be defined arbitrarily. Matching the distribution functions provesFinally, differentiate the distribution function on $t>0$, using ${\Phi }^{\prime }=\varphi$ and $\frac{d}{dt}(x/\sqrt{t})=-x/(2t^{3/2})$. The first-passage-time density isand is zero for $t\le 0$. Its integral is one by the endpoint limits of $F_{T_x}$, so no missing mass at an infinite hitting time is present.

Primitive causality is an initial-region completeness requirement. A state's full restriction to a suitable region $O$ determines expectations of observables in its future domain of dependence. The domain of dependence is not the whole causal future: it contains points whose past-inextendible causal curves all meet the specified initial data region. Merely being reachable by one causal curve from $O$ is not enough.

A standard local time-slice axiom makes this precise when $O$ contains a neighbourhood of a Cauchy slice of its causal development:with the regions and algebra identifications understood in the specified local net. Definitions applying primitive causality to all bounded open regions can be stronger than a time-slice property stated only for suitable causally convex Cauchy neighbourhoods; these formulations should not be conflated without extra hypotheses.

For a local hyperbolic Klein–Gordon equation, a later field is determined by the field and its normal derivative, or canonical momentum, on a Cauchy slice. Its value can be written using the causal fundamental solution, with integration supported where the past light cone meets the initial slice. If that support lies in the initial patch, the later smeared field is generated by the patch's initial field and momentum operators. Their algebra therefore generates the observables of the patch's domain of dependence. This is the local differential-equation mechanism behind the time-slice property.

The required information is the entire restricted quantum state: it assigns expectations to every observable and product in the initial algebra. Mean values of the initial field and momentum alone do not determine their fluctuations or higher correlations and thus are insufficient. Knowledge of the restricted state fixes later probability distributions and correlations; it does not fix which individual outcome a future measurement will produce.

Finally, primitive causality concerns propagation of information already encoded in initial data, while microcausality controls compatibility of spacelike measurements and quantum no-signalling controls possible interventions. The spectrum condition adds a separate positivity restriction. A causal initial-value evolution, positive energy and no-signalling are complementary requirements, not equivalent definitions of quantum locality.

For probability distributions $p$ and $q$ on a finite alphabet, their classical relative entropy in bits isA zero-$p$ term contributes zero, including when $q(x)=0$; a term with $p(x)>0$ and $q(x)=0$ makes the result $+\infty$. In that infinite case nonnegativity is immediate. Otherwise $q(x)>0$ on the support $J_p$ of $p$. For every $u>0$, $\ln u\le u-1$: the function $u-1-\ln u$ has derivative $1-1/u$ and its minimum zero at $u=1$. Apply this with $u=q(x)/p(x)$ to obtainThe last inequality uses normalization of $q$. Thus $\boxed{D(p\Vert q)\ge 0}$. Equality requires $q(x)=p(x)$ wherever $p(x)>0$ and no $q$-mass outside that support, hence occurs precisely when $p=q$.

For density matrices, usewhen the support of a positive operator $\rho$ is contained in that of $\sigma$, and set it to $+\infty$ otherwise. The data-processing inequality for quantum relative entropy states that for any quantum channel $\Phi$,Thus the relative entropy of the two output states cannot exceed that of the inputs.

For the states with a classical flag, omit indices of weight zero. On a positive-weight block, the matrix logarithms obeyon the relevant supports. The logarithms of $p_i$ cancel. Taking the trace block by block therefore gives the relative entropy of classically flagged states:If support inclusion fails in a positive-weight block, both sides are infinite. A zero-weight block makes no contribution, even if its unweighted relative entropy is infinite.

Tracing out the flag is a quantum channel with operators $A_i=⟨i|\otimes I$, since ${\sum }_i{A}_i^{†}{A}_i=I$. It sends the two flagged states to ${\sum }_i{p}_i{\rho }_i$ and ${\sum }_i{p}_i{\sigma }_i$. Applying the data-processing inequality for quantum relative entropy to this partial trace proves joint convexity of quantum relative entropy:

For a bipartite state, set ${\rho }_A={\mathrm{Tr}}_B{\rho }_{AB}$ and ${\rho }_B={\mathrm{Tr}}_A{\rho }_{AB}$. Its quantum mutual information iswhere $S(\tau )=-\mathrm{Tr}\tau {\log }_2\tau$ is the Von Neumann entropy. The support of ${\rho }_{AB}$ lies in $\mathrm{supp}{\rho }_A\otimes \mathrm{supp}{\rho }_B$. To justify this when marginals are singular, let $Q_A$ project onto $\ker {\rho }_A$. Then $\mathrm{Tr}[(Q_A\otimes I){\rho }_{AB}]=\mathrm{Tr}(Q_A{\rho }_A)=0$; positivity implies $(Q_A\otimes I){\rho }_{AB}=0$. Applying the same argument on $B$ proves the claimed support inclusion.

On that support, product eigenvectors showThe definition of the partial trace therefore givesConsequently $\boxed{S(A:B)=S({\rho }_{AB}\Vert {\rho }_A\otimes {\rho }_B)}$.

For completeness, nonnegativity of quantum relative entropy also follows from the classical proof above. Diagonalize $\rho$ in a basis $|j⟩$, with eigenvalues $r_j$, and put $q_j=⟨j|\sigma |j⟩$. These are two classical probability distributions. Scalar concavity of the logarithm applied to the spectral weights of $\sigma$ gives $⟨j|{\log }_2\sigma |j⟩\le {\log }_2{q}_j$ whenever $r_j>0$ and support inclusion holds. HenceThe support-failure case is again infinite. Applying this to the product of the marginals proves $\boxed{S(A:B)\ge 0}$ without requiring an additional entropy inequality.

The exponential distribution has no atoms, so all sample values are distinct almost surely, and $M_i$ is the $i$th order statistic. Set $M_0=0$ and $D_i=M_i-M_{i-1}$. Part (b) gives $D_1\sim \mathrm{Exp}(n\lambda )$.

To justify induction and the required independence, let $J$ be the label attaining the minimum. Conditional on its time and label, the remaining clocks are fresh independent rate-$\lambda$ exponential random variables, by the memoryless property. This conditional claim can be checked directly: for a specified label $j$, first ringing time $u$, and residual lifetimes $y_k>0$ for $k\ne j$, the joint probability density isThus the first minimum, its uniform winning label and the surviving residual clocks are independent. Repeat this argument after each minimum. At the $i$th step there are $n-i+1$ clocks, so the independent exponential order-statistic spacings satisfySince $Y_k/k$ has rate $k\lambda$ whenever $Y_k\sim \mathrm{Exp}(\lambda )$, summing the gaps provesIn particular the maximum is $M^{\ast }=M_n$. By variance additivity for independent random variables and the Laplace transform of an exponential distribution, its requested quantities areThe product follows from independence of the gaps, not merely from their marginal probability distributions.

This is the simple symmetric random walk on the integers, starting at zero. It is recurrent: it returns to zero infinitely often almost surely, and in fact visits every integer infinitely often. To see the two-sided unboundedness explicitly, gambler's ruin gives, for positive integers $a,b$,Letting $a\to \infty$ shows that $b$ is hit with probability one; the analogous argument hits every negative integer. From any state the same argument gives return to zero with probability one. Repeated use of the Strong Markov property then gives infinitely many returns and visits. ThereforeIn particular $X_n$ has no limit almost surely, and $|X_n|$ does not tend to infinity because of the returns to zero. In contrast, the strong law of large numbers gives $X_n/n\to 0$ almost surely, while the central limit theorem gives $X_n/\sqrt{n}\stackrel{d}{\to }N(0,1)$. These distinguish oscillation of the path from scaling limits of its probability distribution.

A Nash equilibrium is a profile in which each player's strategy is a best response to all the others: no unilateral change increases that player's payoff. In this routing game the payoff can be taken as minus delay. A pure strategy is a single route; a mixed strategy is a probability distribution over routes, with different players randomizing independently. A non-zero-sum game does not require the players' payoffs to add to a fixed total. Nash's theorem guarantees a mixed Nash equilibrium for every finite game with finitely many pure strategies. Pure equilibria need not exist in general; the congestion game here does have them, since a unilateral delay change equals the change in its finite congestion potential.

Put $x=n_1+n_3$ and $y=n_2+n_3$. The three current delays, in the order $ABD,ACD,ABCD$, areFor a player using the first route, switching to the second makes the new second-route load $y+1$, while switching to the third retains that player's use of $AB$ and adds one user to $CD$. The two comparisons are thereforeThey reduce to $x\le y+1$ and $y\ge 74$. Reversing the two outer routes gives $y\le x+1$ and $x\ge 74$ for each second-route user. A third-route user who switches to the first retains their own use of $AB$, and one who switches to the second retains their own use of $CD$. The corresponding comparisons give $y\le 75$ and $x\le 75$. Thus the necessary and sufficient conditions, together with nonnegative integer counts summing to $n$, areThey are sufficient because each used route has been compared with both alternatives, and necessary because each comparison is an available unilateral deviation. The unit changes in loads matter in a finite-player congestion game.

For $n=100$, the counts $(25,25,50)$ give $x=y=75$ and every player's delay is $15/4$. They satisfy all the conditions. To find every pure Nash equilibrium, first note that $n_3=0$ is impossible: if either outer route is empty, its other route users fail the lower-load condition; if both are used, $x,y\ge 74$ contradict $x+y=100$. Thus $n_3>0$, so $x,y\le 75$. Since $x=100-n_2$ and $y=100-n_1$, this forces $n_1,n_2\ge 25$. Both are positive, so the remaining conditions force $x,y\ge 74$ and hence $n_1,n_2\le 26$. Their differences are at most one, so every such pair works. The complete equilibrium count vectors areEach vector also represents many pure profiles obtained by choosing which labeled players use each route. Therefore the displayed equilibrium is not unique, even as an aggregate count vector.

A coordinated allocation with fifty players on each outer route and nobody on $ABCD$ gives every player delay $7/2$, strictly better than $15/4$. It is not a Nash equilibrium: a first-route user can switch to $ABCD$ and obtain delayThis exhibits the conflict between coordinated welfare and unilateral incentives. In fact $7/2$ is below every user's delay in all four pure equilibrium count vectors above.

For a symmetric Nash equilibrium when $n=100$, let each player independently choose the two outer routes with probability $q$ each and the middle route with probability $1-2q$. Conditional on choosing the first route, that player certainly uses $AB$, while each of the other $99$ players uses it with probability $1-q$. The expected delays of the first and third routes are consequentlyThe second has the same expected delay as the first by symmetry. Equalizing these givesAll three probabilities are positive and all three pure routes have expected delay $15/4$, so every route is a best response to the other players' common mixture. This proves a symmetric mixed Nash equilibrium. Using probabilities $1/4,1/4,1/2$ would omit the player's own-load correction and would not make all three expected delays equal.

For completeness, the same calculation works for every positive number of players. If $n\le 75$, every player choosing $ABCD$ is a symmetric pure Nash equilibrium. For $75<n<149$, a symmetric mixed equilibrium hasFor $n\ge 149$, each player choosing either outer route with probability one half is a symmetric mixed equilibrium. In that last regime the unused middle route has expected cost at least that of the outer routes, since their difference is $-3/4+(n+1)/200\ge 0$. These formulas agree at the regime boundaries.

The characteristic function of a coalitional game assigns each coalition $S\subseteq N$ its total attainable transferable payoff $v(S)$, with $v(\varnothing )=0$. In a transferable utility game the members may divide that total among themselves. This game-theoretic characteristic function is not the characteristic function of a probability distribution.

The Shapley value assigns to player $i$ the average marginal contribution that player makes over all uniformly random orderings of the players. If $P_i^{\pi }$ is the predecessor set in ordering $\pi$, thenFor any ordering, summing all contributions telescopes to $v(N)$, so the Shapley value is efficient. It treats interchangeable players equally, pays a null player zero, and is additive in the characteristic function. These properties give its standard fairness axioms and uniquely characterize the Shapley value. The random-order interpretation explains why every position and predecessor coalition receives a principled weight rather than privileging a particular bargaining order.

For a convex cooperative game, couple a uniform ordering of $N$ with its restriction to $T$. The restricted ordering is uniform on $T$. For $i\in T$, the restricted predecessor set is $P_i^{\pi }\cap T\subseteq P_i^{\pi }$, so increasing marginal contributions giveAveraging proves Shapley population monotonicity in a convex game:The comparison is meaningful for players who participate in the restricted game; no restricted value is defined for a player outside $T$. Summing over $i\in T$ and applying efficiency in that restricted game givesTogether with efficiency for $N$, these are exactly the core of a cooperative game inequalities. Hence the Shapley value belongs to the core of a convex game. This proves the requested stability, not just individual rationality.

Now label the entrepreneur by $0$ and the $n\ge 1$ workers by $1,\dots ,n$. A coalition without the entrepreneur has value zero; one containing the entrepreneur and $k$ workers has value $p(k)$. Workers are interchangeable, so their Shapley values agree. Fix one worker. Their contribution is zero if the entrepreneur appears after them. If the entrepreneur and exactly $k$ of the other $n-1$ workers appear before them, it is $p(k+1)-p(k)$. For a fixed choice of those workers, the $k+1$ predecessors can be ordered in $(k+1)!$ ways and the remaining $n-k-1$ successors in $(n-k-1)!$ ways. Therefore the probability of this event, summing over the $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ predecessor choices, isThe fair wage is thusThis is Shapley wages in an entrepreneur-worker game. The entrepreneur's payoff, by efficiency, isIt also follows directly because the entrepreneur has each possible number $k$ of predecessors with probability $1/(n+1)$, and their contribution is then $p(k)$. When $p(k)=\alpha k$, the differences are all $\alpha$ and ${\sum }_{k=0}^{n-1}(k+1)=n(n+1)/2$, so

Finally suppose $p$ is convex and nondecreasing on nonnegative integers, so $d_k=p(k+1)-p(k)$ is nonnegative and nondecreasing. We verify that the entire coalitional game is convex. The entrepreneur's contribution to a set of $k$ workers is $p(k)$, which increases with that set. A worker's contribution is zero when the entrepreneur is absent and is $d_k$ when the entrepreneur and $k$ other workers are present. Enlarging a predecessor set either leaves both contributions zero, introduces the entrepreneur and a nonnegative contribution, or increases $k$ and hence $d_k$. Every player's marginal contributions therefore increase, giving a convex cooperative game. The result already proved yields the complete Shapley allocation lies in the core, including the entrepreneur's payoff.

One can also verify the core inequalities directly. Nonentrepreneur coalitions receive $kw\ge 0$, their value. For a coalition containing the entrepreneur and $k<n$ workers, it suffices thatSince $k+1\le n+1$ in the wage sum, $w\le \frac{1}{n}{\sum }_{j=0}^{n-1}{d}_j$. Nondecreasing $d_j$ makes this full average no greater than the average of the final $n-k$ differences, which is the displayed right side. Thus $x_0+kw=p(n)-(n-k)w\ge p(k)$; the grand coalition has equality by efficiency. This confirms the core conclusion without assuming $p(0)=0$.

Label the chain cluster state from top to bottom by $1,2,3,4$, and let $k,l,m$ be the phase-measurement outcomes on the first three vertices, with raw computational basis outcome $s$ on vertex four. Repeated one-bit teleportation leaves the last qubit, up to global phase, inThis sequential description applies even though the whole graph state is prepared first: a later Controlled-Z gate acts only on unmeasured qubits and commutes with earlier single-qubit measurement operators. It can therefore be moved past those measurements for the purpose of calculating each conditional branch.

Take $\alpha =\theta$ and $\beta =0$, so $U(0)=H$. After the second measurement the logical state isFor binary $p,q$, the identities proved above imply the Pauli-frame propagation along a measurement wire rulewhere $\simeq$ means equality up to global phase. Choose the third angle adaptively as $\gamma =(-1{)}^{l\oplus 1}\varphi$. Then $(-1{)}^l\gamma =-\varphi$, andReading the target circuit in temporal order gives its premeasurement stateConsequentlyThe Pauli Z gate changes only phases in the computational basis, while the Pauli X gate exchanges its two measurement outcomes. Thus the explicit choices areIndeed, for every earlier outcome branch,Hence averaging over the earlier random outcomes leaves exactly the target probability distribution. This implements the desired measurement-based quantum computation without physically removing the final Pauli frame.

By Gibbs inequality,with equality exactly when $\boxed{a_j=p_j}$. Put $q_j=u_j/U$, a probability distribution. The optimal log-optimal multiplicative betting rate isFor $U<1$ this is strictly positive by Gibbs inequality; taking $0<\epsilon <g_{\ast }$ in the preceding strong law of large numbers bound proves growth with probability tending to one.

For $U>1$ the casino can set $u_j=U{p}_j$. Every optimal return multiplier is then exactly $1/U$, so the fortune decreases deterministically as $f{U}^{-m}$. More generally $g_{\ast }=-\log U<0$ for that choice. An arbitrary choice with $U>1$ need not cause decline. For example, take $p_1=p_2=1/2$, $u_1=0.01$, $u_2=1.99$. Then $U=2$ but $g_{\ast }=(1/2)\log [0.25/(0.01\cdot 1.99)]>0$. For any fixed positive $p$, making one $u_j$ sufficiently small while preserving $U$ also makes the optimal rate positive.

Let $J_1,J_2,\dots$ be independent rolls with the specified probability distribution, and let $F_m$ be the fortune after $m$ games. Its multiplicative evolution givesby the strong law of large numbers. The summands have finitely many finite values, so its hypotheses hold. For any $\epsilon >0$, the probability that $f{e}^{m(g-\epsilon )}\le F_m\le f{e}^{m(g+\epsilon )}$ tends to one. Thus maximizing $g(a)$ maximizes the typical exponential growth rate, the objective of log-optimal multiplicative betting. Maximizing expected fortune would be a different objective and would not control the typical repeated-game outcome.

For probability distributions $p,q$ with positive entries, Gibbs inequality iswith equality exactly when $p=q$. Indeed, $\log x\le x-1$, with equality only at $x=1$, givesThis also proves the equality condition. With zero entries the same Kullback-Leibler divergence statement holds using $0\log (0/q)=0$ and $p\log (p/0)=+\infty$ for $p>0$, or by restricting to the support and taking limits.

Use the uniform probability measure on the symmetric group $S_n$ and the unnormalized Hamming distanceLet $f:S_n\to \mathbb{R}$ have Lipschitz constant $K>0$ for this distance. We will prove the one-sided concentration inequalitiesConsequently $\mathbb{P}(|f-\mathbb{E}f|\ge t)\le 2e^{-t^2/(2n{K}^2)}$ for $t>0$. A zero Lipschitz constant makes $f$ constant, so that case is immediate.

Let $\sigma$ be a uniform permutation, reveal $\sigma (1),\dots ,\sigma (k)$ successively, and define the Doob exposure martingaleFix the first $k-1$ images. For an available value $a$, let $h(a)$ be the conditional mean when $\sigma (k)=a$. Given two available values $a,b$, left-composition with the transposition exchanging $a,b$ is a bijection from completions with next image $a$ to completions with next image $b$. It fixes the previously exposed images and changes exactly two coordinates of each complete permutation. Since conditional completions are uniform, averaging the Lipschitz condition over this pairing gives $|h(a)-h(b)|\le 2K$.

Thus, conditionally on the first $k-1$ images, $M_k-M_{k-1}$ has mean zero and takes values in an interval of length at most $2K$. We need the range-length version of the Hoeffding lemma: if a real random variable $Z$ has mean zero and lies in an interval of length $\ell$, thenHere is a proof. For $\psi (\lambda )=\log \mathbb{E}{e}^{\lambda Z}$, differentiation gives ${\psi }^{\prime \prime }(\lambda )={\mathrm{Var}}_{\lambda }(Z)$ under the exponentially tilted probability distribution. Any distribution on an interval of length $\ell$ has variance at most ${\ell }^2/4$, because its squared distance from the interval midpoint is at most ${\ell }^2/4$. Since $\psi (0)={\psi }^{\prime }(0)=0$, integrating this second-derivative bound gives the lemma for both signs of $\lambda$. The same argument holds for every conditional distribution.

Apply it conditionally to each martingale difference and use the tower property of conditional expectation repeatedly:The exponential Markov bound now gives, for $\lambda >0$,Choose $\lambda =t/(n{K}^2)$ to obtain the upper tail in the box, and apply the argument to $-f$ for the lower tail. This proves concentration of Lipschitz functions on the symmetric group. Using only the bound $|M_k-M_{k-1}|\le 2K$ in the absolute-increment Azuma-Hoeffding inequality would lose a factor four in the exponent; the conditional range length is what yields the constant needed in part (ii).