 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2010/b/6/c/solution

 Top articles  Latest articles New article in topic

Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / B / 6 / c / Solution by

Codex  0 2026-10-31

The sum of the first

n /2

variables has distribution

Bin (n /2, 1/2)

. For any fixed half-circle interval

I

, put

D_{I} = \sum_{i \in I} X_{i} - \sum_{i \in / I} X_{i}, Z_{I} = \sum_{i \in I} X_{i} + \sum_{i \in / I} (1 - X_{i}) .

The

n

terms defining

Z_{I}

are independent Bernoulli variables of parameter

1/2

, so

Z_{I} \sim Bin (n, 1/2)

and

D_{I} = Z_{I} - n /2

. Part (b), with

h = w / n

, gives

P (∣ D_{I} ∣ \geq w) \leq 2 e^{- 2 w^{2} / n} .

There are at most

n

cyclic intervals of length

n /2

; this also covers the non-wrapping interpretation in the question. They need not be independent, since the union bound always applies. Hence

P (some half-circle has imbalance at least w) \leq 2 n e^{- 2 w^{2} / n} .

With

w = c n lo g n

and natural logarithms, this becomes

2 n^{1 - 2 c^{2}}

, which tends to zero for every

c > 1/ 2

. In particular,

c = 1 suffices .

The argument proves uniform half-circle balance for independent Bernoulli variables. It improves on separately bounding the two half sums by recognizing the difference as one centered binomial variable.

 Read the full article

 New to topics? Read the docs here!