### Password strength

Writing about web page https://xkcd.com/936/

Today in the ST116 group we discussed how to build strong passwords. A good exposition can be found in the xkcd cartoon referenced as the weblink for this article.

Writing about web page https://xkcd.com/936/

Today in the ST116 group we discussed how to build strong passwords. A good exposition can be found in the xkcd cartoon referenced as the weblink for this article.

Writing about web page https://fivethirtyeight.com/features/the-media-has-a-probability-problem/

Not just the media, but it's a fair point. Have a look at what Nate Silver has to say.

This TED talk makes a lot of sense to me, and chimes in with more than 35 years of lecturing experience. Have a look and see what it suggests to you.

The following remarkable procedure is entirely feasible: if I have a class of *n* students then I can distribute *n* different binary images, one to each student, such that each student's image looks like white noise,

and yet if * all* images are combined together in the right way then a meaningful picture emerges.

What's more, I can arrange matters such that if any strict subset of the *n* students tried to collaborate, then all they would get would be more white noise, no matter how they manipulated their *n*-1 images!

So any strict subset of the students would possess no information at all about the butterfly picture, but combined all together they would be in a position to produce a perfect reproduction of the image.

How can this be done?

- Code each black pixel of each image as -1, each white pixel as +1, and view each distributed image as a long vector sequence of +/-1 values.
- Let
*X*_{0}be the vector encoding the target image (the butterfly above). Generate entirely random independent vectors*X*,_{1}*X*_{2}, ...,*X*_{n}_{-1}*n*-1 students.

- Student
*n*is given an image corresponding to the vector*X*obtained by multiplying (coordinate-wise) all the other vectors:_{n}

*X*_{n}=*X*_{0}**X**_{1}*X*_{2}* ... **X*_{n}_{-1 }where "*" denotes coordinate-wise multiplication. - It is simple arithmetic that
*X*_{0}*=**X*_{n}**X**_{1}*X*_{2}* ... **X*_{n}_{-1}. So all students working together possess the information to recover the butterfly image.

- On the other hand one can use elementary probability to show that, if one selects any subset of size
*n*-1 of the vectors*X*,_{1}*X*_{2}, ...,*X*, then this subset behaves as if it is a statistically independent collection of vectors corresponding to white-noise images. (It suffices to consider just one pixel at a time, and show that the corresponding sequence of_{n}*n*-1 random +/-1 values obey all possible multiplication laws.) So no strict subset of the students has any information at all about the butterfly image.

There are many other ways to implement secret-sharing (Google/Bing/DuckDuckGo the phrase "secret sharing"). But this one is nice for probabilists, because it provides a graphic example of why *pairwise independence* (independence of any two events taken from a larger collection of events) need not imply complete independence.

In your third year at Warwick you often have a drink with a friend who enjoys probability (yes, you make some strange friends here). On the Sunday evening before the start of Term 2 she challenges you to a curious game of chance. Hiding a fair six-sided die (numbered 0,1,2,3,4,5) from your observation, she throws it ten times and secretly notes each outcome on a convenient beer mat. Then she turns to you and announces:

"I shall now read you the running averages of the dice throws, but in reverse order.''

(You must have looked puzzled, because she breaks off to explain)

"Let *X*_{n} be the result of the *n*^{th} throw, so the *n*^{th} running average is *Y _{n}*=(

Clearly a flicker of comprehension must have somehow crossed your face, because she now continues:

"At any stage you can stop me reciting the sequence. If the last average I read out was *Y*_{n} then with probability *Y*_{n}/5 (arranged using that book of random numbers which I carry everywhere) I will buy you a pint and the game ends. If you don't stop me at all then clearly you get a pint with probability *Y*_{1}/5. Otherwise you buy me a pint.''

You calculate rapidly: **E**[*Y*_{1}/5]=**E**[*X*_{1}/5]=(1/6) (0+1+...+5)/5=1/2 even if you wait till the last number, and you get to choose when to stop. Must be to your advantage!

"Seems a reasonably good deal to me,'' you say.

"I'm glad you think so;'' she replies, "before we begin you can buy me a pint to compensate. Then we can play the game *K* times, where *K* is as large as you think it should be so that on average you come out ahead.''

How big should *K* be?

The very next day you hear about this course, ST318 *Probability Theory*; by the end of the course you'll have learned enough to be able to answer the above question instantly *without any calculation at all*. All this and 15 CATS credit too. Now that is what you call fair! How can you resist?

The following notes concern some calculations I have made relating to Zanella *et al* (2017). The considerations laid out below are entirely trivial, but are helpful in making it clear whether or not certain conditions might be logically independent of each other.

Consider a random variable *X* with probability density *f*(*x*) = e^{φ(x)}.

- The
*entropy*of*X*is given by*H*= - ∫ log(*f*(*x*))*f*(*x*) d*x*= - ∫ φ(*x*)*f*(*x*) d*x*= -**E**[ φ(*X*) ]; - One is also interested in something loosely related to
*Fisher information*, namely Ι = ∫ φ'(*x*)^{2}*f*(*x*) d*x*=**E**[ φ'(*X*)^{2}].

Is it possible for Ι to be finite while *H* is infinite?

**Yes**.

Consider a density *f*(*x*) which is proportional (for large positive *x*) to 1/(*x *log(*x*)^{2}). Consequently φ(*x*) = constant - (log *x *+ 2 log log *x*) for large *x*.

1: Using a change of variable (e^{u} = *x*) it can be shown that *H* = - ∫ log(*f*(*x*)) *f*(*x*) d*x* is infinite. The contribution to the entropy *H* for large *x* is given by - ∫^{∞} log(*f*(*x*)) *f*(*x*) d*x,* controlled by

∫^{∞} (log *x* + 2 log log *x*) d*x */(*x *log(*x*)^{2}) = ∫^{∞} (*u* + 2 log *u*) e* ^{u} *d

2: On the other hand elementary bounds show that Ι = ∫ φ'(*x*)^{2} *f*(*x*) d*x* can be finite. The contribution to the "Fisher information" Ι for large *x* is given by - ∫^{∞} φ'(*x*)^{2} *f*(*x*) d*x,* related to

∫^{∞} (1 / *x* + 2 / (*x *log *x*) )^{2} d*x */(*x *log(*x*)^{2}) = ∫^{∞} (1 + 2 / log *x* )^{2} d*x */(*x*^{3} log(*x*)^{2}) < constant × ∫^{∞} d*x */ *x*^{3} < ∞.

An example of such a density (behaving in the required manner at ±∞) is

*f*(*x*) = log(2) |*x*| / ((2+*x*^{2}) (log(2+*x*^{2}))^{2}) .

Zanella, G., Bédard, M., & Kendall, W. S. (2017). A Dirichlet Form approach to MCMC Optimal Scaling. *Stochastic Processes and Their Applications*, to appear, 22pp. http://doi.org/10.1016/j.spa.2017.03.021

Here is a puzzle which I often use as a starter for a course of lectures on probabilistic coupling. The puzzle arose during some research -- I devised it as a simple example to show myself why a particular idea would not work -- and I developed the solution using calculations. In a lunch queue, I asked James Norris of Cambridge whether he could think of a calculation-free answer, and he found one almost immediately.

- You go to Starbucks with a friend.

- You are the quiet type, and stay in the front room near the window, sipping a coffee slowly to make it last.

- She is extrovert, and has gone through to a further room where the louder people gather.

There she plays a game: toss*n*coins, win if*r*heads or more. - After the game should have finished, a third friend comes through and says,

**either:**"She won the first toss'';

**or:**"She won at least one toss''.

*(Why don't people speak more clearly?!)* - Which is better news for your friend? Prove your answer without calculation!

*Convergence in probability* is the simplest form of convergence for random variables: for any positive ε it must hold that **P**[ | *X*_{n} - *X* | > ε ] → 0 as *n* → ∞. This kind of convergence is easy to check, though harder to relate to first-year-analysis convergence than the associated notion of *convergence almost surely*: **P**[ *X*_{n} → *X* as *n* → ∞] = 1.

Convergence in probability is implied by convergence almost surely (most direct proof: express convergence almost surely in terms of more elementary events using countable unions and intersections and do some simple reasoning on the result), but is not implied by it. On the other hand a sequence of random variables that converges in probability always has a sub-sequence that converges almost surely. Moreover if every sub-sequence of a sequence of random variables contains a sub-sub-sequence that converges almost surely, then the original sequence converges in probability.

While studying the application of Dirichlet forms to Markov chain Monte Carlo (developing the work of Zanella *et al*, 2017), the following convergence-in-probability question arose:

Work on a given probability space (Ω, *F*, **P**). Suppose that random variables *X*_{1}, *X*_{2}, ... converge to *X* in probability.

Given a sub-σ-algebra *G* < *F*, is it the case that random variables *X*_{1}, *X*_{2}, ... converge to *X* in *G*-conditional probability?

In other words, is it the case that, for every ε>0,

If the conditioning is simply a conditioning on a single event of positive probability, then the answer is **yes**; consider that **P**[ A_{n} | B ] ≤ **P**[ A_{n} ] **P**[ B ], so **P**[ A_{n} | B ] will converge to zero if **P**[ A_{n} ] does.

However the general answer is, of course, **no**. In a nutshell, consider a sequence of random variables that converges in probability but not almost surely. Condition on the entire sequence(!), thus rendering it entirely deterministic. There is a positive chance that the conditioned sequence fails to converge; and if so then it cannot converge in (conditional) probability. We now give an explicit example of a sequence that converges in probability but not almost surely, and spell out the details of why conditional convergence in probability then fails.

Consider a Uniform random variable *U* defined on [0, 1), using the usual Lebesgue σ-algebra *F*. Define *X*_{1}, *X*_{2}, ... as follows: consider the ensemble of events [(*k*-1)2^{-m}, *k2*^{-m} ) for *k* = 1, ..., *m* and *m*= 1, 2, ... Order these and let *X*_{n} be the indicator random variable corresponding to the *n*th event, while *X*= 0.. Then **P**[ *X*_{n} =1]=*2*^{-m }if *X*_{n} is the indicator random variable corresponding to [(*k*-1)2^{-m}, *k2*^{-m} ), hence **P**[ | *X*_{n} - *X* | > ε ] → 0 if 0 < ε < 1. So certainly *X*_{1}, *X*_{2}, ... converge to *X* in probability. On the other hand, if *G *= *F* then almost surely the sequence *X*_{1}, *X*_{2}, ... contains infinitely many 1's as well as infinitely many 0's, so similarly for **P**[ | *X*_{n} - *X* | > ε | *G *] = [*X*_{n} = 0], so almost surely **P**[ | *X*_{n} - *X* | > ε | *G *] can *never* converge.

More generally, this sort of problem arises whenever the σ-algebra *G* contains a random variable whose distribution is not atom-free.

Exactly the same argument shows that L_{p} convergence does not imply "conditional L_{p} convergence".

However the facts that

- convergence in probability implies existence of almost surely convergent subsequences,
- while convergence in probability itself is implied by existence of almost surely convergent sub-subsequences for every subsequence,

can be used to evade the issues raised here. For example, in the case of the application of Dirichlet forms to Markov chain Monte Carlo, even though convergence in probability is not preserved under conditioning, these considerations can be used to prove a strategic conditional CLT ...

Zanella, G., Bédard, M., & Kendall, W. S. (2017). A Dirichlet Form approach to MCMC Optimal Scaling. *Stochastic Processes and Their Applications*, to appear, 22pp. http://doi.org/10.1016/j.spa.2017.03.021