Locked-in to the Game of 20-Questions

One of the worst medical conditions I can imagine is locked-in syndrome. It leaves you with all your mental abilities intact, but totally paralysed except perhaps for the blink of an eye. A perfectly working mind is locked inside a useless body, able to sense all around but unable to communicate. Despite this, one of the most uplifting books I have read is “The Diving Bell and the Butterfly”. It’s the autobiography of Jean-Dominique Bauby, written after he woke up in a hospital bed with locked-in syndrome. In the book, he describes a life with locked-in syndrome, including how he communicated not only with medical staff, friends and family but also to write the book itself. He did so without any technological help.

The book was written via human-human interaction of a heroic form. Put yourself in his position, waking up in a hospital bed totally paralysed. All you can do is blink one eyelid. What would be the best way for you to communicate so that you could write a whole book? You have only a helper with a pen and paper to write down your “words”?

How did Bauby do it?

The system Bauby used involved the helper reading the alphabet aloud “A…B…C …” When the letter he was thinking of was spoken he blinked. The helper would write that letter down and then start again, letter after letter. Try it with a friend: communicate your initials to them that way…now think about that being the only way you have to talk to anyone. I hope your name isn’t Zebedee Zacharius Zog or Zara Zootle!

Bauby realized that the ABC algorithm could be improved upon. He had been the Editor-in-chief of the French women’s magazine Elle before that hospital bed so knew about language. He knew that some letters are more common than others in natural language, so got the helper to read out the letters in order of frequency in French “E…S…A…R…” That way the helper got to the common letters more quickly. A similar trick has been used through the ages to crack secret codes (see our Beheading story elsewhere).

Now as a computer scientist I immediately start thinking I could have made his life so much better (even before the step replacing the human helper with blink detection gadgets and the like). It is a problem about the “complexity”, the efficiency, of algorithms.

In the worst case, perhaps dictating a story where someone does nothing but snore for the whole book, “Zzzzz”, it takes 26 questions per letter. On average over the whole book roughly 13 letters will be said per letter dictated. Bauby’s modification improves things down to about 10 questions per letter, but the worst case is still 26. Thinking as a computer scientist the problem is a search problem (searching for one letter in 26) and the solution he used is known as linear search.

Linear search is a “linear” algorithm with “linear” complexity meaning the time it takes to give an answer is proportionate to the amount of date. Double the data and the algorithm takes twice as long to find the answer. Computer Scientists write this as O(n) as short hand for saying it is linear.

Do it in 5

Other search algorithms are far faster than linear search. From some simple computer science I learnt as an undergraduate, I know that a search through 26 things only needs at most 5 true/false or blink/no blink questions at worst, not 26!

How do we do it? By using the same strategy as is used in the children’s game of 20 questions. It is a search problem too: a search to find the name of a famous person out of thousands, possibly millions of people. And yet it does not take thousands or millions of questions to win. It is all in the questions that you ask.

Played well you do not ask as the first question “Is it Einstein?”, the equivalent to “Is it E?” Rather you first ask: “Are they female?”. Why is that a better question? It is because it rules out half the possibilities whatever the answer. Start with a million possibilities and always ask a halving question and you Try it – start with 1 million and see how many times you have to halve it before you get down to 1:

1 000 000  people are possible to start with
   500 000  people left after 1 question  
   250 000  people left after 2 questions 
   125 000  people left after 3 questions
     64 000  people left after 4 questions, approximately its actually a bit better than this
     32 000  people left after 5 questions
     16 000  people left after 6 questions
       8 000  people left after 7 questions
       4 000  people left after 8 questions
       2 000  people left after 9 questions
       1 000  people left after 10 questions
          500  people left after 11 questions
          250  people left after 12 questions
          125  people left after 13 questions
            64  people left after 14 questions, approximately
            32  people left after 15 questions
            16  people left after 16 questions
              8  people left after 17 questions
              4  people left after 18 questions
              2  people left after 19 questions
              1  person left after 20 questions

So starting with a million people, if you always ask halving questions, it only takes 20 questions (in the worst case) to have found the person, they were thinking of.

The equivalent halving question for the alphabet is “Is it before N?” Keep asking questions like that about letters in the remaining portion of the alphabet, rather than asking if it was a specific famous person, and you get down to a single letter in no more than 5 questions.

            26  letters are possible to start with
            13  letter left after 1 questions
              7  letter left after 2 questions
              4  letter left after 3 questions
              2  letter left after 4 questions
              1  letter left after 5 questions

Tweak it based on letter frequencies and you can do even better for some letters.

Algorithms that halve the size of the problem at each step like this are called logarithmic algorithms. The number of steps it takes no longer increases proportionately with the amount of data, but with the logarithm of the amount of data. If we have n pieces of data to search it takes log (n) steps to find it. This is because the logarithm (to base 2) of a number is just the number of times you can halve the number before you get to 1. The notation log(n) is just a maths way of counting the number of times we halve. As we saw logarithmic algorithms like this are massively more efficient. When you double the amount of data (say from half a million pieces of data to search to a million pieces of data to search, you only need one extra step to find the answer (rather than half a million more). Our new halving algorithm has logarithmic efficiency, which we write O(log n). O(log n) algorithms are massively faster in general than O(n) algorithms.

Bauby should have got the helper to ask such halving questions. Think about it. 5 questions at worst rather than 26, multiplied up by all the letters in his book. If only he had known some computer science, how much easier his life would have been. How much easier it would be to write the book. Now we have worked out a method we can think how we could automate it with suitable technology. How wonderfully computer science can improve lives.

But wait a minute. Perhaps the computer scientist would have ensured his book was never completed and his life was even more a hell. We did not start with technology but we did start with computer science. Perhaps we should have started with the person. We have been counting questions asked and that is the job of the helper for which it may be tedious but it’s not difficult. What if blinking is a great effort for him. His solution involved him blinking only once per letter. Ours requires him to blink 5 times. Multiply that by a whole book and it is 5 times harder for him if blinking is hard. Furthermore, his solution is easy for anyone to walk in and understand. Ours is complex and might need some explaining before the visitor understands and Bauby is not going to be the one to do the explaining.

It worked for him

One thing is certain about Bauby’s solution – it worked for him. He wrote a whole book that way after all. Perhaps the helper did more than just write down his words. Perhaps they opened the curtains, talked to him about the outside world or just provided some daily human warmth. Perhaps the whole point of writing the book was that it gave him an excuse to have a person there to communicate with all the time. The communication method would not then be facilitating the needs of the book, but the book facilitating a deep need for direct communication with a person. Replace the human and perhaps you have replaced the thing that was actually keeping him alive. In extreme usability situation such as this the important thing is that the user really is involved throughout. It is they who ultimately have to adapt the available resources to something that works for them, not only technically but also emotionally and socially. Otherwise we may devise a “solution” that is in theory wonderful and in practice hell on earth. Complexity of algorithms is important but Computer Scientists have to think about much more than just maths and efficient solutions.

Paul Curzon, Queen Mary University of London (updated from the archive)

Further Reading

Find out about what life is like with locked in syndrome by reading: The Diving Bell and the Butterfly by J-D Bauby. Fourth Estate.

More on …

• Algorithms and Complexity
• Disability Stars in Computing

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

---