At least one child is at least this average. Choose achild with the larger value, using a fixed rule for ties. The resulting loop invariant is q(P)≥EZ. At a complete assignment x, there is only one completion left, so q(x)=Z(x) and therefore Z(x)≥EZ.
In the two-environment example of conditional independence, g(T) is 0.1 or 0.9 with equal probabilities. Hence E[g(T)]=0.5 and Var(g(T))=((0.1−0.5)2+(0.9−0.5)2)/2=0.16. The two trials have zero conditional covariance in either environment, yet their unconditional covariance is positive because their success probabilities rise and fall together.
Compare T±2=inf{n≥0:∣Sn∣=2}. From every surviving position in {−1,0,1}, three consecutive positive incrementsforce absorption within three steps. Each fresh block has probability1/8 of this event, so P(T±2>3k)≤(7/8)k and E[T±2]≤24. This establishes finiteness before invoking the theorem. If ej is the average remaining time from position j, the law of total expectation gives
The figure makes the two sources of spread visible. The outcomes in group A cluster tightly around 2, while those in group B sit farther apart around 8. Replacing every outcome by its conditional mean removes the internal spread but leaves the separation between groups. Conversely, subtracting each group's conditional mean aligns the two groups around zero. Averaging only the conditional variances would miss nine units of variance; retaining only the conditional means would miss five. Neither summary alone describes the whole population.
Two modifications clarify what each contribution measures. Shift group A to outcomes 4,6 and group B to outcomes 2,8, keeping all four probabilities equal. Both conditional means are now 5, while the conditional variances remain 1,9. The between-group contribution vanishes, and total variance is just 5. Group membership still tells us how uncertain an outcome is, even though the best point prediction stays the same. Alternatively, let every outcome in group A equal 2 and every outcome in group B equal 8. Now both conditional variances vanish, and all nine units of total variance come from group separation. Knowing the group predicts the outcome perfectly. These limiting cases distinguish differences in average outcome from differences in internal spread; the original mixture distribution contains both.
There is no proof of the printed assertion: it is false for the stated expectations. The original explicitly defines xjas the expected remaining count, so replacing it by a deterministic upper envelope changes the problem.[ref]
For an exact counterexample, start with two balls and two bins. A round serves both balls if they land separately and serves neither if they collide. Each outcome has probability1/2, independently in successive rounds while both balls remain. Consequently
Indeed 2jintended(n)−2≥log2n, so that bound would give xj(n)≤n2−log2n=1. Its growth is O(loglogn) in Big O notation. Because (c) is false, this substitution alone does not prove the result for the actual repeated singleton-removal allocation.
The requested order can nevertheless be established for the actual process. Here is a concrete, deliberately generous replacement, with j(0)=0 for the empty system:
Thus part (a) gives E[Bt+1∣Bt]≤2Bt/3, also for Bt≤1. The law of total expectation yields xt≤n(2/3)t. This proves xj(n)≤1/2 for the small-n branch, including n=1, whose single ball is served immediately.
For the large-n branch, we need control of the random count, rather than an unjustified recurrence for its expectation. If b balls are allocated in a round, changing one chosen bin changes the number of singleton bins by at most two. The surviving count Fb therefore has the bounded differences property with constants 2. McDiarmid's inequality gives
For the first eight rounds, whenever b>n3/4, the conditional expectation is at most 2b/3. Taking u=b/12 shows that the next count is at most 3b/4, except with probability at most e−b/288. If the count has already fallen below n3/4, it stays there. Since (3/4)8<1/8 and n3/4≤n/8, this gives B8≤n/8 outside the stated exceptional events.
Starting with a0=n/8, set ar+1=2ar2/n. If B≤ar and ar≥n3/4, part (a) and the union bound give EFB≤ar2/n. Taking u=ar2/n gives a next count at most ar+1, except with probability at most e−ar3/(2n2)≤e−n1/4/2. The deterministic solution is ar=(n/2)4−2r. It falls below n3/4 within L steps. After reaching that threshold the count cannot increase, so B8+L≤n3/4 outside the exceptional events.
From b≤n3/4, the next conditional expectation is at most n1/2. A deviation u=n1/2leaves at most 2n1/2 balls except with probabilitye−n1/4/2. From at most 2n1/2 balls, the next conditional expectation is at most 4. Taking u=n1/3−4≥n1/3/2leaves at most n1/3 balls except with probabilitye−n1/6/16. Conditional on this final count bound, one more round has expectation at most n−1/3.
Every exceptional probability above is at most e−n1/6/300, and there are at most L+10 opportunities for an exception. For n≥2120, the elementary bounds n1/6/300≥4lnn and L+10≤n give, by the union bound, total exceptional probability at most n−3. The first numerical inequality holds at the cutoff and remains true because n1/6/lnn is increasing there. On an exceptional history there are at most n balls. Taking the last round's conditional expectation and then averaging gives
Order the edges arbitrarily and fix their colours one at atime. After a partial assignment P, regard all unassigned edgesas independent fair red/blue choices, and compute
qA(P)=⎩⎨⎧0,2−r,21−r=1/32,both colours already occur among its fixed edges,at least one edge is fixed, all in the same colour,none of its six edges is fixed.
In the second case, every remaining edge must match the already fixed colour; this includes a completely fixed monochromatic copy, for which r=0 and the contribution is one. In the last case, the six unassigned edges may become either all red or all blue. By linearity of expectation,
Choose the colour with the smaller value, resolving a tie by a fixed rule. At least one is at most their average, so the loop invariant is that Q never increases. Initially Q=(4n)/32; once every edge is fixed, there is no randomness left and Q=Z. Therefore the method of conditional expectations guarantees
Condition on the number of floods and apply the same laws once more. All floods have these moments and are independent of M, so the annual total satisfies
The additional νλ2μ2 term is the variation in the number of entire flood clusters; it would be lost by treating individual claims as an ordinary Poisson stream.
so Poisson thinning gives Ki∼Poisson(λ(1−p)). With validity independent also of claim amount, each claim contributes expected paid amount (1−p)μ. Therefore the annual expected payment is νλ(1−p)μ. The independent-mark assumption is needed for this multiplication; asize-dependent invalidity rule would require the joint expected value of amount and validity instead.
For fixed a>0,n, ∂Z/∂v=−na/(na+v)2<0. Thus more within-riskvariation decreases credibility: individual experience becomes less informative, Z→0as v→∞, and the premium tends to m. Increasing the number of observed years has the opposite effect.
For numerical estimation from a balanced panel, assume the krisks are independent draws from the same riskpopulation, with comparable exposures, and n,k≥2. Set
If a=0 and v>0, use zero credibility. If both estimates are zero, the within and between sums of squares are zero and all the observed amounts coincide; any blend gives that same premium. With only one year per risk or only one risk, these within/between estimators are unavailable, so external structural estimates or additional assumptions are necessary.
The two tails are equal. The binomial representation replaces an infinite sum by a finite exact calculation, eliminating the need to choose aclaim-counttruncation and control its omitted tail. The inner sums can be evaluated recursively, using aj+1=aj(pλx)/(j+1) for their exponential-weighted terms.