Bernoulli Process, LLN, CLT and Combinatorial Connections

1. Bernoulli process and binomial

\[ X_1,X_2,\dots \overset{\text{iid}}{\sim} \mathrm{Bernoulli}(p),\qquad S_n=\sum_{i=1}^{n} X_i\sim\mathrm{Binom}(n,p). \]
\[ \mathbb{E}[S_n]=np,\qquad \mathrm{Var}(S_n)=np(1-p). \]

2. Law of Large Numbers (LLN)

\[ \overline{X}_n=\frac{S_n}{n}=\frac{1}{n}\sum_{i=1}^n X_i \xrightarrow{a.s.} \mathbb{E}[X_1]=p. \]

Statement (strong): for iid \(X_i\) with \(\mathbb{E}[|X_1|]<\infty\), \(\frac{1}{n}\sum_{i=1}^n X_i \xrightarrow{a.s.} \mathbb{E}[X_1]\). In the Bernoulli case this means that, for almost every realization, the sample mean converges to \(p\) as \(n\) grows.

3. Central Limit Theorem (CLT)

\[ \sqrt{n}\,(\overline{X}_n - p) \xrightarrow{d} \mathcal{N}\big(0,\;p(1-p)\big).

CLT: for iid \(X_i\) with mean \(\mu\) and variance \(\sigma^2\), \(\sqrt{n}(\overline X_n - \mu)\xrightarrow{d} N(0,\sigma^2)\). In the Bernoulli case \(\mu=p\), \(\sigma^2=p(1-p)\).

4. Pascal's triangle, binomial expansion and Fibonacci

\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k},\qquad (a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k. \]
\[ F_n=\sum_{i=0}^{\lfloor (n-1)/2\rfloor} \binom{n-1-i}{i}. \]

The Fibonacci identity shows how summing appropriate diagonals of Pascal's triangle yields terms of the Fibonacci sequence. The binomial expansion connects combinatorial coefficients to probabilities in the Bernoulli model by taking \(a=1-p\), \(b=p\).

5. Interactive demos: LLN, Binomial and CLT

Curves: sample means \(\overline X_k\) for several paths. Dashed line = theoretical value \(p\).
Bars: empirical frequencies of \(S_n\). Line: theoretical \(\mathrm{Binom}(n,p)\) probabilities.
Histogram of \(\sqrt{n}(\overline X_n - p)\) with the theoretical density \(\mathcal{N}(0,p(1-p))\) overlaid.

6. Formal comparison and analogies with the previous assignment

Objective

This paragraph relates the current exercise to the previous assignment (where the effective success probability per trial was \(q=(1-p_{\text{attacker}})^m\)). It highlights analogies, differences and the relevant combinatorial remarks.

1. General perspective: pathwise vs. ensemble

In both assignments the fundamental unit is the Bernoulli trial with a fixed success probability (in the previous assignment \(q\), here \(p\)). Two complementary perspectives:

  • Pathwise (LLN): follow a single realization and observe the sample mean \(\overline X_k\). The LLN guarantees that, for almost every path, \(\overline X_n\to p\) (or \(\to q\)).
  • Ensemble (Binomial): repeat the entire experiment of fixed length \(n\) many times and build the empirical distribution of \(S_n\). This distribution is governed by the binomial PMF \[ P(S_n=k)=\binom{n}{k}p^k(1-p)^{n-k}, \] with \(p\) replaced by \(q\) in the previous assignment.

2. Substitution \(p \mapsto q\)

All formulas and theorems transfer by substituting \(p\) with \(q=(1-p_{\text{attacker}})^m\). In particular: \[ S_n\sim\mathrm{Binom}(n,q),\quad \mathbb{E}[S_n]=nq,\quad \mathrm{Var}(S_n)=nq(1-q), \] and \[ \overline X_n \xrightarrow{a.s.} q,\qquad \sqrt{n}(\overline X_n - q)\xrightarrow{d}\mathcal{N}(0,q(1-q)). \] This shows that the difference between the two assignments is mainly numerical (the value of the probability) rather than structural.

3. Combinatorial relations and the role of Pascal

The recursive relation for binomial coefficients \[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} \] builds Pascal's triangle; the binomial expansion \[ (1-p + p)^n = \sum_{k=0}^n \binom{n}{k}(1-p)^{n-k} p^k = 1 \] directly links combinatorial coefficients to binomial probabilities. Sums along diagonals of Pascal produce, among other things, the Fibonacci sequence: \[ F_n=\sum_{i=0}^{\lfloor (n-1)/2\rfloor} \binom{n-1-i}{i}. \] Adding a graphic panel (Pascal with highlighted diagonals) is useful relative to the combinatorial part of the exam.

4. Practical interpretation and suggestions for the report

  1. Include figures: (A) paths of \(\overline X_k\) with dashed line \(p\) (or \(q\)); (B) bar chart of the empirical distribution of \(S_n\) with the theoretical \(\mathrm{Binom}(n,p)\) curve overlaid (or \(\mathrm{Binom}(n,q)\)); (C) histogram of \(\sqrt{n}(\overline X_n-p)\) with the theoretical normal density; (D) annotated Pascal triangle to illustrate Fibonacci.
  2. Always report experimental parameters: \(n\), \(p\) (or \(q\)), number of paths \(m\), number of repetitions \(R\) for empirical estimates, and number of bins for histograms.
  3. Discuss finite-sample discrepancies: Monte Carlo error, skewness for \(p\) far from 0.5, accuracy of the normal approximation as \(n\) grows (rate \(O(1/\sqrt{n})\)).
  4. In the text explicitly state the substitution \(p\mapsto q\) when comparing to the previous assignment and comment on the numerical results in that context.

Conclusion. The current exercise is directly reducible to the previous one via the substitution of the success probability; the combinatorial connections (binomial coefficients, Pascal, binomial expansion and Fibonacci) provide a coherent mathematical framework that justifies the empirical observations shown in the demos.

7. Pascal's Triangle and Fibonacci (tool)

—

References

  1. W. Feller, An Introduction to Probability Theory and Its Applications, Vol.1.
  2. P. Billingsley, Probability and Measure.
  3. G. Graham, D. Knuth, O. Patashnik, Concrete Mathematics.