An exercise in Stanley

A longest increasing subsequence(LIS) in a permutation is a subseq of the one-line notation that is increasing. Permutations with LIS length 2 are counted by catalan numbers, and came from a single rectangular tableau. This generalizes!

(Unpublished) preprint here. Joint work with Arjun Krishnan at the University of Utah. While we do a few slightly new things, this problem (and I think a different solution) appeared earlier. In particular, as an exercise in Stanley's Enumerative Combinatorics. This does give a combinatorial (non obvious?) product rule for certain Kostka numbers.

The picture on the left shows an example computation, going from RSK(sigma) to a 2xn standard tableau (for showing a bijection with such tableau).
The reverse algorithm is shown for a 3xn (nonstandard) tableau on the right.

Predictive policing with urns

Predictive policing, the idea of pre-selecting and distributing officers, is an appealing application for algorithms and data science. It can also go very wrong. In limited feedback settings, it is possible to get into a runaway feedback loop, where initial bias or noise can lead to systemic repeated mistakes. We show this can happen, and show a black-box combinatorial intervention which is robust to it.

Papers here and here. Joint work with Danielle Ensign, Sorelle Frielder, CarlosScheidegger, and Suresh Venkatasubramanian (indeed, all of these people did substantially more of the work than myself - I helped prove a related lemma and with some of the editing).

That said, I think there's something novel and appealing to using randomization intentionally in data settings as a defense mechanism against bias and noise. The mathematical model of apple tasting, and its related theory, deserves to be better known. What can you learn when there's a real cost to gaining information, and how do you balance those costs against the potential insights gained?

The behavior of PREDPOL in a simple 2 location system. The red line indicates the optimal ratio of officers based on the true crime rate. The top row shows the policy over time with only the discovered crimes (ie, events officers were there to catch/respond to), while the bottom treats the case where all crimes are reported.
The improvement policy involves Polya Urns, where marked balls are added to an urn based on what we draw from that urn. We use a modified version of this model, a kind of rejection sampling. If we send our officers to one location 90% of the time, we should not update 90% of the time based on a new incident report from that location; we were much more likely to notice such an incident anyway.

Radiocarbon dating

My favorite application for logarithms is carbon dating. Some carbon in the air is radioactive, so that the amount in a given sample decays exponentially over time. This gives us a clock, so that we can tell how old something is. Sadly, reality is not kind to this model.

An undergraduate research project with Duncan Metcalfe at the University of Utah. Poster presented at University of Utah undergraduate research symposia.

The base amount of radiocarbon in the atmosphere is, sadly, not constant. Thus we don't know both the time and initial amount of radiocarbon, and so must work harder to use radiocarbon dating. There is existing software for this: OxCal.

We used this software, and made a primitive version of the same so that we could explore more of the settings. The question was if it was possible to get precise radiocarbon measurements for a certain 'poorly behaved' set of years.

Page updated