first moment method

[[concept]]

[!themes] Topics

Evaluation Error: SyntaxError: Unexpected token '>'

at DataviewInlineApi.eval (plugin:dataview:19027:21)

at evalInContext (plugin:dataview:19028:7)

at asyncEvalInContext (plugin:dataview:19038:32)

at DataviewJSRenderer.render (plugin:dataview:19064:19)

at DataviewJSRenderer.onload (plugin:dataview:18606:14)

at DataviewJSRenderer.load (app://obsidian.md/app.js:1:1182416)

at DataviewApi.executeJs (plugin:dataview:19607:18)

at DataviewCompiler.eval (plugin:digitalgarden:10763:23)

at Generator.next (<anonymous>)

at eval (plugin:digitalgarden:90:61)

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 \dots \cup E_{N}$ and bound it as

P [E] \leq \sum_{i = 1}^{N} P [E_{i}] \leq N \cdot max_{i} {P [E_{i}]}

Often, for a well-chosen set of $E_{i}$ , the $P [E_{i}]$ are about the same. If $N$ is large and $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

\begin{aligned} P [some E_{i} occurs] & = P [\sum_{i = 1}^{N} 1_{{E_{i}}} \geq 1] \\ \leq E [\sum_{i = 1}^{N} 1_{{E_{i}}}] \\ = \sum_{i = 1}^{N} P [E_{i}] \end{aligned}

which we get from Markov's Inequality. Here, we compute the expectation or first moment of the random variable $# E = | {i : E_{i} occurs} |$ .

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 $ε$ -faithful.

References

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}/>;  
}

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>
}

first moment method

References

See Also

Mentions