Probabilistic Analysis and Randomized Algorithms

Depends on probabilistic outcomes $\to$ we get expected bounds
Assumption: uniformly random input - randomization to avoid “bad” input sequences
Indicator random variable: $I(A)=1$ if event $A$ occurs, otherwise $I(A)=0$
Sample space $S$, event $A$, $X_A=I(A)⟹E(X_A)=P(A)$

Example

Compute expected number of heads in $n$ tosses of a fair coin
$X_i=I(thei-thflipresultedinheads)$ … indicator random variable that H appeared in toss $i$
$X={\sum }_{i=1}^n{X}_i$ … number of heads in $n$ flips

$$E(X)=E(\sum _{i=1}^n{X}_i)=\sum _{i=1}^n\ast E(X_i)=\sum _{i=1}^n\frac{1}{2}=\frac{n}{2}$$

Pseudo-random numbers

Hardware RNG
Pseudo RNG: initialized with seed $\to$ get a large repeatable “random” number sequence

Linear congruential generators

$x_i=(a\ast x_{i-1}+c)modp$ ; $p$ … period
$u_i=\frac{x_i}{m}$ ; $m$ … maximum
Simbple but bad - if current number is small, then the next will also be small

BBS

$x_i=x_{i-1}^{2}modm$ ; $p$,$q$ … large prime numbers, $m=pq$
If you find the primes you can reverse engineer generation (only on quantum computers in polynomial time)

Amortized analysis of computational complexity

Aggregated analysis

Aggregate all possible functions

Stack with multipop operation

$n$ operations of PUSH, POP - worst case per operation: $\frac{n\ast \Theta (1)}{n}=\Theta (1)$
$n$ operations of PUSH, POP, MULTIPOP - worst case per operation: $\frac{n\ast k}{n}=O(k)$
$n-1$ operations of PUSH, then MULTIPOP(n-1) - worst case per operation: $\frac{2n-1}{n}=O(1)$

Accounting method

Assessing worst-case upper bound for a series of $n$ operations
Amortized cost $c_i^{\prime }$ $\ge$ actual cost $c_i$ $⟹$ ${\sum }_{i=1}^n{c}_i^{\prime }\ge {\sum }_{i=1}^n{c}_i$

• found upper bound for amortized cost $\ge$ upper bound for actual cost

Stack with multipop operation

Each PUSH/POP costs 1 coin; if you put $2$ coins all push, all possible future pops are already paid for

| operation | actual cost | amortized cost |
| ---------- | --------- | --- |
| PUSH | $1$ | $2$ |
| POP | $1$ | $0$ |
| MULTIPOP | $min(k,s)$ | $0$ |
$n$ operations of PUSH - worst case: ${\sum }_{i=1}^n{c}_i^{\prime }={\sum }_{i=1}^{n}2=2n$
Worst case per operation: $\frac{2n}{n}=2=O(1)$

Potential method

Data structure $D$ has a “potential” $\Phi$ that pays for more expensive operation

• $D_i$ … $D$ after operation $i$ applied to $D_{i-1}$
• $c_i^{\prime }={\sum }_{i=1}^n{c}_i+\Phi (D_n)-\Phi (D_{i-1})$ … amortized cost

Stack with multipop operation

$\Phi$ … number of elements on the stack

• $\Phi (D_0)$ … assume empty stack
• $\Phi (D_i)$ … number of elements on the stack after operation $i$

| operation | actual cost | $\Delta \Phi$ | amortized cost |
| ---------- | --------- | --- | --- |
| PUSH | $1$ | $(num+1)-num=1$ | $1+1=2$ |
| POP | $1$ | $(num-1)-num=-1$ | $1-1=0$ |
| MULTIPOP | $min(k,s)=k^{\prime }$ | $(num-k^{\prime })-num=-k^{\prime }$ | $min(k,s)-k^{\prime }=0$ |

Worst sequence of $n$ operations: ${\sum }_{i=0}^n{c}_i^{\prime }={\sum }_{i=0}^{n}2=2nWorstcaseperoperation:$\frac{2n}n=2=O(1)$