There’s a mathematical formula for choosing the fastest queue

It seems obvious. You arrive at the checkouts and see one queue is much longer than the other, so you join the shorter one. But, before long, the people in the bigger line zoom past you and you’ve barely moved towards the exit.

When it comes to queuing, the intuitive choice is often not the fastest one. Why do queues feel like they slow down as soon as you join them? And is there a way to decide beforehand which line is really the best one to join? Mathematicians have been studying these questions for years. So can they help us spend less time waiting in line?

The intuitive strategy seems to be to join the shortest queue. After all, a short queue could indicate it has an efficient server, and a long queue could imply it has an inexperienced server or customers who need a lot of time. But generally this isn’t true.

Without the right information, it could even be disadvantageous to join the shortest queue. For example, if the short queue at the supermarket has two very full trolleys and the long queue has four relatively empty baskets, many people would actually join the longer queue. If the servers are equally efficient, the important quantity here is the number of total items in the queue, not the number of customers. But if the trolleys weren’t very full but the hand baskets were, it wouldn’t be so easy to estimate and the choice wouldn’t be so clear.

This simple example introduces the concept of service time distribution. This is a random variable that measures how long it will take a customer to be served. It contains information about the average (mean) service time and about the standard deviation from the mean, which represents how the service time fluctuates depending on how long different customers need.

The other important variable is how often customers join the queue (the arrival rate). This depends on the average amount of time that passes between two consecutive customers entering the shop. The more people that arrive to use a service at a specific time, the longer the queues will be.

Never mind the queue, I picked the wrong shop. Shutterstock

Depending on what these variables are, the shortest queue might be the best one to join – or it might not. For example, in a fish and chip shop you might have two servers both taking orders and accepting money. Then it is most often better to join the shortest queue since the time the servers’ tasks take doesn’t vary much.

Unfortunately, in practice, it’s hard to know exactly what the relevant variables are when you enter a shop. So you can still only guess what the fastest queue to join will be, or rely on tricks of human psychology, such as joining the leftmost queue because most right-handed people automatically turn right.

Did you get it right?

Once you’re in the queue, you’ll want to know whether you made the right choice. For example, is your server the fastest? It is easy to observe the actual queue length and you can try to compare it to the average. This is directly related to the mean and standard deviation of the service time via something called the Pollaczek-Khinchine formula, first established in 1930. This also uses the mean inter-arrival time between customers.

Unfortunately, if you try to measure the time the first person in the queue takes to get served, you’ll likely end up feeling like you chose the wrong line. This is known as Feller’s paradox or the inspection paradox. Technically, this isn’t an actual logical paradox but it does go against our intuition. If you start measuring the time between customers when you join a queue, it is more likely that the first customer you see will take longer than average to be served. This will make you feel like you were unlucky and chose the wrong queue.

The inspection paradox works like this: suppose a bank offers two services. One service takes either zero or five minutes, with equal probability. The other service takes either ten or 20 minutes, again with equal probability. It is equally likely for a customer to choose either service and so the bank’s average service time is 8.75 minutes.

If you join the queue when a customer is in the middle of being served then their service can’t take zero minutes. They must be using either the five, ten or 20 minute service. This pushes the time that customer will take to be served to more than 11 minutes on average, more than the true average for the of 8.75 minutes. In fact, two out of three times you encounter the same situation, the customer will want either the 10 or 20 minute service. This will make it seem like the line is moving more slowly than it should, all because a customer is already there and you have extra information.

So while you can use maths to try to determine the fastest queue, in the absence of accurate data – and for your own peace of mind – you’re often better just taking a gamble and not looking at the other options once you’ve made your mind up.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Enrico Scalas, Nicos Georgiou


Why do we need to know about prime numbers with millions of digits?

SeventyFour via Shutterstock

Prime numbers are more than just numbers that can only be divided by themselves and one. They are a mathematical mystery, the secrets of which mathematicians have been trying to uncover ever since Euclid proved that they have no end.

An ongoing project – the Great Internet Mersenne Prime Search – which aims to discover more and more primes of a particularly rare kind, has recently resulted in the discovery of the largest prime number known to date. Stretching to 23,249,425 digits, it is so large that it would easily fill 9,000 book pages. By comparison, the number of atoms in the entire observable universe is estimated to have no more than 100 digits.

The number, simply written as 2⁷⁷²³²⁹¹⁷-1 (two to the power of 77,232,917, minus one) was found by a volunteer who had dedicated 14 years of computing time to the endeavour.

You may be wondering, if the number stretches to more than 23m digits, why we need to know about it? Surely the most important numbers are the ones that we can use to quantify our world? That’s not the case. We need to know about the properties of different numbers so that we can not only keep developing the technology we rely on, but also keep it secure.

Secrecy with prime numbers

One of the most widely used applications of prime numbers in computing is the RSA encryption system. In 1978, Ron Rivest, Adi Shamir and Leonard Adleman combined some simple, known facts about numbers to create RSA. The system they developed allows for the secure transmission of information – such as credit card numbers – online.

The first ingredient required for the algorithm are two large prime numbers. The larger the numbers, the safer the encryption. The counting numbers one, two, three, four, and so on – also called the natural numbers – are, obviously, extremely useful here. But the prime numbers are the building blocks of all natural numbers and so even more important.

 

Take the number 70 for example. Division shows that it is the product of two and 35. Further, 35 is the product of five and seven. So 70 is the product of three smaller numbers: two, five, and seven. This is the end of the road for 70, since none of these can be further broken down. We have found the primal components that make up 70, giving its prime factorisation.

Multiplying two numbers, even if very large, is perhaps tedious but a straightforward task. Finding prime factorisation, on the other hand, is extremely hard, and that is precisely what the RSA system takes advantage of.

Suppose that Alice and Bob wish to communicate secretly over the internet. They require an encryption system. If they first meet in person, they can devise a method for encryption and decryption that only they will know, but if the initial communication is online, they need to first openly communicate the encryption system itself – a risky business.

However, if Alice chooses two large prime numbers, computes their product, and communicates this openly, finding out what her original prime numbers were will be a very difficult task, as only she knows the factors.

So Alice communicates her product to Bob, keeping her factors secret. Bob uses the product to encrypt his message to Alice, which can only be decrypted using the factors that she knows. If Eve is eavesdropping, she cannot decipher Bob’s message unless she acquires Alice’s factors, which were never communicated. If Eve tries to break the product down into its prime factors – even using the fastest supercomputer – no known algorithm exists that can accomplish that before the sun will explode.

The primal quest

Large prime numbers are used prominently in other cryptosystems too. The faster computers get, the larger the numbers they can crack. For modern applications, prime numbers measuring hundreds of digits suffice. These numbers are minuscule in comparison to the giant recently discovered. In fact, the new prime is so large that – at present – no conceivable technological advancement in computing speed could lead to a need to use it for cryptographic safety. It is even likely that the risks posed by the looming quantum computers wouldn’t need such monster numbers to be made safe.

It is neither safer cryptosystems nor improving computers that drove the latest Mersenne discovery, however. It is mathematicians’ need to uncover the jewels inside the chest labelled “prime numbers” that fuels the ongoing quest. This is a primal desire that starts with counting one, two, three, and drives us to the frontiers of research. The fact that online commerce has been revolutionised is almost an accident.

The celebrated British mathematician Godfrey Harold Hardy said: “Pure mathematics is on the whole distinctly more useful than applied. For what is useful above all is technique, and mathematical technique is taught mainly through pure mathematics”. Whether or not huge prime numbers, such as the 50th known Mersenne prime with its millions of digits, will ever be found useful is, at least to Hardy, an irrelevant question. The merit of knowing these numbers lies in quenching the human race’s intellectual thirst that started with Euclid’s proof of the infinitude of primes and still goes on today.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Ittay Weiss


The Unforgiving Math That Stops Epidemics

Credit: Peter Dazeley Getty Images

Not getting a flu shot could endanger more than just one’s own health, herd immunity calculations show   

As the annual flu season approaches, medical professionals are again encouraging people to get flu shots. Perhaps you are among those who rationalize skipping the shot on the grounds that “I never get the flu” or “if I get sick, I get sick” or “I’m healthy, so I’ll get over it.” What you might not realize is that these vaccination campaigns for flu and other diseases are about much more than your health. They’re about achieving a collective resistance to disease that goes beyond individual well-being—and that is governed by mathematical principles unforgiving of unwise individual choices.

When talking about vaccination and disease control, health authorities often invoke “herd immunity.” This term refers to the level of immunity in a population that’s needed to prevent an outbreak from happening. Low levels of herd immunity are often associated with epidemics, such as the measles outbreak in 2014-2015 that was traced to exposures at Disneyland in California. A study investigating cases from that outbreak demonstrated that measles vaccination rates in the exposed population may have been as low as 50 percent. This number was far below the threshold needed for herd immunity to measles, and it put the population at risk of disease.

The necessary level of immunity in the population isn’t the same for every disease. For measles, a very high level of immunity needs to be maintained to prevent its transmission because the measles virus is possibly the most contagious known organism. If people infected with measles enter a population with no existing immunity to it, they will on average each infect 12 to 18 others. Each of those infections will in turn cause 12 to 18 more, and so on until the number of individuals who are susceptible to the virus but haven’t caught it yet is down to almost zero. The number of people infected by each contagious individual is known as the “basic reproduction number” of a particular microbe (abbreviated R0), and it varies widely among germs. The calculated R0 of the West African Ebola outbreak was found to be around 2 in a 2014 publication, similar to the R0computed for the 1918 influenza pandemic based on historical data.

If the Ebola virus’s R0 sounds surprisingly low to you, that’s probably because you have been misled by the often hysterical reporting about the disease. The reality is that the virus is highly infectious only in the late stages of the disease, when people are extremely ill with it. The ones most likely to be infected by an Ebola patient are caregivers, doctors, nurses and burial workers—because they are the ones most likely to be present when the patients are “hottest” and most likely to transmit the disease. The scenario of an infectious Ebola patient boarding an aircraft and passing on the disease to other passengers is extremely unlikely because an infectious patient would be too sick to fly. In fact, we know of cases of travelers who were incubating Ebola virus while flying, and they produced no secondary cases during those flights.

Note that the R0 isn’t related to how severe an infection is, but to how efficiently it spreads. Ebola killed about 40 percent of those infected in West Africa, while the 1918 influenza epidemic had a case-fatality rate of about 2.5 percent. In contrast, polio and smallpox historically spread to about 5 to 7 people each, which puts them in the same range as the modern-day HIV virus and pertussis (the bacterium that causes whooping cough).

Determining the R0 of a particular microbe is a matter of more than academic interest. If you know how many secondary cases to expect from each infected person, you can figure out the level of herd immunity needed in the population to keep the microbe from spreading. This is calculated by taking the reciprocal of R0 and subtracting it from 1. For measles, with an R0 of 12 to 18, you need somewhere between 92 percent (1 – 1/12) and 95 percent (1 – 1/18) of the population to have effective immunity to keep the virus from spreading. For flu, it’s much lower—only around 50 percent. And yet we rarely attain even that level of immunity with vaccination.

Once we understand the concept of R0, so much about patterns of infectious disease makes sense. It explains, for example, why there are childhood diseases—infections that people usually encounter when young, and against which they often acquire lifelong immunity after the infections resolve. These infections include measles, mumps, rubella and (prior to its eradication) smallpox—all of which periodically swept through urban populations in the centuries prior to vaccination, usually affecting children.

Do these viruses have some unusual affinity for children? Before vaccination, did they just go away after each outbreak and only return to cities at approximately five- to 10-year intervals? Not usually. After a large outbreak, viruses linger in the population, but the level of herd immunity is high because most susceptible individuals have been infected and (if they survived) developed immunity. Consequently, the viruses spread slowly: In practice, their R0 is just slightly above 1. This is known as the “effective reproduction number”—the rate at which the microbe is actually transmitted in a population that includes both susceptible and non-susceptible individuals (in other words, a population where some immunity already exists). Meanwhile, new susceptible children are born into the population. Within a few years, the population of young children who have never been exposed to the disease dilutes the herd immunity in the population to a level below what’s needed to keep outbreaks from occurring. The virus can then spread more rapidly, resulting in another epidemic.

An understanding of the basic reproduction number also explains why diseases spread so rapidly in new populations: Because those hosts lack any immunity to the infection, the microbe can achieve its maximum R0. This is why diseases from invading Europeans spread so rapidly and widely among indigenous populations in the Americas and Hawaii during their first encounters. Having never been exposed to these microbes before, the non-European populations had no immunity to slow their spread.

If we further understand what constellation of factors contributes to an infection’s R0, we can begin to develop interventions to interrupt the transmission. One aspect of the R0 is the average number and frequency of contacts that an infected individual has with others susceptible to the infection. Outbreaks happen more frequently in large urban areas because individuals living in crowded cities have more opportunities to spread the infection: They are simply in contact with more people and have a higher likelihood of encountering someone who lacks immunity. To break this chain of transmission during an epidemic, health authorities can use interventions such as isolation (keeping infected individuals away from others) or even quarantine (keeping individuals who have been exposed to infectious individuals—but are not yet sick themselves—away from others).

Other factors that can affect the R0 involve both the host and the microbe. When an infected person has contact with someone who is susceptible, what is the likelihood that the microbe will be transmitted? Frequently, hosts can reduce the probability of transmission through their behaviors: by covering coughs or sneezes for diseases transmitted through the air, by washing their contaminated hands frequently, and by using condoms to contain the spread of sexually transmitted diseases.

These behavioral changes are important, but we know they’re far from perfect and not particularly efficient in the overall scheme of things. Take hand-washing, for example. We’ve known of its importance in preventing the spread of disease for 150 years. Yet studies have shown that hand-washing compliance even by health care professionals is astoundingly low — less than half of doctors and nurses wash their hands when they’re supposed to while caring for patients. It’s exceedingly difficult to get people to change their behavior, which is why public health campaigns built around convincing people to behave differently can sometimes be less effective than vaccination campaigns.

How long a person can actively spread the infection is another factor in the R0. Most infections can be transmitted for only a few days or weeks. Adults with influenza can spread the virus for about a week, for example. Some microbes can linger in the body and be transmitted for months or years. HIV is most infectious in the early stages when concentrations of the virus in the blood are very high, but even after those levels subside, the virus can be transmitted to new partners for many years. Interventions such as drug treatments can decrease the transmissibility of some of these organisms.

The microbes’ properties are also important. While hosts can purposely protect themselves, microbes don’t choose their traits. But over time, evolution can shape them in a manner that increases their chances of transmission, such as by enabling measles to linger longer in the air and allowing smallpox to survive longer in the environment.

By bringing together all these variables (size and dynamics of the host population, levels of immunity in the population, presence of interventions, microbial properties, and more), we can map and predict the spread of infections in a population using mathematical models. Sometimes these models can overestimate the spread of infection, as was the case with the models for the Ebola outbreak in 2014. One model predicted up to 1.4 million cases of Ebola by January 2015; in reality, the outbreak ended in 2016 with only 28,616 cases. On the other hand, models used to predict the transmission of cholera during an outbreak in Yemen have been more accurate.

The difference between the two? By the time the Ebola model was published, interventions to help control the outbreak were already under way. Campaigns had begun to raise awareness of how the virus was transmitted, and international aid had arrived, bringing in money, personnel and supplies to contain the epidemic. These interventions decreased the Ebola virus R0 primarily by isolating the infected and instituting safe burial practices, which reduced the number of susceptible contacts each case had. Shipments of gowns, gloves and soap that health care workers could use to protect themselves while treating patients reduced the chance that the virus would be transmitted. Eventually, those changes meant that the effective R0 fell below 1—and the epidemic ended. (Unfortunately, comparable levels of aid and interventions to stop cholera in Yemen have not been forthcoming.)

Catch-up vaccinations and the use of isolation and quarantine also likely helped to end the Disneyland measles epidemic, as well as a slightly earlier measles epidemic in Ohio. Knowing the factors that contribute to these outbreaks can aid us in stopping epidemics in their early stages. But to prevent them from happening in the first place, a population with a high level of immunity is, mathematically, our best bet for keeping disease at bay.

For more insights like this, visit our website at www.international-maths-challenge.com.

Credit of the article given to Tara C. Smith & Quanta Magazine