What's the probability of the Riemann Hypothesis?

Usually when we talk about probabilities, we have certain given information, which takes the form of a \(\sigma\)-algebra of possible events, and there is also a probability function that assigns values to each event. The rationality of a probability function is judged based on the relationships between events. For example if \(A \subseteq B\) then we must have \(P(A) \leq P(B)\). But as long as these relationships are satisfied (giving a proper probability measure), the probabilities could be anything. As such, we do not judge subjective probabilities based on whether they’re actually accurate or not, just whether they are consistent with each other.

Now, imagine if information isn’t the limiting factor in our uncertainty, but rather it’s our lack of mathematical knowledge. A statement like the Riemann Hypothesis (RH) is unknown even though it is entirely determined by the axiom system we use, leaving aside issues of completeness. Here there’s no given \(\sigma\)-algebra and in fact the relationships between RH and other statements may themselves be difficult to determine.

A more realistic view is that we have limited computational resources, we want to solve an intractible problem, and we’ll settle for the best approximation we can get. Thus a probability function is seen as a kind of approximation algorithm. With this algorithmic language, however, we aren’t able to give a very good answer for single propositions like RH. If RH is the entire set of inputs, the optimal approximation is the exact truth value, because it takes a trivial amount of computational resources to output the constant 1 or 0. If the set of inputs is infinite, then the particular input corresponding to RH makes no difference in an asymptotic analysis. For more elaboration on this theme, see this paper.

In traditional Bayesianism there is a seemingly ineradicable source of subjectivity from the choice of prefix Turing machine used to define Solomonoff’s prior. Any one input can be assigned a wide range of probabilities. Perhaps we are left with an analogous but different kind of subjectivity for mathematical probabilities.

(Above: Andrew Critch thinking about this in Berkeley.)

The Fundamental Theorem of Asset Pricing is Bayesianism

If uncertainties encode bet preferences as represented by probabilities, Bayesianism is a collection of Dutch book arguments proving that probabilities must be consistent with each other (defining a probability measure) to be rational. Weisberg has an excellent paper that explains the details. On the other hand, the Fundamental Theorem of Asset Pricing proves that for prices to be arbitrage-free, they must be conditional expectations. Details on the relevant results are found in “The Mathematics of Arbitrage”, by Delbaen and Schachermayer. Having a consistent probability function has been shown to be equivalent to minimizing a proper scoring rule. And conditional expectations have been shown to minimize Bregman divergences. Et cetera. The correspondance between these theories is alluded to by Nau.

Data from Canadian 700MHz and 2500MHz spectrum auctions

The 700MHz (2014) and 2500MHz (2015) spectrum auctions generated revenues of 5,270,636,002 CAD from 302 licenses and 755,371,001 CAD from 97 licenses. Both auctions used a combinatorial clock auction (CCA) format involving an ascending clock phase followed by a sealed-bid supplementary stage where bids could be made on packages of products. Final prices were determined using Vickrey pricing with a core-adjustment. An activity rule was used which required bidders to make bids or lose eligibility to bid in later clock rounds, along with a revealed preference rule which allows the eligibility limit to be exceeded as long as consistency checks are satisfied. For full details on the auction formats see the official documentation (700MHz rules, 700MHz additional details, 2500MHz rules); and the record of bids placed is here for 700MHz and here for 2500MHz.

Bid consistency

The revealed preference rule prevents some inconsistent behavior but not all. By “truthful”, we mean bids that are true indications of subjective value, and by “consistent” we mean bids that are indications of some fixed set of valuations, possibly not the bidder’s actual valuations.

The following table gives the values of Afriat’s critical cost efficiency index (CCEI) for the 700MHz auction. Recall that for a CCEI value \(x\), if \(x < 1\) there is at least some intransitivity in preferences (i.e. inconsistent bidding) and \(1-x\) can be interpreted as the fraction of expenditure wasted making inefficient choices (see this by S. Kariv for more).

Kroemer et al. conclude for the 700MHz auction, “the numbers suggest that bidders deviated substantially from straightforward bidding” in the clock rounds. But “it is not unreasonable to believe that bidders tried to bid up to their true valuation in the supplementary stage” because of higher bid amounts compared to the clock rounds.

The next table gives CCEI values for the 2500MHz auction. We extend the definition of CCEI to apply to supplementary bids as in Kroemer’s paper.

Kroemer et al. (Sec. 5.2) also point out that the total number of bids submitted in the 700MHz auction was much smaller than the number of possible bids, which probably indicates untruthful bidding since an omitted package must have valuation less than or equal to its (low) opening price. The same observation holds for the 2500MHz auction. More exactly, the auction formats enforced a limit on the number of packages bidders were allowed to submit, which was in the hundreds, and bidders generally did not reach the limit.

Ideally, we would determine whether the bids made are consistent with a non-truthful strategy incorporating gaming and/or coordination. The papers Janssen and Karamychev - “Raising Rivals’ Cost in Multi-unit Auctions” and Janssen and Kasberger - “On the Clock of the Combinatorial Auction” derive Bayesian Nash equilibria under gaming preferences and conclude that GARP is not violated in equilibrium gaming strategies. We note that the assumptions in these game models do not include all features of the CCAs under consideration e.g. discrete products, many bidders, public aggregate excess demand, revealed preference rule, initial EP limit, supplementary package limit, 50% mid-auction deposits.

Bids, budgets, and final prices

Bidders may have a notion of a budget – the maximum they are willing to spend. But how should this correspond to the maximum they should bid? In general, bidders may end up paying the exact amount of their highest bid, but looking at the data we see bid prices and final prices can be very different in practice. The following tables show figures from both auctions that illustrate this difference. All prices are given in CAD.

700MHz auction: highest bid placed. Average ratio: 0.192. Max ratio: 0.766.

700MHz auction: (highest) bid placed on package eventually won. Average ratio: 0.447. Max ratio: 0.766.

2500MHz auction: highest bid placed. Average ratio: 0.135. Max ratio: 0.277.

2500MHz auction: (highest) bid placed on package eventually won. Average ratio: 0.235. Max ratio: 0.410.

Across both auctions, we see that bidders paid an average of 16% of their maximum bid placed, where each bidder is equally weighted.

Misc. notes

Researchers design approximation algorithms for winner and price determination in auctions (in e.g. this paper) because exact optimization can be intractable as the number of bids grows, at least in the worst case. However, in these recent auction instances, theoretical intractability did not present a problem because the solution was computable in a small amount of time. The 2500MHz allocation stage involved 2,239 bids and a GLPK-powered solver finds the winners and final prices in a couple minutes on a standard computer. Simulations involving well over 30,000 random bids still take a feasible amount of time.

In the 2500MHz auction, there were 4 pairs of package submissions where the lower-priced package had strictly higher quantities of products. In this case the lower-priced package is superfluous. This table shows the packages, submitted by Bell.

Acknowledgement: Thanks to Z. Gao for pointers.

Link of the day: Journal of Craptology

http://www.anagram.com/jcrap/

The prestigious Journal of Craptology is an open-access publication in the area of cryptology.

U of Toronto study space info

(a partial list)

(Above: U of T cannons pointed at Ryerson)

Libraries

Robarts Library

Richard Charles Lee Canada-Hong Kong Library

Gerstein Science Information Centre

Sanford Fleming Library

Mathematics Library

EJ Pratt Library

Architecture Library (Eberhard Zeidler Library)

Kelly Library

The Inforum (Faculty of Information)

East Asian Library

Centre for Reformation and Renaissance Studies

Local Toronto public library branches

Toronto Reference Library

Lillian H. Smith public library

Other areas with seating

Tables in Bahen Centre

Markov of Chain: Automating Weird Sun tweets

Let’s use python to train a Markov chain generator using all the tweets from a certain list of users, say this one. We’ll use the following libraries.

from functional import seq
import markovify
import re
import tweepy
import unidecode

To use the Twitter API, we need to authenticate ourselves. Register for your personal keys at https://apps.twitter.com/ and then create a config.json file that looks like this

{
  "consumer_key":    "...",
  "consumer_secret": "...",
  "access_key":      "...",
  "access_secret":   "..."
}

Now we can initialize the Twitter API provided by tweepy.

config = seq.json('config.json').dict()
auth = tweepy.OAuthHandler(
    config['consumer_key'], config['consumer_secret'])
auth.set_access_token(config['access_key'], config['access_secret'])
api = tweepy.API(auth)

First we write the following function (based on this gist) which returns the most recent tweets of a given user. The API limits us to at most 3240 tweets per user.

def get_user_tweets(screen_name):
    alltweets = []

    #  200 is the maximum allowed count
    # 'extended' means return full unabridged tweet contents
    new_tweets = api.user_timeline(screen_name=screen_name, count=200,
                                  tweet_mode='extended')

    alltweets.extend(new_tweets)

    # save the id of the oldest tweet less one
    oldest_id = alltweets[-1].id - 1

    # keep grabbing tweets until there are no tweets left to grab
    while len(new_tweets) > 0:
        # since we're grabbing 200 at a time, we use `max_id` to
        #   ask for a certain range of tweets
        new_tweets = api.user_timeline(
                screen_name = screen_name, count=200,
                tweet_mode='extended', max_id=oldest_id)

        alltweets.extend(new_tweets)

        #update the id of the oldest tweet less one
        oldest_id = alltweets[-1].id - 1

        print("...{} tweets downloaded so far".format(len(alltweets)))

    # put each tweet on a single line
    tweet_texts = [re.sub(r'\s*\n+\s*', ' ', tweet.full_text)
                   for tweet in alltweets]

    return tweet_texts

The other interaction with Twitter we need to perform is get all users in a list. We’ll write a function that fetches the usernames and calls get_user_tweets on each:

def get_list_tweets(screen_name, list_name):
    '''
    params: `screen_name` is the username of the owner of the list,
    `list_name` is the name of the list found in the URL
    '''

    # get list of all users in list
    user_names = []
    for user in tweepy.Cursor(
            api.list_members,
            screen_name,
            list_name).items():
        user_names.append(user.screen_name)

    # for each user, get their tweets
    list_tweets = []
    for user_name in user_names:
        list_tweets += get_user_tweets(user_name)
    print('Found {1} tweets from @{2}.'
        .format(len(list_tweets), user_name))
    return list_tweets

Let’s run get_list_tweets and save the output to a file.

tweets = get_list_tweets('Grognor', 'weird-sun-twitter')

with open('data/tweetdump.txt', 'w') as f:
    f.write('\n'.join(tweets))

With all of the raw data saved, we’re done with the Twitter API and we can process the data and auto-generate tweets offline. Assuming the file tweetdump.txt has a set of tweets, one per line, we load them as a list of strings tweets.

tweets = open('data/tweetdump.txt').readlines()

Some processing needs to be done in order to get high quality text from the tweets. The next function process_tweet is called on each one.

def process_tweet(tweet):
    # convert to ASCII
    tweet = unidecode.unidecode(tweet)
    # remove URLs
    tweet = re.sub(r'http\S+', '', tweet)
    # remove mentions
    tweet = re.sub(r'@\S+', '', tweet)

    tweet = tweet.strip()

    # append terminal punctuation if absent
    if len(tweet) > 0:
        last_char = tweet[-1]
        if last_char not in '.!?':
            tweet += '.'

    return tweet

processed_tweets = [ process_tweet(tweet) for tweet in tweets ]

And we remove any tweets that aren’t useful.

def is_excluded(tweet):
    ex = False
    # no RTs
    ex = ex or bool(re.match(r'^RT', tweet))
    # remove whitespace-only tweets
    ex = ex or bool(re.match(r'^\s*$', tweet))
    return ex

good_tweets = [ tweet for tweet in processed_tweets
               if not is_excluded(tweet) ]

We save the fully processed tweets for easy access later.

with open('data/processed_tweets.txt', 'w') as f:
    f.write('\n'.join(good_tweets))

The markovify library lets us train, and generate from, a Markov chain very easily. Just load the training text and set a state size.

text = open('data/processed_tweets.txt').read()

text_model = markovify.Text(text, state_size=3)

for x in range(5):
    print('* ' + text_model.make_short_sentence(140))

Some favorites:

• “It is no coincidence we call them gods because we suppose they are trying to convince Robin Hanson.”
• “Tell anyone who does not produce Scott Alexander.”
• “Weird sun is a costly signal of the ability to remember sources of information, not just the study of complex manifolds.”
• “If you read The Hobbit backwards, it’s about a layer of radioactive ash that develops the capacity to become larger.”
• “When you read a physical book, you get a dust speck in the eye.”
• “We all continuously scream about how the people in it are breaking the awkward silence.”
• “People are important, but so are lexicographic preferences.”
• “You don’t need an expert Bayesian Epistemologist to ensure it’s not a markov chain.”