Let be the final A set produced by the algorithm. It contains the initial A set, and every vertex outside has at most half its neighbours in : otherwise its final key would still be positive. Thus is closed under the activation rule.
Now consider any legal sequence, including sequences which change some A preferences back to B. We prove by induction that its current A set is always a subset of . This is true initially. A switch to B preserves the inclusion. If a vertex outside were to switch to A, its A neighbours would all lie in , so their number could not exceed half its degree. Such a switch is forbidden. A switch inside also preserves the inclusion.
Consequently every attainable final A set has size at most . The algorithm supplies a legal sequence attaining itself, so its sequence is optimal. This closure dominance for asynchronous threshold switching proves more than a local-greedy claim: temporary losses of A vertices cannot unlock an additional vertex outside the activation closure.
Only arrange switches towards A. For every vertex , compute its degree and the current number of neighbours preferring A. Put the B vertices in a max-heap with key . Maintain each vertex's current heap array index during exchanges.
While the queue is nonempty and its maximum key is positive, extract that vertex , show it its neighbours' preferences, append to the answer sequence, and set its preference to A. For every neighbour still preferring B, increase by one and use increaseKey to increase its heap key by two. Stop when every remaining key is nonpositive.
A positive key means precisely a strict majority of A neighbours, so every listed move is legal. Degrees never change; A neighbours never revert in this chosen sequence. An isolated B vertex has key zero and cannot be converted. Initialization costs , there are at most extractions, and each edge causes at most two neighbour inspections and at most a constant number of key updates. The required bound is therefore . A simple work queue of newly eligible vertices can even implement the same monotone threshold activation in time, since a vertex needs to be enqueued only once.
Leaves already obey the heap order. Process indices , calling the preceding repair at each. When an index is processed, its descendants have already been processed, so the repair's precondition holds. The resulting array is a max-heap.
The bound obtained by charging to every call is unnecessarily large. The number of nodes with height at least is at most . Therefore
The total repair work is thus , and the loop itself has a linear number of iterations, giving for this bottom-up heap construction. Most nodes are near the leaves and require little repair.
Assume the subtrees rooted at the children in a rooted tree of already obey the max-heap condition. Compare with each present child and choose an index of the largest of these at most three keys. If that index is , stop. Otherwise exchange the two keys, continue at the chosen child, and repeat. This is sift down, with the inequality reversed from a minimum-oriented binary heap.
The exchange repairs the old root position because its new key dominates both child roots; only the subtree receiving the displaced key can still be defective. This recursion invariant proves correctness. Each exchange descends one level and costs constant work, so the worst-case running time is for subtree height , hence . A small key at the root of a suitably ordered heap must descend to a leaf, so the logarithmic worst-case bound is attained.
Store a complete binary tree in a one-indexed array , level by level. Index has parent in a rooted tree for and possible children in a rooted tree and , present only when their indices are at most . The max-heap condition is for every .
Following these inequalities from the root of a tree to any entry proves that is a maximum. The heap order does not sort siblings or unrelated branches. The complete binary tree has height , which bounds how far any single repair can travel. Store the current heap size separately from the array's capacity.
Restrict the unknown function to the possibilities if , and otherwise. Each has exactly one essential variable, even if the allowed alphabet has more than two values. Every oracle answer in this restricted family is one bit.
A correct adaptive deterministic algorithm must distinguish all possibilities. A binary decision tree of depth has at most leaves, so . Therefore . Restricting the answer family is essential to the argument: unrestricted integer-valued answers need not have binary branching. Combined with part ii, this gives optimal logarithmic query complexity for fixed .
If , return its sole index without a query. Otherwise first evaluate for until two different outputs are found. Part i says these outputs are precisely , so two values with must exist. This uses at most calls to the function-evaluation oracle.
Maintain a candidate index set , initially all indices. Split into two nearly equal pieces and choose one, . Query the input that is on and everywhere else. Its output equals exactly when , and otherwise equals . Retain the indicated half and repeat until one index remains.
The loop invariant is , and the witness outputs keep each test unambiguous. There are at most splitting queries. The total is at most evaluations, which is for , and in fact a stronger additive bound. Only oracle calls are being counted; explicitly constructing each query vector can require ordinary work. This is identification of a unique essential variable.
If coordinate is not an essential variable of a function, changing that coordinate alone never changes the output, for any values of the other coordinates. Take two inputs with the same -th coordinate. Change their other coordinates one at a time to transform the first input into the second. Every such change is inessential, so all intermediate outputs are equal.
Define , with in position . The preceding argument gives . Since is essential, is nonconstant. The conclusion depends on the full “for every context” negation of essentiality, not merely on testing a coordinate at one selected input.
Represent the removed half as the first cards in a uniformly random ordering. Every unordered half is then equally likely. Let be their values. Each has mean zero and variance one, and every distinct pair has covariance by the same ordered-pair argument as in (ii).
The general covariance expansion from (b), applied without imposing independence, gives
This is the finite population correction for a half-sample; treating the draws as independent would give the wrong variance.
Finally , so Chebyshev's inequality yields
The cards returned before this sampling step restore the original population; no conditioning on the earlier two observed values is imposed.
Every particular card is second with probability
Hence and have the same distribution, with means zero and variances one. They are not independent, since a card cannot be drawn twice.
Every ordered pair of distinct cards has probability . Therefore
This negative covariance is the effect of sampling without replacement, not a contradiction of their identical marginals.
Write the card values as . Uniform selection gives
Thus and , by the variance identity .
**Chebyshev's inequality: if has finite mean and variance , then for ,
Apply Markov's inequality to the nonnegative random variable with threshold . Since and , the desired statement follows immediately.
Markov's inequality: if and , then . Pointwise,
Taking expected values, using their monotonicity and the identity , gives . Division by the positive threshold proves the inequality. If the expectation is infinite, the extended-valued bound remains true but uninformative.
Differentiate the probability generating function equation:
At , , giving
The derivative is finite because and the explicit square root has no singularity at . Alternatively, the expected population in generation is , so the expected number of splits in that generation is . Summing this nonnegative geometric series gives the same answer without initially assuming a finite expected value.
If the initial individual has no offspring, . If it splits, count that one event and the splitting events in its two independent descendant trees. Thus
where are independent copies of . Taking the probability generating function gives
For , the quadratic equation has two algebraic branches. A probability generating function must remain finite at , where it equals , so the admissible branch is
The rationalized formula is also defined directly at zero. At , , so , consistent with almost-sure finiteness. Extinction occurs after a finite number of generations almost surely, and each generation is finite, which justifies that finiteness claim for the number of splitting events in a binary branching process.
This is a Galton-Watson process with offspring count with probability and with probability . The descendants of distinct initial individuals evolve independently, so
for every finite initial size . Conditioning on the first individual's outcome and applying the law of total probability gives
The equation factors as
Its roots are and . Since , the second root exceeds one and cannot be a probability. Therefore and for every finite initial size. The population reaches the absorbing state zero almost surely; no choice between two admissible fixed-point probabilities remains in this subcritical case.
Let denote the selected die. Bayes' theorem gives
Only the first roll is conditioned on here; the second outcome has not been observed.
The two outcomes are not independent. Conditional on the selected die, the rolls are independent, but sharing the unknown die creates statistical dependence. Each nonfavored face has probability .
The unconditional marginal distribution assigns the following probability to a on either roll:
However, by the law of total probability,
Thus the joint probability does not factor into the two marginals. Conditional independence given a shared latent choice does not imply unconditional independence.
Let be the indicator that black bead belongs to the white bead's connected component. The number of such black beads is . By linearity of expectation, no independence between these indicators is needed.
For , the six oriented distances give respective probabilities
Their sum is , the expected number of black beads in the white component. As a check, summing the formula from (i) and using gives the general value , again equal to when .
View the necklace as a cycle graph. Between the white bead and there are two edge-disjoint paths, containing and links. The beads remain connected if and only if at least one of these paths is uncut.
There are equally likely cut sets. Keeping the -link path uncut requires all three cuts to be among its complementary links, giving choices. Keeping the other path uncut gives choices. These two events are disjoint because three links are cut and they cannot all lie in both complementary paths. Therefore
Use for . The answer is unchanged by exchanging and , so either orientation around the necklace gives the same value. This is the connectivity calculation for random cuts of a cycle.

There are unlisted articles, also show them or only show them.