What classes are you taking?
- literally everyone. Not that it’s a bad question, in-fact it’s probably a rather good question. But it just feels a tad over-used atm.

  • stochastic processes
  • analysis of boolean functions
  • geometric algorithms
  • seminar in number theory
  • writing short stories (afaict? although there was some mess-up with the registration so I’m not sure).
  • NOT: advanced complexity. [Note to self: drop this once the HASS situation is clarified.]

stochastic processes

This is probably the class I’m most excited for.

First class we talked about the threshold at which \(G(n,p_n)\) is connected. Turns out it is precisely \(p_n = \frac{\ln n}{n}\).

proof sketch:

Proposition. Fix constant \(\lambda < 1\) If \(p_n = \lambda \frac{\ln n}{n}\) then whp the graph is disconnected.

Proof. For each \(v\in V\) let \(I_v\) denote the event that \(v\) is isolated (no edges incident to \(v\) survive). Let \(X\) be the number of isolated vertices. For any fixed \(v\) we have \[\Pr[I_v] = (1- p_n)^{n-1} \approx \exp(-(n-1)p_n) \approx 1/n^{\lambda}.\] For example this could be \(1/n^{.999}\).

Hence, \(\mathop{\mathrm{\mathbb{E}}}[X] \approx n^{1-\lambda}\), which you can think of as \(n^{.001} \to \infty\). So, in expectation we have a very large number of isolated vertices, which is great.

Analyze the variance, it’s well-concentrated. Hence, whp at least one isolated vertex. Isolated vertex means in particular that graph is disconnected.

Proposition. Fix constant \(\lambda > 1\). If \(p_n = \lambda \frac{\ln n}{n}\) then whp the graph is connected.

Proof. For any \(S\subseteq V\) with \(|S|\le |V|/2\), define the \(E_S\) as the event that there are no edges between \(S, V\setminus S\). Then \[\Pr[\text{graph disconnected}] \le \sum_{S} \Pr[E_S] \le \sum_{k=1}^{\left\lfloor n/2 \right\rfloor} \binom{n}{k} \Pr[[k]\times([n]\setminus [k]) \cap E = \varnothing] \le \sum_{k=1}^{\left\lfloor n/2 \right\rfloor}(1-p)^{k(n-k)} \binom{n}{k}.\]

And it turns out that this goes to \(0\) as \(n\to \infty\).

Today we talked about branching processes. You have an infinite \(d\)-ary tree and you delete each edge with probability \(p\). This is apparently a special case of “percolation”.

One question of interest is, “What is the chance that there is an infinite component?”

Turns out the answer is that there is a threshold at \(p=1/d\).

TODO: think a bit more about why looking at root component is all you need to do: does that pr threshold as well?

One really interesting thing about this was that we used / proved the Payley-Zygmund inequality, which is really trippy in some sense, because it almost seems like the opposite of chebyshev. It’s proof is just “Cauchy Shwarz” but I still want to understand intuition more.

Example. Ok, so Payley-Zygmund inequality roughly goes like this:

Suppose you have a non-negative random variable and you want to say that it’s actually positive.

Typically with Chebyshev inequality you need \(\sigma < \frac{1}{4}\mu\) to be able to say “stuff is well concentrated around the mean”.

However, with Payley-Zygmund you can get away with \(\sigma < 1000\mu\).

Neat!

boolean functions

We did definitions and motivations. But it just seems very elegant.

Let me prove some basic things really as a way of writing down stuff to remember it:

Proposition. \[\mathop{\mathrm{\mathbb{E}}}f = f(\varnothing), \mathop{\mathrm{\text{Var}}}f = \sum_{S\neq \varnothing} \hat{f}(S)^2.\]

Proof.

Recall the characters are defined as, for each \(S\subseteq [n]\), \[\chi_S: \{\pm 1\}^{n} \to \pm 1, x\mapsto \prod_{i\in S} x_i.\]

Recall we define the inner product as \[\langle f,g \rangle = \mathop{\mathrm{\mathbb{E}}}_x f(x) g(x).\] Thus \[\mathop{\mathrm{\mathbb{E}}}f = \langle f, 1 \rangle = \langle f, \chi_\varnothing \rangle = f(\varnothing).\]

Let \(g=f-\mathop{\mathrm{\mathbb{E}}}f.\) We claim that \(\hat{g}(S)\) is the same as \(\hat{f}(S)\) on all non-empty \(S\), but that \(\hat{g}(\varnothing) = 0\).

Recall, \[\hat{g}(S) = \langle g, \chi_S \rangle = \mathop{\mathrm{\mathbb{E}}}_x g(x)\chi_S(x) = \mathop{\mathrm{\mathbb{E}}}_x f(x) \chi_S(x) - \mathop{\mathrm{\mathbb{E}}}_x\chi_S(x) \mathop{\mathrm{\mathbb{E}}}f.\] Now the important fact is that \(\mathop{\mathrm{\mathbb{E}}}\chi_S = 0\) unless \(S=\varnothing\), in which case \(\mathop{\mathrm{\mathbb{E}}}\chi_\varnothing = 1.\) Hence, \[\hat{g}(S) = \hat{f}(S) - 1_{S=\varnothing} \cdot f(\varnothing).\] Thus our claim about the fourier spectrum of \(g\) is correct.

Finally, we compute \(\mathop{\mathrm{\text{Var}}}f = ||g||^2\) using Parseval’s Equality, which says

\[||g||^2 = \sum_{S\subseteq [n]} \hat{g}(S)^2.\] Which concludes the proof.

geometric algos

closest pair:

  • sort y coord
  • split in half horizontally
  • then there is a vertical column left
  • sweep line on the vertical column
  • sweep line is OP because by packing argument it’s O(1) checks per point

even faster:

  • “gridding”: hash stuff to boxes.

As a historical note, closest pair is probably the first algorithm I ever cared about, in particular due to needing to solve this for a video game “theland”

NT

This class is seeming likely to be my most challenging class. In the combinatorics / algorithms classes I feel very comfortable. The ideas are neat and novel, but I understand the language.

NT is a foreign language so far. Partly I think this is a result of the textbook. The textbook assumes that the reader is really comfortable with basic results of algebra / topology / analysis; however, I’m a bit rusty.

This all said, I think it’ll be a great time. This is very likely the final non-(algorithms, combinatorics) math class I’ll ever take. I don’t think algebra / analysis will ever end up being super relevant to stuff I do. But I think it’ll be fun to pick up a little foreign language, and just learn some really different stuff than what I’m used to.

I hope this can also be an opportunity to learn some other skills along the lines of “doing hard things”. I’m not saying that “doing hard things” is intrinsically meaningful in general. But it often can be. And I’ve been curious about NT for a while. I think algebra / analysis is kinda fancy and neat.

So, why am I taking this class? Because I think numbers are kinda cool and want to know some ridiculously heavy machinery for looking at numbers.

That said, note to self, do not take commutative algebra, analysis or number theory in the future… stick to algos+combo :p.

writing stories

should be fun time, hope I can take it.

misc thoughts

Anyways, all in all, I’m taking some interesting classes and it can be a good time.

But it’s also important to remember to do other stuff, like making good food, walking around boston, and doing research.

add oil!