Jump to ContentJump to Main Navigation
Benford's LawTheory and Applications$

Steven J. Miller

Print publication date: 2015

Print ISBN-13: 9780691147611

Published to Princeton Scholarship Online: October 2017

DOI: 10.23943/princeton/9780691147611.001.0001

Show Summary Details
Page of

PRINTED FROM PRINCETON SCHOLARSHIP ONLINE (www.princeton.universitypressscholarship.com). (c) Copyright Princeton University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in PRSO for personal use. Subscriber: null; date: 28 March 2020

(p.373) Chapter Twenty Exercises

(p.373) Chapter Twenty Exercises

Chapter:
(p.373) Chapter Twenty Exercises
Source:
Benford's Law
Author(s):
Steven J. Miller
Publisher:
Princeton University Press
DOI:10.23943/princeton/9780691147611.003.0020

Abstract and Keywords

This chapter contains a list of exercises based on the lessons from all the previous chapters as well as their possible solutions. It also contains some supplementary information or references to places where the reader might obtain the supplementary information necessary for a better understanding of the concepts introduced in this volume. In addition to this, the chapter also contains brief bibliographies to further assist the reader or instructor in completing the exercises. It must be noted that some of the problems and exercises listed in this chapter are far more accessible after the later parts of this book have been read.

Keywords:   exercises, Benford's law, bibliography, supplementary information, mathematical problems

20.1 A Quick Introduction to Benford’s Law

A couple of important points.

  • There are many problems that would fit in multiple chapters. To help both the instructors and the readers, we have decided to collect them here. Thus, some of the exercises in this chapter will be far more accessible after reading later parts of the book.

  • In Mathematica, if you define the following function you can then use it to find the first digit: firstdigit[x_] := Floor[10^Mod[Log[10,x],1]] (a similar function is definable in other languages, but the syntax will differ slightly).

Exercise 20.1.1. If X is Benford base 10, find the probability that its significand starts 2.789.

Exercise 20.1.2. If X is Benford base 10, find the probability that its significand starts with 7.5 (in other words, its significand is in [7.5, 7.6)).

Exercise 20.1.3. If X is Benford base 10, find the probability that its significand has no 7s in the first k digits (thus a significand of 1.701 would have no 7 in its first digit, but it would have a 7 in its first two digits.

Exercise 20.1.4. Consider α‎n for various α‎ and various ranges of n; for example, take α{2,3,5,10, 2 , 5 , 10 ,π,e,γ} α‎ (here γ‎ is the Euler–Mascheroni constant; see

http://en.wikipedia.org/wiki/Euler-Mascheroni_constant for a description and properties), and let n go from 1 to N, where N ∈ {103, 105, 107}. Which of these data sets do you expect to be Benford? Why or why not? Read up about chi-square goodness of fit tests (see for example

http://en.wikipedia.org/wiki/Pearson_chi_square)and compare the observed frequencies with the Benford probabilities.

(p.374) Exercise 20.1.5. Revisit the previous problem with more values of N. The problem is that there we looked at three snapshots of the behavior; it is far more interesting to plot the chi-square values as a function of N , for N ranging from say 100 to 107 or more. You will see especially interesting behavior if you look at the first digits of π‎n.

Exercise 20.1.6. We have seen that the Benford behavior of a sequence is related to equidistribution of its logarithm. Thus, in the previous problem it may be useful to look at a log-log plot. Thus instead of plotting the chi-square value against the upper bound N, plot the logarithm of the chi-square value against log N.

Exercise 20.1.7. Frequently taking logarithms helps illuminate relationships. For example, Kepler’s third law (see http://www.physicsclassroom.com/class/circles/Lesson-4/Kepler-s-Three-Laws) says that the square of the time it takes a planet to orbit a sun is proportional to the cube of the semimajor axis. Find data for these quantities for the eight planets in our system (or nine if you count Pluto!) and plot them, and then do a log-log plot. A huge advantage of log-log plots is that linear relations are easy to observe and estimate; try to find the best fit line here, and note that the slope of the line should be close to 1.5 (if T is the period and L is the length of the semimajor axis, Kepler’s third law is that there is a constant C such that T2 = CL3, or equivalently T=C L 3/2 , , or logT= 3 2 logL+logC). Revisit the original plot, and try to see that it supports T 2 is proportional to L3!

Exercise 20.1.8. Prove the log-laws: if logb xi = yi and r > 0 then

  • logb b = 1 and logb1 = 0 (note logb x = y means x = by);

  • logb(xr) = r logb x;

  • logb(x1x2) = logb x1 + logb x2 (the logarithm of a product is the sum of the logarithms);

  • logb(x1/x2) = logb x1−logb x2 (the logarithm of a quotient is the difference of the logarithms; this follows directly from the previous two log-laws);

  • logc x = logb x/ logb c (this is the change of base formula).

Exercise 20.1.9. The last log-law (the change of base formula) is often forgotten, but is especially important. It tells us that if we can compute logarithms in one base then we can compute them in any base. In other words, it suffices to create just one table of logarithms, so we only need to find one base where we can easily compute logarithms. What base do you think that is, and how would you compute logarithms of arbitrary positive real numbers?

Exercise 20.1.10. The previous problem is similar to issues that arise in probability textbooks. These books only provide tables of probabilities of random variables drawn from a normal distribution,1 as one can convert from such a table to probabilities for any other random variable. One such table is online here: (p.375) http://mathsisfun.com/data/standard-normal-distribution-table.html . Use a standard table to determine the probability that a normal random variable with mean μ‎ = 5 and variance σ‎2 = 16 (so the standard deviation is σ‎ = 4) takes on a value between −3 and 7. Thus, similarly to the change of base formula, there is an enormous computational saving as we only need to compute probabilities for one normal distribution.

Exercise 20.1.11. Prove d dx log b x= 1 xlogb . . Hint: First do this when b = e, the base of the natural logarithms; use elog x = x and the chain rule.

Exercise 20.1.12. Revisit the first two problems, but now consider some other sequences, such as n!, cos(n) (in radians of course as otherwise the sequence is periodic), n2, n3, nlog n, nlog log n, nlog log log n, nn. In some situations log4 does not mean the logarithm base 4, but rather four iterations of the logarithm function. It might be interesting to investigating nlogf(n) n under this definition for various integer-valued functions f.

Exercise 20.1.13. Revisit the previous problem but for some recurrence relations. For example, try the Fibonacci numbers (Fn+2 = Fn+1 + Fn with F0 = 0 and F1 = 1) and some other relations, such as the following.

Catalan numbers: C n = 1 n+1 ( 2n n ); these satisfy a more involved recurrence

(see http://en.wikipedia.org/wiki/Catalan_number).

Squaring Fibonaccis: G n+2 = G n+1 2 + G n 2 with G0 = 0 and G1 = 1.

  • Fp where p is a prime (i.e., only look at the Fibonaccis at a prime index).

  • The logistic map: xn+1 = rxn(1−xn) for various choices of r and starting values x0 (see http://en.wikipedia.org/wiki/Recurrence_relation).

  • Newton’s method for the difference between the nth prediction and the true value. For example, to find the square root of α‎ we use x n+1 = 1 2 ( x n + α x n ), and thus we would study the distribution of leading digits of | α x n |. One could also look at other roots, other numbers, or more complicated functions. For more on Newton’smethod, see http://mathworld.wolfram.com/NewtonsMethod.html.

  • The 3x + 1 Map: xn+1 = 3xn + 1 if xn is odd and xn/2 if xn is even (though some authors use a slightly different definition, where for xn even, one instead lets xn+1 = xn/2d, where d is the highest power of 2 dividing xn). It is conjectured that no matter what positive starting seed x0 you take, eventually xn cycles among 4, 2, and 1 for n sufficiently large (or is identically 1 from some point onward if we use the second definition). We return to this problem in Chapter 3.

(p.376) For the remaining problems, whenever a data set satisfies Benford’s Law we mean the strong version of the law. This means the cumulative distribution function of the significand is FX(s) = log10(s) for s ∈ [1, 10), which implies that the probability of a first digit of d is log10(1 + 1/d).

Exercise 20.1.14. If a data set satisfies (the strong version of) Benford’s Law base 10, what are the probabilities of all pairs of leading digits? In other words, what is the probability the first two digits are d1d2 (in that order)? What if instead our set were Benford base b?

Exercise 20.1.15. Let X be a random variable that satisfies (the strong version of) Benford’s Law. What is the probability that the second digit is d? Note here that the possible values of d range from 0 to 9.

Exercise 20.1.16. Building on the previous problem, compute the probability that a random variable satisfying the strong version of Benford’s Law has its kth digit equal to d. If we denote these probabilities by pk(d), what is limk→∞ pk(d)? Prove your claim.

Exercise 20.1.17. Find a data set that is spread over several orders of magnitude, and investigate its Benfordness (for example, stock prices or volume traded on a company that has been around for decades).

Exercise 20.1.18. Look at some of the data sets from the previous exercises that were not Benford, and see what happens if you multiply them together. For example, consider n2 ·cos(n) (in radians), or n2 √10n cos(n), or even larger products. Does this support the claim in the chapter that products of random variables tend to converge to Benford behavior?

Exercise 20.1.19. Let μ‎k;b denote the mean of significands of k digits of random variables perfectly satisfying Benford’s Law, and let μ‎b denote the mean of the significands of random variables perfectly following Benford’s Law. What is μ‎k;b for k ∈ 1, 2, 3? Does μ‎k;b converge to μ‎b? If yes, bound |μ‎k;b − μ‎b| as a function of k.

Exercise 20.1.20. Benford’s Law can be viewed as the distribution on significands arising from the density p(x)= 1 xlog(10) on [1, 10) (and 0 otherwise). More generally, consider densities pr(x) = Cr/xr for x ∈ [1, 10) and 0 otherwise with r ∈ (−∞,∞), where Cr is a normalization constant so that the density integrates to 1. For each r, calculate the probability of observing a first digit of d, and calculate the expected value of the first digit.

20.2 A Short Introduction to The Mathematical Theory of Benford’s Law

For a more detailed development of this material, see An Introduction to Benford’s Law [BerH5] by Berger and Hill.

(p.377) 20.3 Fourier Analysis and Benford’s Law

20.3.1 Problems from Introduction to Fourier Analysis

The following exercises are from the chapter “An Introduction to Fourier Analysis,” from the book An Invitation toModern Number Theory (Princeton University Press, Steven J. Miller and Ramin Takloo-Bighash). This chapter is available online on the web page for this book (go to the links for Chapter 3).

Exercise 20.3.1. Prove ex converges for all x ∈ ℝ (even better, for all x ∈ C). Show the series for ex also equals

(18.1)
lim n ( 1+ x n ) n ,

which you may remember from compound interest problems.

Exercise 20.3.2. Prove, using the series definition, that ex+y = exey and calculate the derivative of ex.

Exercise 20.3.3. Let f, g, and h be continuous functions on [0, 1], and a, b ∈ C. Prove

1. ⟨f, f⟩ ≥ 0, and equals 0 if and only if f is identically zero;

2. f,g= g,f ¯ ;

  1. 3. ⟨af + bg, h⟩ = a⟨f, h⟩ + b⟨g, h⟩.

Exercise 20.3.4. Find a vector v =( v 1 v 2 )  2 such that v 1 2 + v 2 2 =0, but v , v 0.

Exercise 20.3.5. Prove xn and xm are not perpendicular on [0, 1]. Find a c ∈ ℝ such that xn − cxm is perpendicular to xm; c is related to the projection of xn in the direction of xm.

Exercise 20.3.6 (Important). Show for m, n ∈ 𝔸 that

(20.2)
e m (x), e n (x)={ 1ifm=n, 0otherwise.

Exercise 20.3.7. Let f and g be periodic functions with period a. Prove α‎f(x) + β‎g(x) is periodic with period a.

Exercise 20.3.8. Prove any function can be written as the sum of an even and an odd function.

Exercise 20.3.9. Show

(20.3)
f(x) f ^ (n) e n (x), e n (x)=0.

This agrees with our intuition: after removing the projection in a certain direction, what is left is perpendicular to that direction.

(p.378) Exercise 20.3.10. Prove 1. ⟨f(x) − SN(x), en(x)⟩ = 0 if |n| ≤ N; 2. | f ^ (n)| 0 1 | f(x)|dx;

  1. 3. Bessel’s Inequality: if ⟨f, f⟩ < ∞ then n= | f ^ (n) | 2 f,f;

  2. 4. Riemann–Lebesgue Lemma: if ⟨f, f⟩ < ∞ then lim|n|→∞ f(n) = 0 (this holds for more general f; it suffices that 0 1 | f(x)|dx<);

  3. 5. Assume f is differentiable k times; integrating by parts, show | f ^ (n)| 1 n k and the constant depends only on f and its first k derivatives.

Exercise 20.3.11. Let h(x) = f(x) + g(x). Does h ^ (n)= f ^ (n)+ g ^ (n)? Let k(x) = f(x)g(x). Does k ^ (n)= f ^ (n) g ^ (n)?

Exercise 20.3.12. If ⟨f, f⟩, ⟨g, g⟩ < ∞ then the dot product of f and g exists: ⟨f, g⟩ < ∞ (see Remark 11.2.4 of [MiT-B]). Do there exist f, g : [0, 1] → C such that 0 1 | f(x)|dx, 0 1 | g(x)|dx<but 0 1 f (x) g ¯ (x)dx=? Is f ∈ L2([0, 1]) a stronger or an equivalent assumption to f ∈ L0, 1?

Exercise 20.3.13. Define

(20.4)
A N (x)={ Nfor|x| 1 N , 0otherwise.

Prove AN is an approximation to the identity on [ 1 2 , 1 2 ]. If f is continuously differentiable and periodic with period 1, calculate

(20.5)
lim N 1 2 1 2 f (x) A N (x)dx.

Exercise 20.3.14. Let A(x) be a non-negative function with A (x)dx=1. Prove AN(x) = N · A(Nx) is an approximation to the identity on R.

Exercise 20.3.15 (Important). Let AN(x) be an approximation to the identity on [ 1 2 , 1 2 ]. Let f(x) be a continuous function on [ 1 2 , 1 2 ]. Prove

(20.6)
lim N 1 2 1 2 f (x) A N (x)dx=f(0).

Exercise 20.3.16. Prove the two formulas above. The geometric series formula will be helpful:

(20.7)
n=N M r n = r N r M+1 1r .

Exercise 20.3.17. Show that the Dirichlet kernels are not an approximation to the identity. How large are 0 1 | D N (x)|dxand 0 1 D N (x) 2 dx?

(p.379) Exercise 20.3.18. Prove the Weierstrass Approximation Theorem implies the original version of the Weierstrass Theorem.

Exercise 20.3.19. Let f (x) be periodic function with period 1. Show

(20.8)
S N ( x 0 )= 1 2 1 2 f (x) D N (x x 0 )dx=  1 2 1 2 f ( x 0 x) D N (x)dx.

Exercise 20.3.20. Let f ^ (n)= 1 2 |n| . Does f ^ (n) e n (x) converge to a continuous, differentiable function? If so, is there a simple expression for that function?

Exercise 20.3.21. Fill in the details for the above proof. Prove the result for all f satisfying 0 1 | f(x) | 2 dx<.

Exercise 20.3.22. If 0 1 | f(x) | 2 dx<, show Bessel’s Inequality implies there exists a B such that | f ^ (n)|B for all n.

Exercise 20.3.23. Though we used |a+b|2 ≤ 4|a|2 + 4|b|2, any bound of the form c|a|2 + c|b|2 would suffice. What is the smallest c that works for all a, b ∈ C?

Exercise 20.3.24. Let f(x) =  1 2 | x |on[ 1 2 , 1 2 ]. Calculate n=0 1 (2n+1) 2 . Use this to deduce the value of n=1 1 n 2 . This is often denoted ζ‎(2) (see Exercise 3.1.7 of [MiT-B]). See [BoPo]2 for connections with continued fractions, and [Kar]3 for connections with quadratic reciprocity.

Exercise 20.3.25. Let f(x) = x on [0, 1]. Evaluate n=1 1 n 4 .

Exercise 20.3.26. Let f(x) = x on [ 1 2 , 1 2 ]. . Prove π 4 = n=1 (1) n+1 (2n1) 2 . See also Exercise 3.3.29, and see Chapter 11 of [BorB]4 or [Schum]5 for a history of calculations of π‎.

Exercise 20.3.27. Find a function to determine n=1 1 n 4 .

Exercise 20.3.28. Show the Gaussian f(x)= 1 2π σ 2 e (xμ) 2 /2 σ 2 is in S(R) for any μ‎, σ‎ ∈ ℝ.

Exercise 20.3.29. Let f (x) be a Schwartz function with compact support contained in [−σ‎, σ‎] and denote its Fourier transform by f(y). Prove for any integer A > 0 that | f ^ (y)| c f y A , where the constant cf depends only on f, its derivatives and σ‎. As such a bound is useless at y = 0, one often derives bounds of the form | f ^ (y)| c f ˜ (1+|y|) A .

(p.380) Exercise 20.3.30. Consider

(20.9)
f(x)={ n 6 ( 1 n 4 |nx| )if|xn| 1 n 4 forsomen, 0otherwise.

Show f(x) is continuous but F(0) is undefined. Show F(x) converges and is well defined for any x ∈ 𝔸.

Exercise 20.3.31. If g(x) decays like x−(1+η‎) for some η‎ > 0, then G(x) =n∈Z g(x + n) converges for all x, and is continuous.

Exercise 20.3.32. For what weaker assumptions on f, f', f" does n f (n)= n f ^ (n)?

Exercise 20.3.33. One cannot always interchange orders of integration. For simplicity, we give a sequence amn such that m ( n a m,n ) n ( m a m,n ) . For ≥ mn nm m, n 0 let

(20.10)
a m,n ={ 1ifn=m, 1ifn=m+1$, 0otherwise.

Show that the two different orders of summation yield different answers (the reason for this is that the sum of the absolute value of the terms diverges).

Exercise 20.3.34. Find a family of functions x) such that fn(

(20.11)
lim n f n (x)dx lim n f n (x)dx

and each fn(x) and f(x) is continuous and |fn(x)|, |f(x)| ≤ M for some M and all x.

Exercise 20.3.35. Let f, g be continuous functions on I = [0, 1] or I = R. Show if f, f, g, g < ∞then h = f ∗g exists. Hint: Use the Cauchy–Schwarz inequality. Show further that h ^ (n)= f ^ (n) g ^ (n) if I = [0, 1] or if I = R. Thus the Fourier transform converts convolution to multiplication.

Exercise 20.3.36. Let X 1,X2 be independent random variables with density p. Prove

(20.12)
Prob( X 1 + X 2 [a,b])= a b (pp)(z) dz.

Exercise 20.3.37 (Important). If for all i = 1, 2, … we have fi, fi < ∞, prove for all i and j that fi ∗ fj, fi ∗ fj < ∞. What about f1 ∗ (f2 ∗ f3) (and so on)? Prove f1 ∗ (f2 ∗ f3) = (f1 ∗ f2) ∗ f3. Therefore convolution is associative, and we may write f1 ∗ ···∗ fN for the convolution of N functions.

Exercise 20.3.38. Suppose X1, … , XN are i.i.d.r.v. from a probability distribution p on R. Determine the probability that X1 + · · · + XN ∈ [a, b]. What must be assumed about p for the integrals to converge?

(p.381) Exercise 20.3.39. One useful property of the Fourier transform is that the derivative of ĝ is the Fourier transform of 2π‎ixg(x); thus, differentiation (hard) is converted to multiplication (easy). Explicitly, show

(20.13)
g ^ (y)=\ 2 πixg(x) e 2πixy dx.

If g is a probability density, note g ^ (0)=2πiE[x]and g ^ (0)=4 π 2 E[ x 2 ].

Exercise 20.3.40. If B(x) = A(cx) for some fixed c = 0, show B ^ (y)= 1 c A ^ ( y c ). .

Exercise 20.3.41. Show that if the probability density of X1 + · · · + XN = x is (p ∗ · · · ∗ p)(x) (i.e., the distribution of the sum is given by p ∗ · · · ∗ p), then theprobability density of X 1 ++ X N N =x x is ( ( N p N p)(x N ). By Exercise 20.3.40, show

(20.14)
FT[ ( N p N p)(x N ) ](y)= [ p ^ ( y N ) ] N .

Exercise 20.3.42. Show for any fixed y that

(12.15)
lim N [ 1 2 π 2 y 2 N +O( y 3 N 3/2 ) ] N = e 2 π 2 y 2 .

Exercise 20.3.43. Show that the Fourier transform of e−2π‎2y2 at x is 1 2π e x 2 /2 .

Hint: This problem requires contour integration from complex analysis.

Exercise 20.3.44. Modify the proof to deal with the case of p having mean μ‎ and variance σ‎2.

Exercise 20.3.45. For reasonable assumptions on p, estimate the rate of convergence to the Gaussian.

Exercise 20.3.46. Let be two probability densities satisfying p1, p2

(20.16)
x p i (x)dx=0, x 2 p i (x)dx=1, | x | 3 p i (x)dx<.

Consider SN = X1 +· · ·+XN, where for each i, X1 is equally likely to be drawn randomly from p1 or p2. Show the Central Limit Theorem is still true in this case. What if we instead had a fixed, finite number of such distributions p1, … , pk, and for each i we draw Xi from pj with probability qj (of course, q1 + · · · + qk = 1)?

Exercise 20.3.47 (Gibbs Phenomenon). Define a periodic with period 1 function by

(20.17)
f(x)={ 1if 1 2 x<0, 1if0x< 1 2 .

Prove that the Fourier coefficients are

(20.18)
f ^ (x)={ 0ifniseven 4 nπi ifnisodd.

(p.382) Show that the Nth partial Fourier series SN(x) converges pointwise to f (x) wherever f is continuous, but overshoots and undershoots for x near 0. Hint: Express the series expansion for SN(x) as a sum of sines. Note sin(2mπx) 2mπ = 0 x cos (2mπt)dt. Express this as the real part of a geometric series of complex exponentials, and use the geometric series formula. This will lead to

(20.19)
S 2N1 (x)= 8 0 x ( 1 2i e 4nπit 1 sin(2πt) )dt=4 0 x sin(4nπt) sin(2πt) dt,

which is about 1.179 (or an overshoot of about 18%) when x= 1 4nπ . What can you say about the Fejér series TN(x) for x near 0?

Exercise 20.3.48 (Nowhere Differentiable Function). Weierstrass constructed a continuous but nowhere differentiable function! We give a modified example and sketch the proof. Consider

(20.20)
f(x)= n=0 a n cos( 2 n 2πx), 1 2 <a<1.

Show f is continuous but nowhere differentiable. Hint: First show |a| < 1 implies f is continuous. Our claim on f follows from noting that if a periodic continuous function g is differentiable at x0 and g ^ (n)=0 unless n = ±2m, then there exists C such that for all n, | g ^ (n)|Cn 2 n . To see this, it suffices to consider x0 = 0 and g(0) = 0. Our assumptions imply that (g, em) = 0 if 2n−1 < m < 2n+1 and m = 2n. We have g ^ ( 2 n )=(g, e 2 n F 2 n1 (x)) where FN is the Fejér kernel. The claim follows from bounding the integral (g, e2nF2n−1(x)). In fact, more is true: Baire showed that, in a certain sense, “most” continuous functions are nowhere differentiable! See, for example, [Fol].6

Exercise 20.3.49 (Isoperimetric Inequality). Let γ‎(t) = (x(t), y(t)) be a smooth closed curve in the plane; we may assume it is parametrized by arc length and has length 1. Prove the enclosed area A is largest when γ‎(t) is a circle. Hint: By Green’s Theorem

(20.21)
γ x dyydx =2Area(A).

The assumptions on γ‎(t) imply x(t), y(t) are periodic functions with Fourier series expansions and ( dx dt ) 2 + ( dy dt ) 2 =1. . Integrate this equality from t = 0 to t = 1 to obtain a relation among the Fourier coefficients of dx dt and dx dt (which are related to those of x(t) and y(t)); (20.21) gives another relation among the Fourier coefficients. These relations imply 4π‎Area(A) ≤ 1 with strict inequality unless the Fourier coefficients vanish for |n| > 1. After some algebra, one finds this implies we have a strict inequality unless γ‎ is a circle.

Exercise 20.3.50 (Applications to Differential Equations). One reason for the introduction of Fourier series was to solve differential equations. Consider the vibrating string problem: a unit string with endpoints fixed is stretched into some (p.383) initial position and then released; describe its motion as time passes. Let u(x, t) denote the vertical displacement from the rest position x units from the left endpoint at time t. For all t we have u(0, t) = u(1, t) = 0 as the endpoints are fixed. Ignoring gravity and friction, for small displacements Newton’s laws imply

(20.22)
2 u(x,t) x 2 = c 2 2 u(x,t) t 2 ,

where c depends on the tension and density of the string. Guessing a solution of the form

(20.23)
u(x,t)= n=1 a n (t)sin(nπx),

solve for an(t). One can also study problems on R by using the Fourier transform. Its use stems from the fact that it converts multiplication to differentiation, and vice versa: if g(x) = f(x) and h(x) = xf(x), prove that g ^ (y)=2πiy f ^ (y) and d f ^ (y) dy =2πi h ^ (y). This and Fourier inversion allow us to solve problems such as the heat equation

(20.24)
u(x,t) t = 2 u(x,t) x 2 ,x,t>0

with initial conditions u(x, 0) = f(x).

20.3.2 Problems from Chapter 1: Revisited

Many of the problems from Chapter 1 are appropriate here as well. In addition to reexamining those problems, consider the following.

Exercise 20.3.51. Is the sequence an = nlog n Benford?

Exercise 20.3.52. In some situations log4 does not mean the logarithm base 4, but rather four iterations of the logarithm function. Investigate nlogf(n) n under this definition for various integer-valued functions f.

20.3.3 Problems from Chapter 3

Exercise 20.3.53. Assume an infinite sequence of real numbers {xn} has its logarithms modulo 1, {yn = log10 xn mod 1}, satisfying the following property: as n → ∞the proportion of yn in any interval [a, b] ⊂ [0, 1] converges to b − a if b −a > 1/2. Prove or disprove that {xn} is Benford.

Exercise 20.3.54. As 2 is irrational, the sequence {xn = nChapter Twenty Exercises} is uniformly distributed modulo 1. Is the sequence { x n 2 } uniformly distributed modulo 1?

Exercise 20.3.55. Does there exist an irrational α‎ such that α‎ is a root of a quadratic polynomial with integer coefficients and the sequence { α n } n=1 is Benford base 10?

(p.384) Exercise 20.3.56. We showed a geometric Brownian motion is a Benford-good process; is the sum of two independent geometric Brownian motions Benford-good?

The next few questions are related to a map we now describe. We showed that, suitably viewed, the 3x + 1 map leads to Benford behavior (or is close to Benford for almost all large starting seeds). Consider the following map. Let R(x) be the number formed by writing the digits of x in reverse order. If R(x) = x we say x is palindromic. If x is not a palindromic number set P(x) = x + R(x), and if x is palindromic let P(x) = x. For a given starting seed x0 consider the sequence where xn+1 = P(x). It is not known whether there are any x0 such that the resulting sequence diverges to infinity, though it is believed that almost all such numbers do. The first candidate to escape is 196; for more see http://en.wikipedia.org/wiki/Lychrel_number (this process is also called “reverse-and-add,” and the candidates are called Lychrel numbers).

Exercise 20.3.57. Consider the reverse-and-add map described above applied to a large starting seed. Find as good of a lower bound as you can for the number of seeds between 10n and 10n+1 such that the resulting sequence stabilizes (i.e., we eventually hit a palindrome).

Exercise 20.3.58. Come up with a model to estimate the probability a given starting seed in 10n and 10n+1 has its iterates under the reverse-and-add map diverge to infinity. Hint: x plus R(x) is a palindrome if and only if there are no carries when we add; thus you must estimate the probability of having no carries.

Exercise 20.3.59. Investigate the Benfordness of sequences arising from the reverse-and-add map for various starting seeds. Of course the calculation is complicated by our lack of knowledge about this map, specifically we don’t know even one starting seed that diverges! Look at what happens with various Lychrel numbers. For each N can you find a starting seed x0 such that it iterates to a palindrome after N or more steps?

Exercise 20.3.60. Redo the previous three problems in different bases. Your answer will depend now on the base; for example, much more is known base 2 (there we can give specific starting seeds that iterate to infinity).

Exercise 20.3.61. Use the Erdös–Turan Inequality to calculate upper bounds for the discrepancy for various sequences, and use those results to prove Benford behavior. Note you need to find a sequence where you can do the resulting computation. For example, earlier we investigated an = nlog n; are you able to do the summation for this case?

Exercise 20.3.62. Consider the analysis of products of random variables. Fix a probability p (maybe p = 1/2), and independent identically distributed random variables X1, …,Xn. Assume as n → ∞the product of the Xi’s becomes Benford. What if now we let X n ˜ be the random variable where we toss n independent coins, each with probability p, and if the ith toss is a head then Xi is in the product (if the product is empty we use the standard convention that it is then 1). Is this process Benford?

(p.385) Exercise 20.3.63. Redo the previous problem, but drop the assumption that the random variables are identically distributed.

Exercise 20.3.64. Redo the previous two problems, but now allow the probability that the ith toss is a head to depend on i.

Exercise 20.3.65. Consider

(20.25)
ϕ m ={ mif|x 1 8 | 1 2m , 0otherwise;

this is the function from Example 3.3.5 and led to non-Benford behavior for the product. Can you write down the density for the product?

Exercise 20.3.66. In the spirit of the previous problem, find other random variables where the product is not Benford.

Exercise 20.3.67. Consider a Weibull random variable with a scale parameter α‎ of 1 and translation parameter β‎ of 0; so f(x; γ‎) = xγ‎−1 exp(xγ‎) for x ≥ 0 and is zero otherwise. Investigate the Benfordness of chaining random variables here, where the shape parameter γ‎ is the output of the previous step.

Exercise 20.3.68. The methods of [JaKKKM] led to good bounds for chaining exponential and uniform random variables. Can you obtain good, explicit bounds in other cases? For example, consider a binomial process with fixed parameter p.

Exercise 20.3.69. Apply the methods of Cuff, Lewis, and Miller (for the Weibull distribution) to other random variables. Consider the generalized Gamma distribution (see http://en.wikipedia.org/wiki/Generalized_gamma_distribution for more information), where the density is

f(x;a,d,p)= p/ d a Γ(d/p) x d1 exp( (x/a) p )

for x > 0 and 0 otherwise, where a, d, p are positive parameters.

For the next few problems, let fr(x) − 1/(1 + |x|r) with r > 1.

Exercise 20.3.70. Show that for

Chapter Twenty Exercises

Exercise 20.3.71. Verify the Fourier transform identity used in our analysis:

p r ( e b+y ) e b+y = 1 2 sin( π r ) e 2πiby csc( π r ( 12πiy ) ),

where b ∈ [0, 1].

(p.386) 20.4 Benford’s Law Geometry

Exercise 20.4.1. Perform a chi-square goodness-of-fit test on the data values in Table 4.1.

Exercise 20.4.2. Let the random variable X have the Benford distribution as defined in this chapter. Find E[X]. Next, generate one million Benford random variates and compute their sample mean. Perform this Monte Carlo experiment several times to ensure that the sample means are near E[X].

Exercise 20.4.3. Let T ∼ exponential(1). Find the probability mass function of the leading digit to three-digit accuracy. Compare your results to those in Table 4.2.

Exercise 20.4.4. Redo the previous exercise, but instead of finding the probability mass function of the leading digit, find the cumulative distribution function of the significand (i.e., find the probability of observing a significand of at most s).

Exercise 20.4.5. Determine the set of conditions on a, b, and c associated with W ∼ triangular(a, b, c) which result in T = 10W following Benford’s Law.

Exercise 20.4.6. Use R to confirm that the cumulative distribution function Fx(x) = Prob(X ≤ x) = log10(x + 1) results in a probability mass function that gives the distribution specified in Benford’s Law. What is the range of x?

Exercise 20.4.7. Use R to determine whether the cumulative distribution function Fx(x) = Prob(X ≤ x) = x2 (for some range for x) results in a probability mass function that gives the distribution specified in Benford’s Law. If yes, what is the range for x?

Exercise 20.4.8. Which of the following distributions of W follow Benford’s Law?

  • fW(w) ∼ U(0, 3.5).

  • fW(w) ∼ U(17, 117).

  • fW(w) = w3−w2+w for 0 ≤ w ≤ 1, and 1−w3+w2−w for 1 ≤ w ≤ 2.• fW(w) = w for 0 ≤ w ≤ 1, and 1 − w1 for 1 ≤ w ≤ 2.

Exercise 20.4.9. Let b1 and b2 be two different integers exceeding 1. Is there a probability density p on an interval I such that if a random variable X has p for its probability density function then X is Benford in both base b1 and b2? What if the two bases are allowed to be real numbers exceeding 1? Prove your claims.

20.5 Explicit Error Bounds Via Total Variation

Exercise 20.5.1. Find TV(sin(x), [−π‎, π‎]).

Exercise 20.5.2. Confirm that TV(h, J) = TV+(h, J) +TV(h, J).

(p.387) Exercise 20.5.3. Let Yo and Z be independent random variables such that Yo has a density fo with TV(fo) < ∞ and Z has distribution π‎. Verify that Y := Yo + Z ? has density f(y) = fo(y − z) π‎(dz) with TV(f) ≤ TV(fo).

Exercise 20.5.4. Show that an absolutely continuous probability density f on R satisfies

TV (f) 2 f (x) 2 f(x) dx.

Exercise 20.5.5. Let γ‎a,σ‎ be the density of the Gamma distribution Gamma(a, σ‎) with shape parameter a > 0 and scale parameter σ‎ > 0, i.e.,

γ a,σ (x)= σ a x a1 exp(x/σ)/Γ(a)

  1. 1. Show that for a ≥ 1, TV(γ‎a,σ‎) = σ‎−1 TV(γ‎a,1) and TV(γ‎a,1) = 2((a − 1)/e)a−1/Γ‎(a).

2. It is well known that Γ‎(t+1) = (t/e)tChapter Twenty Exercises1+o(1)) as t→∞(this is Stirling’s formula). What does this imply for TV(γ‎a,1)? Show that TV( γ a,σ )0as a σanda1.

Exercise 20.5.6. Let X be a strictly positive random variable with density h on (0,∞). Verify that Y := logB(X) has density f given by f(y) = log(B)Byh(By) for y ∈ ℝ.

Exercise 20.5.7. Let X be a random variable with distribution Gamma(a, σ‎) for some a, σ‎ > 0; see Exercise 20.5.5.

  1. 1. Determine the density fa,σ‎ of Y := logB(X). Here you should realize that fa,σ‎(y) = fa,1(y − logB(σ‎)). Show then that

TV( f a,σ )=2log(B) (a/e) a /Γ(a).

What happens as a→∞?

  1. 2. To understand why the leading digits of X=σ(a+ a Z a ) a) for a random variable Za with mean zero and variance one. (Indeed, the density of Za converges uniformly to the standard Gaussian density as a → ∞.) Now investigate the distribution of Y = logB(X) as a→∞.

20.6 Lévy Processes and Benford’s Law

Exercise 20.6.1. Provide an example of a non-continuous cadlag function.

Exercise 20.6.2. Prove that a Weiner process is also a Lévy process.

Exercise 20.6.3. Prove that a Poisson process is also a Lévy process.

(p.388) Exercise 20.6.4. Prove that the exponential Lévy process {exp(Xt)} (t ∈ ℝ) is a martingale with respect to (Ft) := σ‎{Xs : s ≤ t} if and only if E[exp(Xt)] = 1.

Exercise 20.6.5. Let f(t) = E[exp(itξ‎)], g(t) = E[exp(itη‎)] ( t ∈ ℝ) be the characteristic functions of (real-) valued random variables ξ,η(i= 1 ). Recall that exp(it) = cost + i sin t (t ∈ ℝ) and E[exp(itξ‎)] := E[cos(tξ‎)] + iE[sin(tξ‎)] (t ∈ ℝ). Finally, a+ib ¯ := a  ib ( a, b   ) denotes the complex conjugate of a + ib. Note that |f|2(t) = f(t) · f¯ (t). Show the following.

  1. 1. f is continuous, f(0) = 1, and |f(t)| ≤ 1, t ∈ ℝ.

  2. 2. f ¯ is a characteristic function.

  3. 3. f · g is a characteristic function. Hence, |f|2is a characteristic function.

  4. 4. Let h1, h2, … be characteristic functions. If a1 ≥ 0, a2 ≥ 0, … are real numbers such that a1+a2+· · · = 1, then a1h1+a2h2+· · · is a characteristic function.

  5. 5. Show that every characteristic function h is non-negative definite, i.e., for all n ≥ 2, real t1, … , tn, and complex a1, … , an we have that

j=1 n k=1 n h ( t j t k ) a j a ¯ k 0.

Exercise 20.6.6. Show that, for each real numberp > 0, f(z) := cos(2π‎pz) (z ∈ ℝ) is a characteristic function. Deduce that g(z) := (cos(2π‎pz))2 (z ∈ ℝ) is a characteristic function.

Exercise 20.6.7. (This exercise gives an example of a characteristic function which “wildly fluctuates.”) It follows from Exercises 20.6.6 and 20.6.5(4) that

h(z):= k=1 2 k (cos(2π 7 k z)) 2 ,z

is a characteristic function. Show that h is of infinite total variation over each non-degenerate interval [a, b], i.e.,

sup{ k=1 n | h( z k+1 )h( z k )| }=,

the supremum taken over all n ≥ 1 and real numbers a ≤ z1 < z2 < · · · < zn+1 ≤ b.

Hint: It suffices to prove the claim for intervals [r + 7−N, r + 2 · 7−N] (being convenient for calculations!) where N ≥ 1 is an integer and r ≥ 0 a real number. Let k ≥ N+1 and denote by I(k) the set of integers j such that 1+(r+7−N)7k < j ≤ ((r+2·7−N)7k). For j ∈ I(k) put t2j−1(k) = (j−1/4)7−k, t2j(k) = j ·7−k. Show, by using the inequalities |a + b| ≥ |a| − |b| and |(cos b)2 − (cos a)2| ≤ 2|b − a| (a, b ∈ ℝ) that

jI(k) | h( t 2j (k))h( t 2j1 (k))|2(1π/5) 7 N (7/2) k +const.

(p.389) Exercise 20.6.8. 1. Try to guess how the integral a b f(z)exp(itz)dz behaves as t→∞if f : [a, b] → R is a step function of the form f(t) = j=1 m c j I [b j -1 ,b j  ) (t) where a ≤ b0 < b1 < · · · < bm ≤ b.

  1. 2. Verify your guess when f is an indicator function of an interval.

  2. 3. How does the above integral behave when f is continuous on [a, b]?

Exercise 20.6.9. Show that a Lévy measure Q satisfies Q(R r (−α‎, α‎)) < ∞ for all α‎ > 0.

Exercise 20.6.10. Let X be a Lévy process having Lévy measure Q. Show that, for fixed c > 0 and s ≥ 0, the process X given by X= − (t ≥ 0) is a t Xct+s- Xs Lévy process having Lévy measure Q= cQ.

Exercise 20.6.11. Let N = (Nt) (t ≥ 0) be a Poisson process with parameter λ‎ > 0.

  1. 1. Verify that the generating triple of N is given by (λ‎, 0,Q) where Q has total mass λ‎ concentrated on {1}.

  2. 2. Verify (6.15) directly for X = N, i.e.,

holds for all c > 0, s ≥ 0, and every Borel set A ⊂ R.

Q * (A)= c 1  E[#{s<ts+c:Δ N t Ar{0}]

Exercise 20.6.12. Let Tt = T t = j=1 N t ς j ( t  0 ) (t ≥ 0) denote the compound Poisson process of Example 6.1.21. (Here, (Nt) is a Poisson process with parameter λ‎ > 0; ζ‎1, ζ‎2, … are independent random variables with a common distribution Q1 such that Q1({0}) = 0.Furthermore, the processes (ζ‎n) and (Nt) are independent of each other.)

  1. 1. Show that the characteristic function gt of Tt (t ≥ 0) is given by

g t (z)=exp[ λt ( e izx 1) Q 1 (dx) ]

  • for all z ∈ ℝ and t ≥ 0.

  • 2. It can be shown (see the reference in Example 6.1.21) that (Tt) is a Lévy process. Determine its generating triple (β‎, σ‎2,Q).

Exercise 20.6.13. Let W be a (standard) Brownian motion (BM). Show that, for each c > 0,W = (cWt/c2) is a BM (scaling property).

Exercise 20.6.14. Let ξ‎ ∼ N(μ‎, σ‎2) where μ‎ ∈ ℝ andσ‎ > 0.

  1. 1. Deduce from (6.26) that the characteristic function of ξ‎ is given by

E[exp(izξ)]=exp(iμz σ 2 z 2 /2),z.

  1. (p.390) 2.Deduce from the result in (1) that, for all μ‎, z ∈ ℝ andσ‎ > 0,

cos (zx)exp( (xμ) 2 /(2 σ 2 ))dx= 2π σ 2 cos(μz)exp( σ 2 z 2 /2)

  • and

sin (zx)exp( (xμ) 2 /(2 σ 2 ))dx= 2π σ 2 sin(μz)exp( σ 2 z 2 /2).

Exercise 20.6.15. Let W = (Wt) be a BM. Put

S t,u := sup 0su | W t+s W t |,t0,u>0.

  1. 1. Show that St,u is a random variable. (This requires a little argument since the definition of St,u involves uncountably many random variables!) Hint: Recall that all sample paths of W are continuous.

  2. 2. Show that Wn/n → 0 (n→∞) a.s.

  3. 3. Since, for each fixed t ≥ 0, (Wu+t −Wt) (u ≥ 0) is a BM, it follows that for each t > 0, St,1 has the same distribution as S0,1. (∗) Furthermore, we have that

(**)
P( S 0,1 a)2exp( a 2 /2),a0

(see, e.g., [KaSh]). Use (2) as well as (∗) and (∗∗) to show that Wt/t → 0 (t→∞) a.s.

W t /t 0(t )a.s.

Hint: Use the Borel–Cantelli Lemma.

Exercise 20.6.16. Let ξ‎1, ξ‎2, … be independent random variables defined on some probability space (Ω‎,F, P), which have a common distribution given by P(ξ‎n = +1) = p, P(ξ‎n = −1) = 1 − p =: q (n ≥ 1), where 0 < p < 1. Put Sn := ξ‎1 + · · · + ξ‎n, n ≥ 0 (S0 = 0and let (F),n) (n ≥ 0) be the filtration generated by (ξ‎n). (Note that F0 = {∅,Ω‎}.)

  1. 1. Show that Yn := (q/p)Sn (n ≥ 0) is an (Fn)-martingale.

  2. 2. Put c(α‎) := E[exp(αξ‎1)] = p exp(α‎) + q exp(−α‎) (α‎ ∈ ℝ). Show that, for every fixed α‎ ∈ ℝ, Zn := exp(α‎Sn)/(c(α‎))n (n ≥ 0) is an (Fn)-martingale.

Z n :=exp(α S n )/ (c(α)) n (n0)

Exercise 20.6.17. Let ξ‎1, ξ‎2, … be independent random variables defined on the same probability space, which have a common distribution given by P(ξ‎n = +1) = P(ξ‎n = −1) = 1/2. Put S0 = 0 and Sn = ξ‎1 + · · · + ξ‎n (n ≥ 1) which means that (Sn) is a simple symmetric random walk on Z, starting at 0. Let (Fn) be the filtration generated by (ξ‎n). Show that following two sequences are (Fn)martingales:

  1. (p.391) 1. (S− 3nSn).

  2. 2. (S− 6nS+ 3n2 + 2n).

Hint: Note that E[ξ‎n|Fn−1] = E[ξ‎n] = 0 a.s. (since ξ‎n is independent of Fn−1), and that E[ S n1 2 ξ n | F n1 ]= S n1 2 E[ ξ n ]=0 a.s. (since Sn−1 is Fn−1-measurable). Note that Sn = Sn−1 + ξ‎n.

Exercise 20.6.18. Let (Ω‎,F, P) be a probability space and let (Fn) (n ≥ 0) be any filtration on (Ω‎,F). In the sequel let Z = (Zn) (n ≥ 0) and H = (Hn) (n ≥ 1) be sequences of random variables defined on (Ω‎,F) such that Z is adapted and H is predictable which means that, for all n ≥ 1, Hn is Fn−1-measurable. The sequence H • Z given by

(HZ) n := j=1 n H j ( Z j Z j1 ),n0( (HZ) 0 =0)

is called the H-transformof Z or the (discrete) stochastic integral of H with respect to Z. Nowlet Z be an (Fn)-martingale and assume that Hj(Zj−Zj−1) ∈ L1, j = 1, 2, …. Show that H • Z is an (Fn)-martingale.

Hint: Use the iteration property of conditional expectations (see Example 6.1.29).

Exercise 20.6.19. Let W = (Wt) be a BM and let (Ft) be the filtration generated by W. Show that the following processes are (Ft)-martingales:

  1. 1. (Wt).

  2. 2. (W2 t − t).

  3. 3. (W4 t − 6tW2 t + 3t2).

Hint: Note that Wt −Ws is independent of Fs (0 ≤ s ≤ t).

Exercise 20.6.20. Let (Nt) be a Poisson process with parameter λ‎ > 0, and put Mt = Nt − λ‎t (t ≥ 0). Let (Ft) be the filtration generated by (Nt).

  1. 1. Show that (Mt) is an (Ft)-martingale.

Hint: Nt − Ns is independent of Fs (0 ≤ s < t).

  • 2. Show that (M2 t − λ‎t) is an (Ft)-martingale.

  • Hint: Write M2 t −M2 s = (Mt −Ms)2 + 2Ms(Mt −Ms) (0 ≤ s < t).

Exercise 20.6.21. Let (Nt) be a Poisson process with parameter λ‎ > 0, and let c > 0 be any constant.

  1. 1. Determine the constant μ‎(c) such that the process (exp(cNt + μ‎(c)t)) (t ≥ 0) is a martingale with respect to the filtration (Ft) generated by (Nt). Hint: Use Theorem 6.1.30 and Exercise 20.6.11.

  2. 2. Verify directly that the process obtained in (1) is an (Ft)-martingale.

Hint: Use that E[exp(c(Nt − Ns))|Fs] = E[exp(c(Nt − Ns))] a.s. (0 ≤ s < t) since Nt − Ns is independent of Fs.

(p.392) Exercise 20.6.22. Let ξ‎ have a binomial distribution with parameters n ≥ 1 and 0 ≤ p ≤ 1, i.e.,

P(ξ=k)=( n k ) p k (1p) nk ,k=0,1,,n.

  1. 1. Use Azuma’s inequality (Theorem 6.3.1) to prove the following inequality which is due to H. Chernoff (Ann. Math. Statist. 23 (1952), 493507):

(*)
P(|ξnp|t)2exp(2 t 2 /n),t0,n1.

Hint: ξ‎ has the same distribution as a sum of suitable 01 random variables ξ‎1, … , ξ‎n.

  1. 2. Verify (∗) directly for n = 1.

Exercise 20.6.23. Prove (6.147).

Hint: First note that |g(z)| =: exp(I(z)), where

I(z):= 0 z cosx1 x ( log( z x ) ) r dx,z0,r>0.

Then (6.147) says that

(*)
I(z) 1 2(r+1) ( 1 ( log(2z/(3π)) ) r+1 ),z4π,r>0.

In order to prove (∗) note that the cosine is ≤ 0 on the intervals J(k) := [(2k − 1)π‎ − π‎/2, (2k − 1)π‎ + π‎/2], and that

(**)
J(k)[0,z]iff1kk(z):= z/(2π)+1/4 .

Hence

I(z) k=1 k(z)1 J(k) 1 x ( log( z x ) ) r dx.

Using (∗∗) and comparing with a certain Riemann integral finally yields (∗).

Exercise 20.6.24. A process Zt = Z0 exp(Xt), t ≥ 0 (Z0 > 0) is observed at time points t = 0, 1, 2, …, T, where (Xt) is a Lévy process of jump-diffusion type as in Example 6.5.2. Let H0(2) denote the null hypothesis which says that there exist α‎ ∈ ℝ, c ≥ 2, λ‎ ≥ 0 and a distribution Q1 on R satisfying Q1({0}) = 0 such that (Xt) is associated with α‎, c, λ‎, and Q1. (Note that H0(2) has a meaning different from that at the beginning of Section 6.5!) Let H 0(2) be rejected if |)LT/T − p10(1)| ≥ 0.1 (see (6.100) and (6.150)). Let the level of significance be 0.1. (Note that the rejection of H0(2) entails the rejection of the null hypothesis that (Zt) is a Black–Scholes process having volatility ≥ 2; see (6.27).) How large has T to be? (Answer: T ≥ 1715.)

Exercise 20.6.25. A process Zt = Z0 exp(Xt), t ≥ 0 (Z0 > 0) is observed at the time points t = 0, 1, 2, …, T, where (Xt) = α‎t+Tt, t ≥ 0. Here, α‎ ∈ ℝ; (Tt) is a compound Poisson (or CP-)process associated with λ‎ > 0 and Q1 = N(μ‎, σ‎2) (see (p.393) Example 6.1.21). Suppose that the null hypothesis H0(λ‎, σ‎) (λ‎ > 0, σ‎ > 0) is to be tested, which says that there exist α‎ ∈ ℝ, μ‎ ∈ ℝ, λ‎ ≥ λ‎, and σ‎ ≥ σ‎ such that Xt = α‎t + Tt (t ≥ 0), and (Tt) is a CP-process associated with λ‎ and Q1. Verify that the test outlined in Exercise 20.6.24, which rejects λ‎, σ‎) if | L ˜ T /T p 10 (1) | (≥ 0.1, is not applicable no matter how the level of significance 0 < p0 < 1 is chosen.

Hint: Show that there does not exist any (finite) constant Σ‎ satisfying (6.153) (g being the characteristic function of X1, (Xt) being an arbitrary Lévy process satisfying H0(λ‎, σ‎)). Use Exercise 20.6.14(2).

Exercise 20.6.26. Suppose we observe a process Zt = Z0 exp(μ‎t + cXt), t ≥ 0 (Z0 > 0) at time points t = 0, 1, … , T. Let (Xt) be a gamma process with parameters α‎ and Δ‎, and consider (as in Example 6.5.5) the null hypothesis H0(c, α‎,Δ‎) where B = 10, c∗ = α‎ = 1,Δ‎ = 2, p0 = v = 0.1,m = 1, d1 = 1, and λ‎(10) = (2π‎/ log 10)2 (recall that log is the natural logarithm).

  1. 1. Show that in this special case we can choose Σ‎ = (log 10)2/24.

  2. 2. How large has the time horizon T to be? (Answer: T ≥ 2129 (instead of T ≥ 2582 as in Example 6.5.5!).)

Exercise 20.6.27. Prove the following elementary result (Lemma 6.6.7): Leta1, a2, · · · be real numbers such that 0 ≤ an < 1 (n ≥ 1) and n=1 a n <. Then

n=1 a n t  0(t ).

Exercise 20.6.28. Prove the claim in Example 6.1.28.

Exercise 20.6.29. Prove the iteration property of conditional expectations (see Example 6.1.29).

Exercise 20.6.30. Prove Lemma 6.2.1.

20.7 Benford’s Law as a Bridge Between Statistics and Accounting

An auditor decides to run a Benford’s Law test on a data set that consists of 1000 legitimate expense records from a business, plus a number of fraudulent transactions that an employee is making to a front for a business set up in a relative’s name. Because the employees of the business have to obtain special approval for expenditures over $10,000, the fraudulent transactions are all for amounts between $9000 and $9999. For the 1000 legitimate expenditures, we have this data: (p.394)

First Digit

Observed

1

314

2

178

3

111

4

92

5

88

6

59

7

56

8

56

9

46

Exercise 20.7.1. Using the Benford Law test at http://web.williams.edu/Mathematics/sjmiller/public_html/benford/chapter01/MillerNigriniExcelBenfordTester_Ver401.xlsx (or any other suitable software), verify that the data conforms reasonably well to Benford’s Law.

Exercise 20.7.2. Use trial and error (or some more clever approach) to determine how many fraudulent transactions with first digit 9 would need to be added to the 1000 legitimate observations above in order for the hypothesis that the data follows Benford’s Law to be rejected at a five percent significance level. Does this seem plausible?

Exercise 20.7.3. What is the role of sample size in the sensitivity of Benford’s Law? Suppose there are 10,000 legitimate observations instead of 1000, but the ratios for legitimate observations remains the same, i.e., the number of observations for each digit is multiplied by 10. Try the problem again. What changes?

Exercise 20.7.4. In which of the following situations is an auditor most likely to use Benford’s Law?

  • An analysis of a fast food franchise’s inventory of hamburgers.

  • An audit of a Fortune 500 company’s monthly total revenue over the fiscal year.

  • An analysis of a multibillion dollar technology company’s significant assets.

Exercise 20.7.5. Give an additional example of a way that including Benford’s Law in an introductory-level statistics class will meet the four goals of the GAISE report of 2005.

Exercise 20.7.6. Determine whether the following situations are Type I errors, Type II errors, or neither.

  • An auditor uses Benford’s Law to analyze the values of canceled checks by a business in the past fiscal year. The auditor finds that there are significant spikes in the data set, with 23 and 37 appearing as the first two digits more often than expected. After further investigation, it was found that there were valid non-fraudulent explanations for the variations in the first digits.

  • (p.395) An auditor finds that a company’s reported revenue does not follow Benford’s Law. Further investigation is taken, and it is found that a manager has been rounding up her weekly sales to the nearest thousand to earn an incentive based on a weekly sales benchmark. The manager claims that the inflated sales were an accounting error.

  • An owner of a business has falsely claimed to give his employees bonuses on each paycheck based on their monthly sales in order to lower his income taxes. An auditor examines the data, but is unable to confidently claim that the data does not follow Benford’s Law. Rather than waste funds on a costly investigation, the auditor chooses not to investigate the owner.

Exercise 20.7.7. What are the negative effects of a Type I error in an audit? A Type II error? In what situations might one be more dangerous than the other?

Exercise 20.7.8. What are some of the reasons listed in the chapter that might explain why a data set should not be expected to follow Benford’s Law?

Exercise 20.7.9. Give an example of a reason other than fraud that explains why a data set that is expected to conform to Benford’s Law does not.

20.8 Detecting Fraud and Errors Using Benford’S Law

Exercise 20.8.1. Do the following data sets meet the requirements described by Nigrini in order to be expected to follow Benford’s Law? Explain why or why not.

  • The 4-digit PIN numbers chosen by clients of a local bank.

  • The annual salaries of graduates from a public university.

  • Numeric student ID numbers assigned by a school.

  • The distances in miles between Washington, DC and the 500 most populated cities in the United States (excluding Washington, DC).

  • Results to a survey of 1000 students asked to provide a number in between 1 and 1,000,000.

  • The number of tickets bought for all events held in a particular stadium over the past five years.

Exercise 20.8.2. Take a company which has been at the heart of a scandal (for example, Enron) and investigate some of its publicly available data.

Exercise 20.8.3. An audit of a small company reveals a large number of transactions starting with a 5. Come up with some explanations other than fraud. Hint: There are two cases: it is the same amount to the same source each time, and it isn’t.

(p.396) 20.9 Can Vote Counts’ Digits and Benford’s Law Diagnose Elections?

Exercise 20.9.1. If X satisfies Benford’s Law, then the mean of its second digit is 4.187. What is the mean of the kth digit?

Exercise 20.9.2. If X satisfies Benford’s Law, multiply by an appropriate power of 10 so that it has k integer digits. What is the probability the last digit is d? What is the probability the last two digits are equal? What is the probability the last two digits differ by 1?

Exercise 20.9.3. Find some recent voting data (say city or precinct totals) and investigate the distribution of the first and second digits.

20.10 Complementing Benford’S Law For Small N: A Local Bootstrap

Exercise 20.10.1. Do you agree with the assessment that Nigrini’s conditions for applying Benford’s Law are mostly satisfied? Why or why not?

Exercise 20.10.2. Why does having a large σ‎(log10 xi) and a large σ‎(log10 wi,j) ensure that the vi,j first-digit distribution approaches Benford’s Law?

Exercise 20.10.3. What does it mean for bootstrap methods to be considered “conservative”? Identify some of the ways in which bootstrap methods are conservative.

Exercise 20.10.4. There are many conservative statistics. Look up the Bonferroni adjustment for multiple comparisons, as well as alternatives to that.

Exercise 20.10.5. How would a local bootstrap realization change if the value of Δ‎ were changed?

Exercise 20.10.6. Confirm that if cbK7 > 99.924%, then ceK7 > 99.99960%.

20.11 Measuring the Quality of European Statistics

Exercise 20.11.1. In which of the following two scenarios would χ‎2 be larger?

  • The first-digit frequencies are mostly identical to the expected Benford distribution, but the digit 1 appears 31.1% of the time and the digit 2 appears 16.6% of the time (compared with the expected values of approximately 30.1% and 17.6%, respectively).

  • The first-digit frequencies are mostly identical to the expected Benford distribution, but the digit 8 appears 6.12% of the time and the digit 2 appears 3.58% of the time (compared with the expected values of approximately 5.12% and 4.58%, respectively).

(p.397) Exercise 20.11.2. What is μ‎b, the value of the mean of the Benford distribution of first digits base b?

Exercise 20.11.3. What is the value of a if μ‎e = 3.5?

Exercise 20.11.4. Using Figure 11.1, confirm the values of χ‎2, χ‎2/n, and d for the distribution of first digits for Greek social statistics in the year 2004.

Exercise 20.11.5. Using Figure 11.1 and the formula for distance measure a used by Judge and Schechter, calculate the value of the mean of the data set (μ‎e) in the year 2004. Confirm this value by using the formula μ e = Σ i=1 9 nProb( D 1 =i) n .

The final problem uses data on two fictitious countries, which is available online http://web.williams.edu/Mathematics/sjmiller/public_html/benford/chapter11/ (some of the additional readings on that web page may be useful as well).

Exercise 20.11.6. Calculate the values χ‎2, χ‎2/n, d, and a and compare the results for both countries. Which one of these two countries should be examined closer? Are the outcomes consistent?

20.12 Benford’s Law and Fraud in Economic Research

Exercise 20.12.1. Use (12.1) to find f(6) and F(6) for Benford’s Law.

Exercise 20.12.2. If X is a Benford variable defined on [1, 10), then what is the probability that the second digit is 5 given that the first digit is also 5?

Exercise 20.12.3. Use (12.4) to confirmthat when using Benford’s Law for Rounded Figures, Prob(D1 = 8) = 0.054.

Exercise 20.12.4. If X is a Benford variable defined on [1, 10), given that the first digit is 8, what is the probability that the second digit is 0 when rounding to two significant digits? What is the probability that the second digit is 2?

Exercise 20.12.5. Using Benford’s Law for Rounded Figures as the frequencies of first digits for a data set of 300 observed values, calculate Q1, Q2, M1, and M2 using (12.6) and (12.7).

Exercise 20.12.6. Should the Q1 test or theM1 test be used for attempting to detect variations in Benford’s Law?

  • What if the data set in question has a mean of 3.44?

  • Which test should be used for detecting variations in the Generalized Benford Law?

(p.398) Exercise 20.12.7. The Federal Tax Office (FTO) knows that Ω‎ =10% of tax declarations of small and medium enterprises are falsified. The FTO checks the first digits using Benford’s Law. Random samples of tax declarations are drawn and the null hypothesis (Ho) “Conformity to Benford’s Law” is tested at the α‎ = 5% level of significance.

  • Using (12.9), what rejection rate of Ho(θ‎) would you expect if the probability of a Type II error β‎ lies in the interval [0.05, 0.75]?

  • The FTO obtained the rejection rate θ‎ = 0.12. Use (12.9) to calculate the probability β‎ of a Type II error.

  • The FTO arranges for an audit at the taxable enterprise if the Benford test rejects Ho for a certain tax declaration at the α‎ = 5% level. What is the probability that such an audit will be provoked erroneously? And what is the probability to forbear an audit erroneously?

Exercise 20.12.8. A sample of scientific articles is taken, and 17% are found to have regression coefficients with a doubtful distribution of first digits. Use (12.10) to calculate ˆΩ‎.

20.13 Testing for Strategic Manipulation of Economic and Financial Data

Exercise 20.13.1. What are some of the potential reasons given in Section 13.1 for why data sets that are expected to follow Benford’s Law fail to do so?

Exercise 20.13.2. Did Benford’s Law prove financial misreporting during the financial crisis? Justify your assertion.

Exercise 20.13.3. What are some of the potential motives that banks have for manipulating VAR data?

20.14 Psychology and Benford’s Law

Exercise 20.14.1. Using (11.1) in Section 11.3, find χ‎2 for the elaborated and unelaborated data from Scott, Barnard, and May’s study found in Table 14.1.

Exercise 20.14.2. What distribution of leading digits would you expect if people were asked to randomly give an integer from 1 to N? How does your answer depend on N? Try an experiment with some of your friends and family.

(p.399) 20.15 Managing Risk in Numbers Games: Benford’s Law and the Small-Number phenomenon

Exercise 20.15.1. What are the risks associated with a high liability limit in a fixed-odds lottery game? What if the limit is too small?

Exercise 20.15.2. From the data obtained in Table 15.1, determine the probability that a given number on a ticket for the UK powerball game is a single digit.

Exercise 20.15.3. Figure 15.1 shows the proportion of tickets in a Pennsylvania Pick-3 game with a given first digit. Explain why there are several outliers larger than the mean proportion and no outliers smaller than the mean proportion.

Exercise 20.15.4. What is the probability that a Type I player chooses the number 345 in a Pick-3 game?

Exercise 20.15.5. Let Alice be a Type II player in a Pick-3 game who bets on a number with three significant digits 80% of the time, a number with two significant digits 15% of the time, and a number with one significant digit 5% of the time. What is the probability that Alice bets on the number 345? The number 45? The number 5?

Exercise 20.15.6. In the Pennsylvania Pick-3 game, the least square model indicates that 60.42% of the players are Type I players and 39.58% of the players are Type II players. Based on this model, use (15.4) to calculate the expected proportion of the betting volume on a three-digit number with first significant digit 4.

Exercise 20.15.7. Let Bob be a Type II player in a Pick-3 game who bets on a number with three significant digits 80% of the time, but also has a tendency to exhibit switching behavior; that is, he will switch later digits withprobability 0.9105, and switch the digit to 0 with probability 0.1054. What is the probability that Bob bets on the number 345?

Exercise 20.15.8. Use (15.5) to calculate the probability that Bob chooses a three-digit number in between 520 and 529 inclusive.

Exercise 20.15.9. Calculate the variance using the equation in Section 15.4.1 under the scenario that all players randomly select a three-digit number.

20.16 Benford’s law in the Natural Sciences

Exercise 20.16.1. Demonstrate that (16.3) holds for α‎ = 2.

Exercise 20.16.2. Rewrite the log-normal distribution density function (16.5) as the log-normal density function (16.6).

Exercise 20.16.3. Show that as σ‎ grows larger, the log-normal density function approaches the power law p(x) = Cσ‎x−1, where Cσ‎ is a constant depending on σ‎.

(p.400) Exercise 20.16.4. Provide examples not mentioned in the chapter of scientific data sets that are not effectively scale invariant.

Exercise 20.16.5. Explain the intuition behind why the following distributions are approximately Benford:

  • The Boltzman–Gibbs distribution (16.8).

  • The Fermi–Dirac distribution (16.9).

  • The Bose–Einstein distribution (16.10).

Exercise 20.16.6. Obtain a physics textbook (or a CRC handbook, or… ) and find a list of physical constants. Perform a chi-square test to determine whether the list of constants follows Benford’s Law as expected.

Exercise 20.16.7. Sandon found agreement between Benford’s Law and population and surface area data for the countries of the world. Find a source that provides the population density of each country. Then determine if population density follows Benford’s Law. This can be done using a chi-square test. In general, should the ratio of two Benford random variables be Benford?

20.17 Generalizing Benford’s Law: A Reexamination of Falsified Clinical Data

Exercise 20.17.1. Use (17.1) to calculate the average frequency of first digits in Stigler’s distribution of first significant digits. Check to see that the distribution matches the values displayed in Table 17.1.

Exercise 20.17.2. Verify (17.3), (17.5), and (17.6). Then verify that the sum of the three subsets matches (17.7).

Exercise 20.17.3. Calculate the mean of the Stigler FSD distribution and Benford FSD distribution to confirm that they are equivalent to 3.55 and 3.44, respectively.

Exercise 20.17.4. For the Estimated Maximum Entropy FSD distribution for data with an FSD mean of 3.44 shown in Table 17.3, find H (p) and ensure that the criteria from (17.13) and (17.14) are reached.

  • If the Estimated Maximum Entropy FSD distribution is accurate, then the listed probabilities will maximize H (p). First, determine whether replacing p ^ 1 with0.231and p ^ 2 with 0.2 still allows (17.13) and (17.14) to hold. Now find H(p). Is H(p) larger or smaller than before?

Exercise 20.17.5. If the FSD mean is 5, what will be the estimated maximum entropy FSD distribution? What is Var(d) according to (17.18)?

Exercise 20.17.6. Examining the Poehlman data in Table 17.4, calculate the difference for each digit FSD distribution given by Benford’s Law.

(p.401) Exercise 20.17.7. The estimated empirical likelihood distributions given an FSD mean will maximize i=1 9 p i . . To test this, ensure that the product of the pi’s from Table 17.5 are greater than the empirical data found in Table 17.4.

Exercise 20.17.8. A researcher is trying to decide whether a data set follows Benford’s Law or Stigler’s Law. What values of the mean of the leading digit suggest Benford over Stigler? What values suggest Stigler over Benford?

20.18 Partial Volume Modeling of Medical Imaging Systems Using the Benford Distribution

Exercise 20.18.1. What is the PV effect? What implications does the PV effect have for medical imaging?

Exercise 20.18.2. Prove Corollary 18.3.4.

Exercise 20.18.3. What advantages are there to describing the PV effect using matrices as in (18.11)?

Exercise 20.18.4. What are the differences between a Rician noise model described by (18.12) and a Gaussian noise model described in (18.13)?

Exercise 20.18.5. Use (18.22) to calculate p(α‎) for α‎ = 0.50, where α‎ has two digits of precision.

Exercise 20.18.6. How is the contrast to noise ratio (CNR) affected if both the distance between the signal levels of two components and the standard deviation of each class is doubled?

20.19 Application of Benford’s Law to Images

Exercise 20.19.1. In (19.9) one of the factors is Γ( j2πn+log10 clog10 ), where j= 1 . . Estimate how rapidly this tends to zero as |n| → ∞as a function of c (if you wish, choose some values of c to get a feel of the behavior).

Exercise 20.19.2. In (19.19) we find that |an(c, σ‎)| ≤ |an(c+)| for all n; investigate how close these can be for various choices of c and σ‎.

Exercise 20.19.3. In Example 19.5.3 we found four zero-mean Gaussians with shaping parameter c = 1 with four different standard deviations and a1 = 0. Can you find six zero-mean Gaussians with shaping parameter c = 1 and six different standard deviations with a1 = 0? What about eight? More generally, can you find 2m such Gaussians for m a positive integer?

Notes:

(1) The random variable X is normally distributed with mean μ‎ and variance σ‎2 if its probability density function is f(x;μ,σ)=exp( (xμ) 2 /(2 σ 2 ) )/ 2π σ 2 .

(2) E. Bombieri and A. van der Poorten, Continued fractions of algebraic numbers. Pages 137–152 in Computational Algebra and Number Theory (Sydney, 1992), Mathematical Applications, Vol. 325, Kluwer Academic, Dordrecht, 1995.

(3) A. Karlsson, Applications of heat kernels on Abelian groups: ζ‎(2n), quadratic reciprocity, Bessel integral, preprint.

(4) J. Borwein and P. Borwein, Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, John Wiley and Sons, New York, 1987.

(5) P. Schumer, Mathematical Journeys, Wiley-Interscience, John Wiley & Sons, New York, 2004.

(6) G. Folland, Real Analysis: Modern Techniques and Their Applications, 2nd edition, Pure and Applied Mathematics, Wiley-Interscience, New York, 1999.