Picking a random state from a set based on probabilities
There could potentially be millions of states, since each distinct word in the text I scan will be become a state. And they'll never change once calculated. I'm going to scan over a book, calculate the probabilities, then serialize the state/probability map to use later.


Given this, there are a couple more efficient approaches, depending on how much preprocessing you want to do. There's a great article, Darts, Dice, and Coins, that outlines this further and ends with an O(1) algorithm, Vose's alias method.

I think the most straightforward, though, is a binary search tree-based approach ("roulette wheel selection"). Same basic idea as your current code, fill [0, 1) with proportional sections corresponding to your state probability map:

[  :a  | :b |   :c   |:d|  :e  )
0    0.25  0.4     0.76 0.8    1


but then instead of looping over a list, use something like a TreeMap that is designed to answer these kinds of queries in O(log n).

(defn states-&gt;treemap
  "Builds a navigable map of `partial sum -&gt; state`"
  [states]
  (-&gt;&gt; states
    (reduce (fn [[entries sum] [k v]]
              (let [sum' (+ sum v)]
                [(conj entries [sum' k]) sum']))
            [[] 0])
    first
    (into {})
    (java.util.TreeMap.)))

(defn random-state [^java.util.NavigableMap nm]
  (.getValue
    (.ceilingEntry nm (rand))))


That's not "pure Clojure", obviously, but we're on the JVM and it's pretty idiomatic to pull from Java as needed. Otherwise, your Clojure looks fine to me, but definitely check out that article for further depth.