CSE347 Analysis of Algorithms (Lecture 11)

More randomized algorithms

Caching problem: You have a cache with $k$ blocks and a sequence of accesses, called $\sigma$ . The cost of a randomized caching algorithm is the expected number of cache misses on $\sigma$ .

Randomized Marking Algorithm

A phase $i$ has $n_i$ new pages.

Our goal is to optimize $m^*(\sigma)\geq \frac{1}{2}\sum_{i=1}^{n} n_j$ where $n_j$ is the number of new pages in phase $j$ .

Marking algorithm:

at a cache miss, evict an unmarked page uniformly at random
at the beginning of the algorithm, all the entries are unmarked
after $k$ unique accesses and one miss, all the entries are unmarked
old pages: pages in cache at the end of the previous phase
new pages: pages accessed in this phase that are not old.
new pages always cause a miss.
old pages can cause a miss if a new page was accessed and replaced that old page and then the old page was accessed again. This can also be caused by old pages replacing other old pages and creating this cascading effect.

Reminder: Competitive ratio for our randomized algorithm is

max_\sigma \{\frac{E[m(\sigma)]}{m^*(\sigma)}\}


def randomized_marking_algorithm(sigma, k):
    cache = set()
    marked = set()
    misses = 0
    for page in sigma:
        if page not in cache:
            # once all the blocks are marked, unmark all the blocks
            if len(marked) == k:
                marked.clear()
            # if the cache is full, randomly remove a page that is not marked
            if len(cache) == k:
                for page in cache:
                    if page not in marked:
                        cache.remove(page)
            misses += 1
            # add the new page to the cache and mark it
            cache.add(page)
            marked.add(page)
    return misses

Example:

A cache on phase $i$ has $k$ blocks and miss on page $x$ :

[ $n_i$ new pages] [ $o_i$ old pages] [ $x$ ] [ $\ldots$ ]

$P[x \text{ causes a miss}] = P[x\text{ was evicted earlier}] \leq \frac{n_j}{k-o_i}$

Proof:

Warning: the first few line of the equation might be wrong.

\begin{aligned} P\left[x \text{ was evicted earlier}\bigg\vert\begin{array}{c} n_j\text{ new pages}, \\ o_i\text{ old pages}, \\ k \text{ unmarked blocks} \end{array}\right] &=P[x\text{ was unmarked}]+P[x\text{ was marked}] \\ &=P[x\text{ was unmarked (new page)}]+P[x\text{ was old page}]+P[x\text{ was in the remaining cache blocks}] \\ &= \frac{1}{k}+\frac{o_i}{k} P\left[x \text{ was evicted earlier}\bigg\vert\begin{array}{c} n_j-1\text{ new pages}, \\ o_i-1\text{ old pages}, \\ k-1 \text{ unmarked blocks} \end{array}\right] +\frac{k-1-o_i}{k} P\left[x \text{ was evicted earlier}\bigg\vert\begin{array}{c} n_j-1\text{ new pages}, \\ o_i\text{ old pages}, \\ k-1 \text{ unmarked blocks} \end{array}\right] \\ \end{aligned}

Let $P(n_j, o_i, k)$ be the probability that page $x$ causes a miss when the cache has $n_j$ new pages, $o_i$ old pages, and $k$ unmarked blocks.

Using $P(n_j, o_i, k)\leq \frac{n_j}{k-o_i}$ , we have

\begin{aligned} P(n_j, o_i, k) &= \frac{1}{k}+\frac{o_i}{k} P(n_j-1, o_i-1, k-1)+\frac{k-1-o_i}{k} P(n_j-1, o_i, k-1) \\ &\leq \frac{1}{k}+\frac{o_i}{k} \frac{n_j-1}{k-1-o_i-1}+\frac{k-1-o_i}{k} \frac{n_j-1}{k-1-o_i} \\ &= \frac{1}{k}+\left(1+\frac{o_in}{k-o_i}+\frac{n_j-1}{k-o_i}\right)\\ &=\frac{1}{k}\left(\frac{k-o_i+o_in+(n_j-1)(k-o_i)}{k-o_i}\right)\\ &= \frac{n_j}{k-o_i} \end{aligned}

Fix a phase $j$ , let $x_i$ be an indicator random variable

x_i=\begin{cases} 1 & \text{if page } i \text{th old page causes a miss} \\ 0 & \text{otherwise} \end{cases}

\begin{aligned} P[x_i=1]&=P[i\text{th old page causes a miss}]\\ &\leq \frac{n_j}{k-(i-1)}\\ \end{aligned}

\begin{aligned} E[x_i]&=E[\sum_{i=1}^{o_i} P[x_i=1]]\\ &= E[n_j+\sum_{i=1}^{k-n_j}x_i]\\ &=n_j+\sum_{i=1}^{k-n_j} E[x_i]\\ &\leq n_j+\sum_{i=1}^{k-n_j} \frac{n_j}{k-(i-1)}\\ &=n_j+\left(1+\frac{1}{k}+\frac{1}{k-1}+\cdots+\frac{1}{n_j}\right)\\ &\leq n_j H_k\\ \end{aligned}

Let $N$ be the total number of phases.

So the expected total number of misses is

E[\sum_{i=1}^{N} x_i]\leq \sum_{i=1}^{N} E[x_i]\leq\sum_{j=1}^{N} n_j H_k

So the competitive ratio is

\frac{E[\sum_{i=1}^{N} x_i]}{\frac{1}{2}\sum_{j=1}^{N} n_j}\leq 2H_k=O(\log k)

Probabilistic boosting for decision problems

Assume that you have a randomized algorithm that gives you the correct answer with probability $\frac{1}{2}+\epsilon$ . for some $\epsilon>0$ .

I want to boost the probability of the correct decision to be $\geq 1-\delta$ .

What we can do is to run the algorithm $x$ times independently with probability $\frac{1}{2}+\epsilon$ and take the majority vote.

The probability of the wrong decision is

\binom{x}{\lceil x/2\rceil} \left(\frac{1}{2}-\epsilon\right)^{\lceil x/2\rceil}

I want to choose $x$ such that this is $\leq \delta$ .

$(1-p)^{\frac{1}{p}}\leq e^{-1}$

\begin{aligned} \binom{x}{\lceil x/2\rceil}\left(\frac{1}{2}-\epsilon\right)^{\lceil x/2\rceil}&\leq \left(\frac{xe}{x/2}\right)^{\lceil x/2\rceil}\left(\frac{1}{2}-\epsilon\right)^{-\lceil x/2\rceil\epsilon} \end{aligned}

We use this to solve for $x$ .