Techincal Note: Calculating Hamming Distances Between Two Binary Strings in Excel

I haven’t seen anywhere that does this, so here’s how to calculate the Hamming distance between two binary strings in excel.

3-bit binary cube Hamming distance examples
Credit: Wikipedia / en:User:Cburnett

Say you have two binary strings, say 001001 and 100100. How do you calculate their Hamming distance? It turns out it isn’t that easy in Excel, but is possible.

How do we calculate the Hamming distance between 100 and 011 in the cube above, shown as the shortest (red) line joining these two points?

To cut to the chase, the formula for calculating the Hamming distance between strings in cell A1 and B1 is:

=LEN(B1) - LEN(SUBSTITUTE(DEC2BIN(BITXOR(BIN2DEC(B1), BIN2DEC(A1)), LEN(B1)), "1", ""))

BITXOR(A1, B1) sums the difference in bits between the strings in A1 and B1 according to Exclusive OR XOR logic:

INPUTSOUTPUT
ABA XOR B
000
011
101
110

However, Excel needs these numbers as decimals, and the BIN2DEC function converts these binary strings to decimals.

And finally, a trick for counting the occurances of a character in a string:

LEN(A1)-LEN(SUBSTITUTE(A1,”1″,””)) counts the number of 1’s in the string.

As I say, quite a technical note, and I hope useful to people looking at Hamming distances.

Agent-Based Strategizing: New Book Published at Cambridge University Press

My new book, Agent-Based Strategizing, has been published at Cambridge University Press. It is available to download for free until 31 July 2019 at the link below. The book is an overview of how agent-based modelling has been (and can be) used in strategic management.

https://www.cambridge.org/core/elements/agentbased-strategizing/4AD9D0D7416DE46AEB7F1A5478772ACF

Abstract: Strategic management is a system of continual disequilibrium, with firms in a continual struggle for competitive advantage and relative fitness. Models that are dynamic in nature are required if we are to really understand the complex notion of sustainable competitive advantage. New tools are required to tackle challenges of how firms should compete in environments characterized by both exogeneous shocks and intense endogenous competition. Agent-based modelling of firms’ strategies offers an alternative analytical approach, where individual firm or component parts of a firm are modelled, each with their own strategy. Where traditional models can assume homogeneity of actors, agent-based models simulate each firm individually. This allows experimentation of strategic moves, which is particularly important where reactions to strategic moves are non-trivial. This Element introduces agent-based models and their use within management, reviews the influential NK suite of models, and offers an agenda for the development of agent-based models in strategic management.

Spatial Transmission Models PowerPoint Slides presented at EURO2019 (30th European Conference on Opeartional Research), Dublin

These are the slides for my presentation at the 30th European Conference on Operational Research based on my Risk Analysis paper. The paper is available to download here.

Speech given at a meeting of Congregation of the University of Oxford, 7 May 2019

Dr Duncan Robertson, Fellow of St Catherine’s

Vice-Chancellor, members of Congregation. I look around this room and see privilege.  Every one of us here in the Sheldonian Theatre is privileged; every member of Congregation reading the Gazette is privileged.  We are privileged not by our past but by our present: we all have the power to share in the democratic self-governance of the institution that is the Collegiate University of Oxford.

But democratic self-governance is hard.  It is time-consuming and troublesome, and is most easily left to specialists.  Specialists with a track record of delivering strategic plans at high speed.

The Vice Chancellor warned us of the dangers of high speed in her 2017 Oration, and I quote: Over 2,000 years ago Tacitus pointed out that ‘Truth is confirmed by inspection and delay; falsehood by haste and uncertainty’.

It is tempting to react quickly to short term opportunities in order to gain transient rewards, but this is, as my strategic management colleagues will confirm, often at the expense of more attractive opportunities foregone.  We must, at the very least, be able to give ad hoc proposals the service of being fully inspected.  The proposal to establish a new Society – or is it a College? – is a significant one, particularly when it is to have a distinctive culture as was the case with Templeton College before it.

The reason that an ‘education priority’ within the Strategic Plan has abruptly become a press release announcing Parks College, without the knowledge of Congregation, is that such proposals are now increasingly made without such scrutiny.  While the Strategic Plan was put to Congregation for approval, the Implementation Plan referred to within the Strategic Plan was not.  This ‘Plan within a Plan’ is administered by Programme Boards whose agenda and minutes are secret.  In short, Congregation does not know what is going on, and its ability to give informed consent is subverted.

One of the strengths of Oxford that sets it apart from its ‘competitors’ is its self-governance.  This has allowed the University to evolve and adapt to a changing environment, and mercifully not be suffocated by the latest management fads and fashions.  It is bewildering that ‘Senior Managers’ do not appear to recognize the capabilities available to them within Congregation, preferring to operate in a more comfortable ‘command and control’, top-down fashion.  If strategy is imposed, we as a University lose the ability to adapt and to take advantage of opportunities that may emerge – opportunities that may not be visible from the board room but are visible from the diversity of perspectives that each one of us holds as a unique member of Congregation.

The combined organizational capabilities of Congregation – all members of Congregation, experts in their own fields whatever they may be – are truly awe-inspiring.  It is not always easy to find consensus, but that does not mean that this University should give up and follow the lowest common denominator of managerial hubris.

Congregation must be allowed to review and guide the Legislative Proposal to create Parks College prior to giving its approval. The Strategic Plan spoke of creating a new College by 2023, not a new Society in 2019.

The Nolan Committee on Standards in Public Life was established 25 years ago.  The principles of openness and accountability which it set out are as relevant now as they have ever been.  I urge you to vote against the Legislative proposal while we still have the right to exercise that privilege.

Mapping Brexit II

An updated map of Monday’s Indicative Votes but including last week’s votes for the Withdrawal Agreement. Note more analysis here:
http://www.duncanrobertson.com/2019/03/28/mapping-brexit/

This network map shows each MP that voted for each of 5 propositions: Parliamentary Sovereignty, Confirmatory Public Vote, Customs Union, Common Market 2.0, or the Withdrawal Agreement. The large dots show the number of MPs that voted for each proposition. It shows that Parliamentary Sovereignty and the Confirmatory Public Vote are unlikely to be in any consensus (unless with Common Market 2.0 &/or Customs Union), whereas a consensus between the Withdrawal Agreement and either Common Market 2.0 &/or Customs Union may be a possible way to form a Parliamentary majority.

Note the colours are indicative only, and that these votes were whipped by either the Labour Party or the Conservative Party (for instance, Cabinet ministers were instructed to vote only for the Withdrawal Agreement, so the blue dots to the right of the Withdrawal Agreement dot are likely to include the Cabinet).

Mapping Brexit

Wednesday’s indicative votes in the House of Commons produced no definitive answer of the way forward.  By using social network analysis showing the size of each voting bloc and ‘Hamming distances’ (ironically usually used for error correction), we can map how close MPs are to each other, giving an indication of how a coalition could be made if each block of MPs flipped their vote in order to form a Parliamentary consensus.

Brexit is currently turning out to a failed experiment in direct democracy, something I pointed out nearly three years ago.

However, with the House of Commons opening up data, it does allow us a rare insight into the goings on of the population and the MPs that are our representatives.

One interesting data source is released by the UK Parliament showing the voting record of every MP for every ‘division’ (vote). One particularly interesting vote was that done on Wednesday 27 March, where MPs were able to cast their votes for 8 motions:

Mr Baron’s motion B (No deal) ,
Nick Boles’s motion D (Common market 2.0) ,
George Eustice’s motion H (EFTA and EEA) ,
Mr Clarke’s motion J (Customs union) ,
Jeremy Corbyn’s motion K (Labour’s alternative plan) ,
Joanna Cherry’s motion L (Revocation to avoid no deal) ,
Margaret Beckett’s motion M (Confirmatory public vote) , and
Mr Fysh’s motion O (Contingent preferential arrangements)

By making a so-called bipartite network, we can map individual MPs to the votes for which they voted yes. This results in a map of MPs shown below.

(c) Dr Duncan Robertson duncanrobertson.com

While this is interesting, it doesn’t really show the distance between MPs’ voting intentions.

We can redraw the map by using the distance between MPs according to the votes they cast. We can do this by constructing a binary string of their votes. For simplicity, we count only the ‘aye’ or yes votes, and ignore abstentions and nos.

For instance, if an MP voted yes, no, no, yes, no, yes, yes, no, they would be given a string of 10010110, whereas if another MP voted no, no, yes, no, yes, yes, no, yes, they would be given a string of 00101101. So, what is the ‘distance’ between 10010110 and 00101101? For this, we use the Hamming distance – count the number of locations where there is a difference. In this case, the Hamming distance between the MPs is 6.

By constructing a graph of Hamming distances of 1, we can construct neighbours of individual groups of MPs. This is shown in the graph below.

I have listed the votes in the following order:

Common Market 2.0
Confirmatory Public Vote
Contingent Preferential Arrangement
Customs union
EFTA and EEA
Labour’s Alternative Plan
No Deal
Revocation to Avoid No Deal

(c) Dr Duncan Robertson duncanrobertson.com

However, this isn’t very useful, as it doesn’t show the type of MP that voted for each of these. So we can relabel the nodes with a representative MP from that bloc.

From this, you can work out the number of intermediate MPs to get to any other MPs. What is quite interesting is that every MP was just one vote away from another – no-one is isolated. Which, in some little way, gives us hope.

(c) Duncan Robertson duncanrobertson.com

We can then weight the edges to show the possible coalition that could be made if these blocs were to join. And here it is:

The size of each circle represents the number of MPs that voted the same way as the representative MP named on the circle, and the thickness of the links shows how many MPs would join together if one vote were flipped.

If the linked blocs join up, you can see how there could be a path to a Parliamentary majority – for the blocs to join, it would mean switching one vote from ‘aye’ to ‘no’ or vice versa.

For completeness, the list of MPs and their associated binary string is linked here. You can find the MPs that are part of each bloc by searching for the MP name in the label on the network graph. The Hamming distance between each and every MP is available on request. I leave it to the reader to construct an affinity matrix – or what I would call currently describe as a ‘Matrix of Hate’ for each MP pair.

UKRI Future Leaders Fellowships Peer Review College Membership

I am very pleased to have been invited to join the Peer Review College for the UKRI (UK Research and Innovation) Future Leaders Fellowships.

UK Research and Innovation (UKRI) ‘is the national funding agency investing in science and research in the UK. Operating across the whole of the UK with a combined budget of more than £6 billion, UKRI brings together the 7 Research Councils, Innovate UK and Research England’.

‘The UK Research and Innovation Future Leaders Fellowships (FLF) will grow the strong supply of talented individuals needed to ensure that UK research and innovation continues to be world class.’

Spatial Transmission Models: A Taxonomy and Framework

Risk Analysis

This paper , published in the journal Risk Analysis, sets out a review of the different methods used for modelling the spread of an idea, disease, etc. over space.

ABSTRACT

Within risk analysis and more broadly, the decision behind the choice of which modelling technique to use to study the spread of disease, epidemics, fires, technology, rumors, or more generally spatial dynamics, is not well documented.

While individual models are well defined and the modeling techniques are well understood by practitioners, there is little deliberate choice made as to the type of model to be used, with modelers using techniques that are well accepted in the field, sometimes with little thought as to whether alternative modelling techniques could or should be used.

In this paper, we divide modelling techniques for spatial transmission into four main categories: population-level models, where a macro-level estimate of the infected population is required; cellular models, where the transmission takes place between connected domains, but is restricted to a fixed topology of neighboring cells; network models, where host-to-host transmission routes are modelled, either as planar spatial graphs or where short cuts can take place as in social networks; and finally agent-based models which model the local transmission between agents, either as host-to-host geographical contacts, or by modelling the movement of the disease vector, with dynamic movement of hosts and vectors possible, on a Euclidian space or a more complex space deformed by the existence of information about the topology of the landscape using GIS techniques. We summarize these techniques by introducing a taxonomy classifying these modeling approaches.

Finally, we present a framework for choosing the most appropriate spatial modelling method, highlighting the links between seemingly disparate methodologies, bearing in mind that the choice of technique rests with the subject expert.