In the previous post we talked about Gaussian and sub-Gaussian processes and generic chaining.
In this post we talk about the Spielman-Srivastava probabilistic construction of graph sparsifiers. Their analysis requires a bound on the largest eigenvalue of a certain random matrix, that can be derived from matrix Chernoff bounds.
We will then make our life harder and we will also derive an analysis of the Spielman-Srivastava construction by casting the largest eigenvalue of that random matrix as the sup of a sub-Gaussian process, and then we will apply the machinery from the previous post.
This will be more complicated than it needs to be, but the payoff will be that, as will be shown in the next post, this more complicated proof will also apply, with some changes, to the setting of hypergraphs.
Welcome to phase two of in theory, in which we again talk about math. I spent last Fall teaching two courses and getting settled, I mostly traveled in January and February, and I have spent the last two months on my sofa catching up on TV series. Hence I will reach back to last Spring, when I learned about Talagrand’s machinery of generic chaining and majorizing measures from Nikhil Bansal, in the context of our work with Ola Svensson on graph and hypergraph sparsification. Here I would like to record what I understood about the machinery, and in a follow-up post I plan to explain the application to hypergraph sparsification.
Yesterday the Italian prime minister announced the timeline of the loosening of the lockdown. Some manufacturing restarted yesterday, and some customer-facing businesses will gradually reopen between next Monday and the beginning of June.
What has been happening in Italy in the last few days, and what can other Western countries expect in the next week or two?
The national discourse has been obsessed with “The Peak,” that is, the time when things reach their worst point, and start improving after that. For the last several days, all indicators, such as new cases, deaths, and ICU occupancy, have been improving. Apparently, then, “The Peak” is behind us. Virologists have been cautious to say that “peak” is the wrong mountain metaphor to use, and that we have rather reached a “plateau” in which things will change very slowly for a while.
Below is the number of confirmed covid-19 deaths in Italy updated with today’s data, showing that we reached the plateau a couple of weeks ago, meaning that the number of new cases started to plateau about a month ago, when the lockdown started.
The data from New York City continues to track the data from Lombardy, so NYC should be just a few days away from its own plateau, if the match continues.
Given all this, people have been wondering when and how we will get out of the lockdown, and reach what everybody has been calling the “Phase Two” of this emergency.
By virtue of being one or two weeks ahead of the rest of the Western world, Italy has been giving advance notices to other countries about what to expect in the covid19 epidemic. For this reason, friends from other countries have been frequently asking me some questions, whose answers I would like to share.
The Protezione Civile, the Italian equivalent of FEMA, holds a daily press conference to announce coronavirus data from the previous 24 hours. Today they had relatively good news, of which we hope to hear more soon. The Protezione Civile puts a lot of data online every day, on github, which allows any interested party to monitor the situation and will allow people in other countries to see the effect of our various restrictive measures over time.
The graph below, which is courtesy of Carlo Lucibello, shows the number of deaths in Italy on a logarithmic scale, compared with data from China from 36 days before.
(Image credit: Carlo Lucibello)
At the start, Italian deaths rose like in China, at the same exponential rate. About twenty days after the lockdown of Wuhan, the Chinese data started deviating from the exponential rate and leveled off. In Italy, about ten days ago, there was a slowdown, which followed the institution of the “yellow zone” by about 15 days. The “yellow zone” measures closed schools, universities, museums, cinemas, and clubs, and restricted hours of bars and coffee shops, in Lombardy. Apparently, although these measures made a difference, they still allowed the spread of the virus to continue at an exponential rate.
On March 8, Lombardy was put on a stricter lockdown, with travel restrictions, and on March 10 the lockdown was extended to the rest of the country. So we may hope to see a stronger slowdown and maybe a leveling-off two or three weeks after these measures, that is, any day now. It may seem premature to ask this question, but what happens next?
Today the Italian government announced additional measures to facilitate “social distancing,” halting all “non-essential” manufacturing and other work activities, forbidding people from leaving the house to walk or jog (even alone), and further restricting the cases in which it is allowed to travel between different cities.
These measures, which apply nationwide, are meant to be in place for two weeks. They will be economically devastating (even more so than the already devastating nationwide lockdown of March 10), and they will be difficult to keep in place for longer than the expected two weeks.
When a nationwide “lockdown” was first instituted, the prime minister announced it by saying “let’s be distant today in order to more warmly hug each other tomorrow”. In general, the spirit of these measures has been to suffer for a short time and then return to normal.
This feels like the national mood in general, and the government took today’s further restrictive measures somewhat reluctantly, because there was strong popular support for them.
Here I am worried that we are approaching this crisis the way many people attempt to lose weight: by going on a starvation diet, then losing some weight, then celebrating and finally gaining back more weight than they lost.
The point being that I worry about what will happen once the worst is over and these restrictive measures will be lifted. Until there is a vaccine or a cure, we will not be able to really go back to normal, and we will have to make some sustainable “lifestyle changes” to “maintain” what we got, just like people who maintain weight loss for a long time do so by making sustainable changes for the long term.
Concretely, we will need a very efficient system to monitor new cases and trace contacts, perhaps similar to Taiwan’s, and to follow the kind of stricter hygiene precautions in public places that have been common in East Asia since SARS. Let’s hope that we will have to worry about such problems soon.
Greetings from the future! The progression of covid-19 in Italy is running about eight days ahead of France and Spain and about 16 days ahead of the United States. Here in Lombardy, which is about ten days ahead of NYC, we have been “sheltering at home” for 13 days already.
How is social distancing working out for me? I thought that I was well prepared for it, but it is still not easy. I have started to talk to the furniture, and apparently this is perfectly normal, at least as long as the furniture does not talk back.
As I have been telling my dining table, it has been very dismaying to read news from the US, where there seemed to be a very dangerous complacency. I am relieved to see that this is changing, especially at the state level, which makes me much more hopeful.
I have also found media coverage to be disappointing. Apparently, many highly educated people, including people whose job involves understanding policy issues, have no idea how numbers work (source). This is a problem because a lot of issues concerning this epidemic have to do with numbers, which can be misleading if they are not reported in context.
For example, before the time when Trump decided that he had retroactively been concerned about a pandemic since January, conservative media emphasized the estimate of a 2% mortality rate, in a way that made it sound, well, 98% of people survive, and 98% is approximately 100%, so what is the big deal. For context, the Space Shuttle only exploded 1.5% of the times, and this was deemed too dangerous for astronauts. This is the kind of intuitive reference that I would like to see more of.
Even now, there is a valid debate on whether measures that will cost the economy trillions of dollars are justified. After all, it would be absurd to spend trillions of dollars to save, say, 10,000 lives, it would be questionable to do so to save 100,000 lives, and it would be undoubtedly right to do so to save millions of lives and a collapse of the health care system (especially considering that a collapse of the health care system might create its own financial panic that would also cost trillions of dollars).
So which one is it? Would doing nothing cost 10,000 American lives? A million? How long will people have to “shelter at home”? And what is next? I can recommend two well-researched articles: this on plausible scenarios and this on what’s next.
Kristof’s article cites an essay by Stanford professor John Ioannidis who notes that it is within the realm of possibilities, given the available data, that the true mortality rate could be as low as 0.05%, that is, wait for it, lower than the mortality rate of the flu. Accordingly, in a plausible scenario, “If we had not known about a new virus out there, and had not checked individuals with PCR tests, the number of total deaths due to “influenza-like illness” would not seem unusual this year.”
Ioannidis’ essay was written without reference to data from Italy, which was probably not available in peer-reviewed form at the time of writing.
I would not want professor Ioannidis to tell me how to design graph algorithms, and I don’t mean to argue for the plausibility of the above scenario, but let me complement it with some data from Italy.
Lombardy is Italy’s richest and most developed region, and the second richest (in absolute and PPP GDP) administrative region in Europe after the Ile de France (source). It has a rather good health care system. In 2018, on average, 273 people died per day in Lombardy of all causes (source). Yesterday, 381 people died in Lombardy with coronavirus (source). This is spread out over a region with more than 10 million residents.
Some areas are harder-hit hotspots. Three days ago, a Bergamo newspaper reported that 330 people had died in the previous week of all causes in the city. In the same week of March in 2019, 23 people had died. That’s a 14x increase of mortality of all causes. Edited to add (3/22/2020):the mayor of Bergamo told Reuters that 164 people died in Bergamo of all causes in the first two weeks of March 2020, versus 56 in the first two weeks of March 2019, a 3x increase instead of the 14x increase reported by Bergamo News.
Bergamo’s hospital had 16 beds in its intensive care unit, in line with international standards (it is typical to have of the order of an ICU bed per 5000-10,000 people, and Bergamo has a population of 120,000). Right now there are 80 people in intensive care in Bergamo, a 5x increase in capacity that was possible by bringing in a lot of ventilators and moving other sick people to other hospitals. Nonetheless, there have been reports of shortages of ICU beds, and of people needing to intubated that could not be. There are also reports of people dying of pneumonia at home, without being tested.
Because of this surge in deaths, Bergamo’s funeral homes have not been able to keep up. It’s not that they have not been able to keep up with arranging funerals, because funerals are banned. They just do not have the capacity to perform the burials.
So coffins have been accumulating. A couple of days ago, a motorcade of army vehicles came to Bergamo to pick up 70 coffins and take them to other cities.
It should be noted that this is happening after 20 days of “social distancing” measures and after 13 days of “sheltering at home” in Lombardy.
My point being, if we had not known that a news virus was going around, the number of excess deaths in Bergamo would have not been hidden by the random noise in the number of deaths due to influenza-like illness.
As the coronavirus epidemic advances in Italy with a 25-30% growth rate (meaning that the numbers are doubling every 3-4 days), and after two weeks of “lockdown-lite” in Northern Italy seems to have made no difference, the Italian government imposed on Sunday morning a stricter lockdown on the region of Lombardy and some cities outside the region including Venice. Several people have reached out to ask how things are going, so here is a brief recap.
In the past two weeks, in Italy, we have been drowning in information about the novel coronavirus infection, but the statistics that have been circulating were lacking proper context and interpretation. Is covid-19 just a stronger form of the flu or is it a threat to the world economy? Yes.
Now that the first community transmissions are happening in my adopted home in the San Francisco Bay Area, I would like to relay to my American readers what I learned from the Italian experience.
Greetings from Milan, in Italy’s “yellow zone” of areas bordering clusters of coronavirus infections. This week, all schools, universities, museums, theaters are closed, bars have to close by 6pm, and fairs and conferences are being postponed. The “red zone” of small towns with the clusters of infections is on lockdown.
Milan has been unseasonably warm and sunny in the past few days, and walking through the city, with very light car and pedestrian traffic, has been lovely. This is apparently what the city usually looks like in August, but without the heat and humidity. Continue reading →
