False. Take edges $u\to a$ and $c\to u$, and let the outer DFS loop try vertices in order $a,u,c$. The first call finishes $a$ immediately. The next discovers $u$, whose only outgoing edge reaches already black $a$, so its tree contains only $u$. Finally $c$ sees already black $u$.

Vertex $u$ has both an incoming edge from $c$ and an outgoing edge to $a$, yet is the sole vertex of its DFS tree. Nonzero incoming and outgoing degrees do not require either edge to become a tree edge in depth-first search.

True for a directed cycle. Suppose there were no back edges. On examining an edge $u\to v$, its target would either be white, in which case its recursive call finishes before $u$; or black, in which case it has already finished. A gray target would be an active ancestor and hence give a back edge, contrary to the supposition. Therefore every edge would satisfy $f(v)<f(u)$.

Applying those strict inequalities around a directed cycle would imply $f(u)<f(u)$, a contradiction. Thus some back edge in depth-first search must exist in the search's edge classification. Such an edge is classified relative to the DFS forest; it is not one of the forest's tree edges.

False. The same ordered traversal gives a path $u\to x\to v$, butA path from $u$ can pass through an already discovered ancestor, whose remaining edges are scanned only after $u$ finishes. A reachability statement alone therefore does not impose the claimed finishing-time bound.

False. Use vertices $x,u,v$, edges $x\to u$, $u\to x$, $x\to v$, and start depth-first search at $x$, scanning $u$ before $v$. The times areThere is a directed path $u\to x\to v$ and $d(u)<d(v)$, but $u$ and $v$ are separate children of $x$. Thus $v$ is not a descendant of $u$. The path leaves $u$ through an already gray ancestor; its later branch need not be explored inside $u$'s recursive call. This is consistent with the DFS parenthesis property.

The normalized sum has mean one and variance $(5n-2)/n^2$. For every fixed $ϵ>0$, the Chebyshev inequality givesThis proves the requested limit, and in fact proves convergence in probability of $S_n/n$ to one. It is a finite covariance range weak law: adjacent dependence is harmless here because only linearly many covariance terms survive.

Put $Z_i=Y_{i-1}{Y}_i$ for $1\le i\le n$. Independence of the underlying exponentials gives $\mathbb{E}{Z}_i=1$ andBy the covariance of overlapping independent products, adjacent terms have covariance one. Terms separated by at least two indices use disjoint independent factors, so their covariance is zero. There are $n-1$ adjacent pairs. Linearity of expectation and the variance of a sum formula therefore yieldIn particular, the products themselves are not independent merely because the original $Y_i$ are.

For finite second moments, the general variance of a sum formula isEach distinct unordered pair appears once in the second sum and twice when the full square is expanded. No independence assumption is needed.

Assume finite second moments and write $Z_i=X_i-\mathbb{E}{X}_i$. Expanding the squared centered sum givesThis variance of a sum identity does not require independence; the covariance term records the contribution that would otherwise be lost.

For the overlapping products, factor using the independence of $T,U,V$:This is the covariance of overlapping independent products: the shared $U$ contributes its second moment. In contrast, $TU$ and $VW$ use disjoint independent factors and are themselves independent, giving

Because $T$ and $U$ are independent random variables, their product's expected value factors:The original independence assumption is essential to this factorization.

The rate-one exponential distribution has density $e^{-t}$ for $t\ge 0$. Integration by parts gives $\mathbb{E}T=1$ and $\mathbb{E}[T^2]=2$, so

The Markov property and time homogeneity giveSince $p_{2n}>0$, conditional probability yields the Markov chain return bridge expressionThe explicit formula gives $p_n\sim \frac{3}{4}(3/4{)}^n$, soThe conditioning event has positive probability at each finite time even though those return probabilities tend to zero. Taking an undefined conditional on an infinite-time zero-probability event is not needed.

The initial values are $p_0=1$ and $p_1=1/2$. The characteristic polynomial of the linear recurrence iswith roots $3/4$ and $-1/4$. Hence $p_n=a(3/4{)}^n+b(-1/4{)}^n$. The initial conditions give $a+b=1$, $3a-b=2$, so $a=3/4$, $b=1/4$. Therefore

Let $q_j=\mathbb{P}(M_j=Y)$. By the law of total probability,There is no return contribution from the absorbing state $Z$. Since $Y$ can be entered only from $X$, $q_{n-1}=\frac{1}{2}{p}_{n-2}$ for $n\ge 2$. Substitution yieldsNo independence between successive positions is assumed; the conditional transitions give the recurrence.

Starting at $X$, the two possible two-step returns are $X\to X\to X$ and $X\to Y\to X$. They are disjoint events, with probabilities $1/4$ and $3/16$. ThereforeEach path probability uses the specified Markov property to multiply its successive transition probabilities.

For a finite or countable measurable partition, the law of total probability isIndeed, $A$ is the disjoint union of $A\cap B_i$, and the conditional probability formula gives each positive-probability term. Zero-probability cells contribute zero; their conditionals need not be defined by a ratio. If all cells have positive probability, the sum simply runs over every $i\in I$.

A partition of a set consists of nonempty subsets that are pairwise disjoint and whose union is the whole set. HereThus every outcome belongs to exactly one cell. The probability calculation additionally requires the cells to be measurable events.

For $Y\sim \mathrm{Geom}(p)$, its mean is $1/p$, so the size-biased probability generating function isChoose $X_1,X_2$ independent with distribution $\mathrm{Geom}(p)$. Their shifted sum has generating function, initially for $s>0$,with both sides continuous and zero at $s=0$. Equality of probability generating functions provesEquivalently, $X_1+X_2=k+1$ has $k$ possible positive summand pairs, each of probability $p^2(1-p{)}^{k-1}$, matching the size-biased geometric distribution probabilities.

For $0\le s<1$, differentiate the probability generating function term by term and multiply by $s/\mu$:This is the size-biased probability generating function identity. At $s=1$, the finite-mean assumption gives the limiting value one on both sides; at zero, positive support gives value zero.

Since $Y\ge 1$, its finite expected value satisfies $1\le \mu <\infty$. Every $q_k=k{p}_k/\mu$ is nonnegative andThus these values are a probability mass function. They define the size-biased distribution of $Y$: larger values receive proportionally more weight.