CR01 Using Randomness in Science

Teaching team: Pierre Borgnat, Patrick Flandrin, Olivier Gandrillon and Nicolas Schabanel

Person in charge: N. Schabanel

Lectures Timetable

Date	8:00-10:00	13:30-15:30	15:45-17:45
Thursday Dec 12	Nicolas Schabanel (1/4)
Thursday Dec 19	Nicolas Schabanel (2/4) Lecture Notes: [ PDF ]
Tuesday Jan 7			Olivier Gandrillon (1/2) Slides: [ PDF \| PPT ]
Thursday Jan 9	Nicolas Schabanel (3/4) Lecture Notes: [ PDF ]
Thursday Jan 16	Nicolas Schabanel (4/4)	Olivier Gandrillon (2/2) Slides: [ PDF ]	Patrick Flandrin (1/2)
Thursday Jan 30	Patrick Flandrin (2/2)
Tuesday Feb 4		Pierre Borgnat (1/2)	Pierre Borgnat (2/2)
Tuesday Feb 6	Exam (9h30-11h30)

General presentation

The fact that new powers come from randomness got increasingly clear in various scientific fields during the last decades, and the technics to take advantages of randomness are now mature enough to be considered as classic if not indispensable in most scientific fields. After a short introduction to the simple mathematics needed for this course, we will go through the different aspects of the powerful uses of randomness in computer science, physics and biology, and their estounishing consequences.

Computer Science part: Unexpected possibilities obtained by introducing randomness in algorithms (N. Schabanel) (circa 2/5th of the course)

Since the 70s, computer scientist have discovered that access to a random source can yield to surprising and counterintuitive results of unexpected power. We will see in this course how to use a random source to count with a tiny tiny memory (randomized counters), how to correct a buggy program without modifying its internal code (self-correcting program), how to test if someone knows a secret without knowing nor learning anything about his secret (zero-knowledge proof), and study the strange properties of expander graphs and their estounishing applications. The most striking fact is that all these methods are very simple to design as well as to analyze and are most of time much more efficient that their deterministic alternatives: faster and saving a lot of resources. These technics are thus very likely to be favored by evolution in nature, and one should be prepared to face them! Randomness is thus far better that some noise we want to get rid off but turns out to be a very powerful engine. We shall see as well how the notion of randomness is connected to the notion of problems which are hard to solve.

Some references:

S. Arora, B. Barak. Computational complexity : a modern approach, Princeton U. Press, 2010
S. Hoory, N. Linial, A. Wigderson. Expanders graphs and their applications, Bull . Amer. Math. Soc., 43:439-561, 2006.
L. Trevisan’s remarkable lecture notes : http://lucatrevisan.wordpress.com/lecture-notes/

Physics part: The data analysis viewpoint Noise and/or information (P. Borgnat et P. Flandrin) (circa 2/5th of the course)

Classically, in most data analysis methods (signal and image processing, statistics, data collection,…), noise is usually seen as a disturbance to get rid of. However, beyond situations where information is carried by noise, some methods propose to make use of noise as an aid for analysis and decision. Several of these approaches stemming from physical sciences, it is proposed to discuss three such families in the following directions:

Accessing data with some randomness in the measurement process: random sampling and quantization; introduction to « compressed sensing »; estimation via random projections (sketches, Bloom filters,...)
Random shuffling of data: « bootstrap » techniques in statistics ; « surrogate data analysis » in nonlinear physics and signal processing,...
Noise-assisted data analysis: stochastic resonance; robust averaging; links with noise-assisted algorithms and simulations (stochastic gradient, Monte-Carlo methods, simulated annealing).

The purpose of the course is to cover the main results on these three instances where some controlled random component, or even noise, can be efficiently used to enhance the performance of the analysis. Basics as well as more recent advances will be covered.

References:

1st part:
- P. Babu, P. Stoica (2010). "Spectral analysis of nonuniformly sampled data – a review," Digital Signal Processing, vol. 20(2), pp. 359–378
- R.G. Baraniuk, E. Candès, R. Nowak, M. Vetterli eds. (2008). "Special Section on Compressive Sampling," IEEE Sig. Proc. Mag., vol. 25(2), pp. 12–101. See also: http://dsp.rice.edu/cs/
- S. Muthukrishnan (2003). "Data streams: Algorithms and applications," in ACM SIAM SODA.
2nd part:
- B. Efron, R. Tibshirani (1994). An Introduction to the Bootstrap. Chapman & Hall/CRC.
- B. Efron, B. (1982). The jackknife, the bootstrap, and other resampling plans. CBMS-NSF Monographs.
- T. Schreiber, A. Schmitz (2000) "Surrogate time series," Physica D, vol. 142(3-4), pp. 346–382.
- A. Zoubir, D.R Iskander (2004). Bootstrap Techniques for Signal Processing, Cambridge University Press.
3rd part:
- A. Bulsara, P. Hänggi, F. Marchesoni, F. Moss, M. Shlesinger, eds. (1993). Stochastic Resonance in Physics and Biology, J. Stat. Phys. 70, 1-512.
- T. Wellens, V. Shatokhin, A.Buchleitner (2004). "Stochastic resonance," Rep. Prog. Phys., vol. 67, pp. 45–105.
- F. Mossa, L.M. Ward, W.G. Sannita (2004). "Stochastic resonance and sensory information processing: a tutorial and review of application," Clinical Neurophysiology, vol. 115, pp. 267–281.
- D. Rousseau, F. Chapeau-Blondeau (2005). "Stochastic resonance and improvement by noise in optimal detection strategies," Digital Signal Processing, vol. 15, pp. 19-32.

Biology part: Randomness at the heart of the cell (O. Gandrillon) (circa 1/5th of the course)

The idea that chance could play a leading role in biology is obviously a clear legacy of Charles Darwin, who first postulated chance (coupled with selection) as the driving principle of evolution. Nevertheless, this idea has not been very popular among molecular biologists, who are still much in favor of a programmatic paradigm ("the genetic program") that randomness can only disturb. There has been overtime a number of dissenting voices (Novick and Weiner, 1957; Spudich and Koshland, 1976; Rigney and Schieve, 1977; Berg, 1978; Kupiec, 1983), but it was not until 2002 (Elowitz et al., 2002) that the experimental demonstration of the variability of gene expression at the single cell level forced a part of the community to reconsider the role that chance could be play in biology (Huang, 2010; Eldar and Elowitz, 2010). In recent years a large body of literature (Vinuelas, 2012, for a recent review) has sought to demonstrate that chance could play:

An adaptive role;
A role in the cell cycle;
A role in decision making in the HIV virus and the cellular level in some prokaryotes can lead to a role in the pathogenesis;
A role during embryonic development and in some processes of cellular differentiation.
A role in cancer development.
A role in aging. 7. A role in the variability in cancer cells in response to treatment.

We will try in this course to address two issues:

How to measure and model the stochasticity of gene expression
Illustrate its possible role in biology through one or two examples.

A few references:

Berg, O.G. (1978). A model for the statistical fluctuations of protein numbers in a microbial population. J Theor Biol 71, 587-603.
Eldar, A., and Elowitz, M.B. (2010). Functional roles for noise in genetic circuits. Nature 467, 167-173.
Elowitz, M.B., Levine, A.J., Siggia, E.D., and Swain, P.S. (2002). Stochastic gene expression in a single cell. Science 297, 1183-1186.
Huang, S. (2010). Cell Lineage Determination in State Space: A Systems View Brings Flexibility to Dogmatic Canonical Rules. PLOS Biol 8, e1000380.
Kupiec, J.J. (1983). A probabilistic theory for cell differentiation, embryonic mortality and DNA C-value paradox. Speculations in Science and Technology 6, 471-478.
Novick, A., and Weiner, M. (1957). Enzyme Induction as an All-or-None Phenomenon. Proc Natl Acad Sci U S A 43, 553-566.
Rigney, D.R., and Schieve, W.C. (1977). Stochastic model of linear, continuous protein synthesis in bacterial populations. J Theor Biol 69, 761-766.
Spudich, J.L., and Koshland, D.E., Jr. (1976). Non-genetic individuality: chance in the single cell. Nature 262, 467-471.
Viñuelas, J., Kaneko, G., Coulon, A., Beslon , G. and Gandrillon, O. (2012). Toward experimental manipulation of stochasticity in gene expression. Progress in Biophysics & Molecular Biology, 110, pp 44-53.

Evaluation (subject to changes)

Each part will be evaluated separately by either: a short homework, article reading, a short programming project, or writing a report.