first moment method

[[concept]]

Topics

const fieldName = "theme"; // Your field with links
const oldPrefix = "Thoughts/01 Themes/";
const newPrefix = "Digital Garden/Topics/";
 
const relatedLinks = dv.current()[fieldName];
 
if (Array.isArray(relatedLinks)) {
    // Map over the links, replace the path, and output only clickable links
    dv.el("span",
        relatedLinks
            .map(link => {
                if (link && link.path) {
                    let newPath = link.path.startsWith(oldPrefix)
                        ? link.path.replace(oldPrefix, newPrefix)
                        : link.path;
                    return dv.fileLink(newPath);
                }
            })
            .filter(Boolean).join(", ") 
	// Remove any undefined/null items
    );
} else {
    dv.el(dv.current().theme);
}
 
 

The proof of the Johnson-Lindenstrauss lemma applies the union bound to show that the probability of $\hat{G}$ being pairwise faithful is high. This turns out to be a very powerful tool if we can carefully choose our events.

If we want to bound the probability of a “bad” event, we can decompose it into $E=E_1\cup E_2\cup \cdots \cup E_N$ and bound it as $\mathbb{P}[E]\le {\sum }_{i=1}^N\mathbb{P}[E_i]\le N\cdot {\max }_i\{\mathbb{P}[E_i]\}$ Often, for a well-chosen set of $E_i$, the $\mathbb{P}[E_i]$ are about the same. If $N$ is large and $\mathbb{P}[E_i]$ is very small, we can often see a bound with an exponential scale (like we did in the proof)

This approach is sometimes called the first moment method because we may write

\mathbb{P}[\text{ some }E_{i}\text{ occurs }] &= \mathbb{P}\left[ \sum_{i=1}^N \mathbb{1}_{\{ E_{i} \} }\geq 1\right] \\ &\leq \mathbb{E}\left[ \sum_{i=1}^N \mathbb{1}_{\{ E_{i} \}}\right] \\ &= \sum_{i=1}^N \mathbb{P}[E_{i}] \end{align}$$ which we get from [[Concept Wiki/Markov's Inequality]]. Here, we compute the expectation or *first moment* of the random variable $\#E = \lvert \{ i: E_{i} \text{ occurs} \} \rvert$. > [!NOTE] > > There is also the "second moment method" which involves computing the second moment of $\#E$. This method is usually used to show that some $E_{i}$ *does* occur with high probability. > > > [!example] > > > > If $d$ is too small, then $\hat{G}$ is *not* pairwise $\varepsilon$-[[Concept Wiki/epsilon faithful function\|faithful]]. > # References >[!references] > ## See Also - ### Mentions > [!mentions]+ > > > ```datacorejsx > const modules = await cJS() > > const COLUMNS = [ > { id: "Name", value: page => page.$link }, > { id: "Last Modified", value: page => modules.dateTime.getLastMod(page) }, > ]; > > return function View() { > const current = dc.useCurrentFile(); > // Selecting `#game` pages, for example. > let queryString = `@page and linksto(${current.$link})`; > let pages = dc.useQuery(queryString); > > // check types > pages = pages.filter( (p) => !modules.typeCheck.checkAll(p, current) ).sort() > > > return <dc.Table columns={COLUMNS} rows={pages} paging={20}/>; > } > ``` > ```datacorejsx const { dateTime } = await cJS() return function View() { const file = dc.useCurrentFile(); return <p class="dv-modified">Created {dateTime.getCreated(file)} ֍ Last Modified {dateTime.getLastMod(file)}</p> } ```