text:
# Why is a small angle considered a vector?

I have been told by my teacher that the angle of rotation, namely theta cannot be considered as a vector, which is self explanatory as it does not follow the laws of vector algebra.

But then he said that a very very small angle (limit) can be considered as a vector because it has negligible effect on the vector mathematics, namely that vector a + vector b = vector b + vector a.

He also demonstrated the fact by rotating a book, and showed that theta is not a vector, but since a very small change in the angle will not have an effect, the small angle is considered an angle.

Hence = d"theta"/dx = $$\omega$$ (angular vecocity, which we know is a vector)

I do not understand how an angle, however small can be considered as a vector. Because no matter how much small you rotate something, that small change will effect the result even though it is tiny.

Does he mean it is not a vector because it is a pseudo-vector?

vanhees71
The rotation of a vector $\vec{x}$ around an axis given by the unit vector $\vec{n}$ and angle $\varphi$ is given by
$$\vec{x}'=(\vec{n} \cdot \vec{x}) \vec{n}+(\vec{n} \times \vec{x}) \times \vec{n} \cos \varphi+\vec{n} \times \vec{x} \sin \varphi.$$

format: plain


text:
Hackerrank - Equalize the Array Solution
1 min read

# Hackerrank - Equalize the Array Solution

Karl has an array of integers. He wants to reduce the array until all remaining elements are equal. Determine the minimum number of elements to delete to reach his goal.

For example, if his array is , we see that he can delete the  elements  and  leaving . He could also delete both twos and either the  or the , but that would take  deletions. The minimum number of deletions is .

Function Description

Complete the equalizeArray function in the editor below. It must return an integer that denotes the minimum number of deletions required.

equalizeArray has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains an integer , the number of elements in .
The next line contains  space-separated integers .

Constraints

Output Format

Print a single integer that denotes the minimum number of elements Karl must delete for all elements in the array to be equal.

Sample Input

5
3 3 2 1 3

Sample Output

2

Explanation

Array . If we delete  and , all of the elements in the resulting array, , will be equal. Deleting these  elements is minimal. Our only other options would be to delete  elements to get an array of either  or .

### Solution in Python

from collections import Counter
def equalizeArray(arr):
return len(arr) - max(Counter(arr).values())
input()
arr = list(map(int,input().split()))
print(equalizeArray(arr))

# Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×


text:
# Basic OOP & Solution Design

I had an exercise as below for an interview. I used two design patterns: factory and decorator. I put my code at the end of it.

How could I improve the solution?

## Basic OOD & Solution Design Requirements

Develop a simple Visual Studio CONSOLE Application which simulates a vector-based drawing package.
Your application should support the following 5 drawing primitives (we'll call them widgets):

1) rectangle 2) square 3) ellipse 4) circle 5) textbox

The application should allow a user to Add a new widget to the drawing, stating the location and size/shape of the widget.
The location can be a standard x/y coordinate on an imaginary page. The size/shape depends on the widget, as follows:

• rectangle – width and height
• square – width
• ellipse –horizontal and vertical diameter
• circle – diameter
• textbox – bounding rectangle (i.e., the rectangle which surrounds the textbox; the text will be centred within this rectangle).

NOTE: - there is no need to worry about rotation. - integer units are fine for all dimensions. - for the textbox you only need to configure the text to display (which will be rendered horizontally within the bounding rectangle). Don’t worry about font face /size / alignment, etc. - as per our coding standards, please use a separate .cs file for each class.

Your console application should be able to 'print out' the current drawing by printing the key details of each widget (type, location, size/shape) to the console.
You don't need to actually render the widgets in any manner - we're just simulating a drawing package at this stage.

Your application can use the Console Application Main() method to test the drawing simulator by adding a hard-coded set of widgets to the drawing.

** Important Note: You DO NOT need to concern yourself with handling any input from the user. Our widgets will be hard-coded within the Main() method.

Time allowed: 2 hours.

My solution follows:

public interface IDraw
{
void Print();
}

class Shape
{
private int X { get; set; }
private int Y { get; set; }

public Shape(int x, int y)
{
this.X = x;
this.Y = y;
}

public string GetLocation()
{
return "(" + this.X + "," + this.Y + ")";
}
}

class Square : Shape, IDraw
{
public Square(int x, int y) : base(x, y)
{
}

public int size { get; set; }

public void Print()
{
Console.WriteLine("{0} {1}  size={2}", typeof(Square).Name, base.GetLocation(), this.size);
}
}

class Rectangle : Shape, IDraw
{

public int Width { get; set; }

public int Height { get; set; }

public Rectangle(int x, int y) : base(x, y)
{
}

class Textbox : Rectangle, IDraw
{
public Textbox(int x, int y)
: base(x, y)
{ }

public string Text { get; set; }

public new void Print()
{
Console.WriteLine("{0} {1} Width={2} Height={3} Text={4}", typeof(Textbox).Name, base.GetLocation(), this.Width, this.Height, "\"" + this.Text + "\"");
}
}
public void Print()
{
Console.WriteLine("{0} {1} Width={2} Height={3} ", typeof(Rectangle).Name, base.GetLocation(), this.Width, this.Height);
}
}

class Ellipse : Shape, IDraw
{

public Ellipse(int x, int y) : base(x, y)
{
}

public int HorizontalDiameter { get; set; }

public int VerticalDiameter { get; set; }

public void Print()
{
Console.WriteLine("{0} {1} diameterH={2} diameterY={3}", typeof(Ellipse).Name, base.GetLocation(), this.HorizontalDiameter, this.VerticalDiameter);
}
}

class Circle : Shape, IDraw
{

public Circle(int x, int y) : base(x, y)
{
}

public int size { get; set; }

public void Print()
{
Console.WriteLine("{0} {1} size={2}", typeof(Circle).Name, base.GetLocation(), this.size);
}
}

class Program
{

static void Main(string[] args)
{

//Hard-coded set of widgets
var widgets = new List<IDraw>()
{
new Rectangle(10, 10) { Width = 30, Height = 40 },
new Square(15, 30) { size = 35 },
new Ellipse(100, 150) { HorizontalDiameter = 300, VerticalDiameter = 200 },
new Circle(1, 1) { size = 300 },
new Textbox(5, 5) { Width = 200, Height = 100, Text = "Sample text!" }
};

foreach (var widget in widgets)
{
try
{
widget.Print();
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}

}

}
}

## migrated from stackoverflow.comOct 15 '12 at 15:07

This question came from our site for professional and enthusiast programmers.

• This isn't really on topic for SO. Programmers...maybe. (If you re-work the actual question you're asking.) – Servy Oct 4 '12 at 14:57
• We can't tell you why someone else decided against you. Could be any number of reasons. Call them and ask for feedback - you might learn something. – Oded Oct 4 '12 at 14:58
• @Servy - Not the way it is, not if the question is about why this is supposedly incorrect. – Oded Oct 4 '12 at 14:58
• @Oded Yeah, that's why I said "maybe". It's more that, this question can't really be fixed up enough to stay on SO; it might be able to be re-phrased into something that's appropriate for programmers. It's also why I voted to close as NARQ rather than off topic. – Servy Oct 4 '12 at 15:00
• Did you not implement "Textbox"? – NotMe Oct 4 '12 at 15:12

Off the bat I see a couple of things with regards to MS published coding standards, although I'm not sure what their standards are.

I'm not sure why the X/Y locations are private. Seems to me that you'd want those properties exposed as public members with regular fields backing them and default values set. Exa:

private int _x = 0;
public int X {
get { return _x; }
set { _x = value; }
}

As it stands now, the only way to get the location is through the GetLocation method which returns a string already formatted for display... not exactly what you want as that couples display to implementation which is a no-no.

Next public properties should always follow proper capitalization. You have:

public int size { get; set; }

which should be:

public int Size { get; set; }

Although, again, I'd set a default value or ensure some type of constraints on it.

Next, instead of having a generic try .. catch. I'd simply test if the object implemented the IDraw interface and, if so, call it's method. The try .. catch, especially with a generic catch, is lazy and for those whom performance is critical not a good thing.

Finally, I'm not sure that I would implement the print formatting within the classes themselves anyway. Again, that's coupling presentation with logic. Perhaps it would have been better to have another class whose job it is to emit the objects.

Finally/Finally, I would think 2 hours is probably 4 times longer than necessary to whip this out, even under pressure. Then again, I type fast.

All in all, if I was judging your entry against the requirements I'd estimate that you were a junior developer that needs some training. Yes, you met the requirements however the code itself would need additional work before going into a production type environment. If I was looking for a senior guy I wouldn't bother bringing you in for more questions.

Hope that helps. This answer is not meant to be bashing in any way but rather just a real world breakdown of what one person that routinely hires developers (not for them) sees wrong. So I hope it's taken in that vain.

Just my 0.02. Apart from the above points, especially since you presented it as a simple OOD exercise, I would have implemented a "Drawing" class with Print and Add methods instead of using a simple List.

Furthermore, your use of the new modifier in the Print method of Rectangle really annoys me, and would have made me look for someone else.

I think that I would have defined Shape as implementing IDraw, too, with a virtual version of Print printing just the position of the Shape (or even an abstract version of the method, if you prefer). Then you can override the method as you want in all your subclasses.

In the majority of cases having to use the new modifiers makes me look for bad design decisions.

• For the record, I did vote to close AND answered the question (in a wiki format). I'm not sure this question belongs here but at the same time I think helping people understand how to grow is a good thing. – NotMe Oct 4 '12 at 15:32
• Thank you very much. I think it was a graet review of codes. You are right about creating a new class and having those methods there. It was a main thing that I missied. Not sure why this quetion has been blocked as it is a good practice for reviewing and coding. – patricgh Oct 5 '12 at 12:04
• @patricgh: I changed your question slightly to be more inline with a regular code review type instead of asking the community to guess what the hiring team thought. – NotMe Oct 5 '12 at 14:01
• Thank you very much. I think, now, it makes mush sense than before. Hope it can help other coders. – patricgh Oct 5 '12 at 15:39
• "Typically in c# private variables are prefixed with an underscore." Not in current Microsoft standards, no. Camel-cased with no additional decoration is preferred layout for the name. – Jesse C. Slicer Oct 15 '12 at 16:11


text:
# zbMATH — the first resource for mathematics

Stochastic evolution equations with Wick-polynomial nonlinearities. (English) Zbl 1406.60096
Summary: We study nonlinear parabolic stochastic partial differential equations with Wick-power and Wick-polynomial type nonlinearities set in the framework of white noise analysis. These equations include the stochastic Fujita equation, the stochastic Fisher-KPP equation and the stochastic FitzHugh-Nagumo equation among many others. By implementing the theory of $$C_0$$-semigroups and evolution systems into the chaos expansion theory in infinite dimensional spaces, we prove existence and uniqueness of solutions for this class of SPDEs. In particular, we also treat the linear nonautonomous case and provide several applications featured as stochastic reaction-diffusion equations that arise in biology, medicine and physics.

##### MSC:
 60H15 Stochastic partial differential equations (aspects of stochastic analysis) 60H40 White noise theory 60G20 Generalized stochastic processes 37L55 Infinite-dimensional random dynamical systems; stochastic equations 47J35 Nonlinear evolution equations 11B83 Special sequences and polynomials
Full Text:
##### References:
 [1] Albeverio, S., Di Persio, L. S.: Some stochastic dynamical models in neurobiology: Recent developments. Europena Communications in Mathematical and Theoretical Biology14, (2011), 44–53. [2] Aronson, D., Weinberger, H.: Nonlinear diffusion in population genetics, combustion and nerve propagation. In J. A. Goldstein, editor, Partial Differential Equations and Related Topics, number 466 in Lecture Notes in Mathematics. Springer–Verlag, New York, 1975. · Zbl 0325.35050 [3] Barbu, V., Cordoni, F., Di Persio, L.S.: Optimal control of stochastic FitzHugh–Nagumo equation. International Journal of Control89(4), (2016), 746–756. · Zbl 1338.93398 [4] Fisher, R.A.: The wave of advance of advantageous genes. Ann. Eug.7, (1937), 353–369. · JFM 63.1111.04 [5] FitzHugh, R.: Impulses and physiological states in theoretical models of nerve membrane. Biophysical Journal1, (1961), 445–466. [6] Fujita, H., Watanabe, S.: On the uniqueness and non-uniqueness of solutions of initial value problems for some quasi-linear parabolic equations. Comm. Pure. Appl. Math21, (1968), 631–652. · Zbl 0157.17603 [7] Fujita, H., Chen, Y. G.: On the set of blow-up points and asymptotic behaviours of blow-up solutions to a semilinear parabolic equation. Analyse mathématique et applications, 181–201, Gauthier–Villars, Montrouge, 1988. [8] Hida, T., Kuo, H.-H., Pothoff, J., Streit, L.: White Noise. An Infinite-dimensional Calculus. Kluwer Academic Publishers Group, Dordrecht, 1993. [9] Holden, H., Øksendal, B., Ubøe, J., Zhang, T.: Stochastic Partial Differential Equations. A Modeling, White Noise Functional Approach. Second Edition. Springer, New York, 2010. · Zbl 1198.60005 [10] Huang, Z., Liu, Z.: Stochastic travelling wave solution to stochastic generalized KPP equation. Nonlinear Differ. Equ. Appl.22, (2015), 143–173. · Zbl 1322.60114 [11] Kaligotla, S.; Lototsky, S. V.: Wick product in the stochastic Burgers equation: a curse or a cure? Asymptot. Anal.75(3-4), (2011), 145–168. · Zbl 1251.35198 [12] Kato, T.: Linear evolution equations of “hyperbolic” type. II. J. Math. Soc. Japan25, (1973), 648–666. · Zbl 0262.34048 [13] Kolmogorov, A., Petrovskii, I., Piskunov, N.: Study of the diffusion equation with increase in the amount of substance and its application to a biological problem. Bull. State Univ. Mos.1, (1937), 1–25. [14] Levajković, T., Pilipović, S., Seleši, D., Žigić, M.: Stochastic evolution equations with multiplicative noise. Electron. J. Probab.20(19), (2015), 1–23. · Zbl 1321.60137 [15] Meneses, R., Quaas, A.: Fujita type exponent for fully nonlinear parabolic equations and existence results, Journal of Mathematical Analysis and Applications376(2), (2011), 514–527. · Zbl 1218.35027 [16] Mikulevicius, R., Rozovskii, B.: On unbiased stochastic Navier-Stokes equations. Probab. Theory Related Fields154, (2012), 787–834. · Zbl 1277.60109 [17] Nagumo, J., Arimoto, S., Yoshizawa, S.: An active pulse transmission line simulating nerve axon. Proceedings of the Institute of Radio Engineers50(10), (1962), 2061–2070. [18] Neidhardt, H., Zagrebnov, V. A.: Linear non-autonomous Cauchy problems and evaluation semigroups. Advan. Diff. Equat.14, (2009), 289–340. · Zbl 1180.35371 [19] Øksendal, B., Våge, G., Zhao, H. Z.: Asymptotic properties of the solutions to stochastic KPP equations. Proc. Roy. Soc. Edinburgh Sect. A130(6), (2000), 1363–1381. · Zbl 0978.60070 [20] Pazy, A.: Semigroups of Linear Operators and Applications to Partial Differential Equations. Applied Mathematical Sciences 44, Springer–Verlag, New York, 1983. · Zbl 0516.47023 [21] Pilipović, S., Seleši, D.: Expansion theorems for generalized random processes, Wick products and applications to stochastic differential equations. Infin. Dimens. Anal. Quantum Probab. Relat. Top.10(1), (2007), 79–110. [22] Pilipović, S., Seleši, D.: On the generalized stochastic Dirichlet problem - Part I: The stochastic weak maximum principle. Potential Anal.32, (2010), 363–387. [23] Stanley, R.P.: Catalan Numbers. Cambridge University Press, New York, 2015. · Zbl 1317.05010 [24] Yosida, K.: Time dependent evolution equations in a locally convex space. Math. Ann.162, (1965/1966), 83–86. · Zbl 0138.08301 [25] Zeidler, E.: Nonlinear functional analysis and its applications. I. Fixed-point theorems. Springer-Verlag, New York, 1986. · Zbl 0583.47050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# Lead needed to coat a cable

3 posts / 0 new
MichMaganda
Lead needed to coat a cable

How much lead is needed to coat a cable, 55mm in diameter, if the cable is 5km long and the lead coat is 4mm thick. 11.4x10^3 kg/m^3 for the density of the lead.

Jhun Vert

Radius of uncoated cable = 55/2 = 27.5 mm = 0.0275 m
Radius of coated cable = 55/2 + 4 = 31.5 mm = 0.0315 m
Length of cable = 5000 m

$V = \pi (0.0315^2 - 0.0275^2)(5000) = 1.18\pi ~ \text{ m}^3$

$m = \rho V = (11.4 \times 10^3)(1.18\pi) = 42,260.70 ~ \text{ kg}$

MichMaganda

Thank you, sir!! :)

• Mathematics inside the configured delimiters is rendered by MathJax. The default math delimiters are $$...$$ and $...$ for displayed mathematics, and $...$ and $...$ for in-line mathematics.


text:
Register for: AustMS2018

# Abstracts for AustMS2018

17 abstracts submitted for session.

Authors Title Session Timetabled Abstract
Dr Anna Romanov An orbit model for the spectra of nilpotent Gelfand pairs Rep Th 2018-12-06 10:00:00 Let N be a connected and simply ...
Dr Asilata Bapat Recollement of perverse sheaves on real hyperplane arrangements Rep Th 2018-12-07 13:30:00 A hyperplane arrangement gives a stratification on ...
Dr Masoud Kamgarpour Topology of representation stacks Rep Th 2018-12-04 14:00:00 I will talk about computing how to ...
Dr Michael Ehrig Finite dimensional representations of orthosymplectic supergroups Rep Th 2018-12-06 09:00:00 In the talk I want to review ...
Dr Thomas Gobet A Soergel-like category for complex reflection groups of rank one Rep Th 2018-12-07 14:00:00 We introduce analogues of Soergel bimodules for ...
Dr Travis Scrimshaw Crystal structures for symmetric Grothendieck polynomials Rep Th 2018-12-06 09:30:00 Kashiwara's theory of crystal bases allows one ...
Dr Valentin Buciumas Quantum polynomial functors Rep Th 2018-12-07 14:30:00 The classical polynomial functors of Friedlander and ...
Dr Yusra Naqvi A product formula for certain coefficients of Macdonald polynomials Rep Th 2018-12-06 08:30:00 Macdonald polynomials generalise several classical families of ...
Joel Gibson The Product Monomial Crystal Rep Th 2018-12-05 17:00:00 The product monomial crystal is the non-generic ...
Mr Alexander Ferdinand Kerschl Inner products on graded Specht modules Rep Th 2018-12-04 15:30:00 A cellular basis of an algebra gives ...
Mr Edmund Xian Chen Heng Braid group action on triangulated categories Rep Th 2018-12-05 15:30:00 It is known that braid groups act ...
Mr Saul D. Freedman p-groups related to exceptional Chevalley groups Rep Th 2018-12-05 16:30:00 It is well-known that given any finite ...
Mr Seamus Albion The Selberg integral and Macdonald polynomials Rep Th 2018-12-04 16:30:00 In 1944, Atle Selberg discovered a remarkable ...
Ms Iva Halacheva Puzzles for restricting Schubert classes to the symplectic Grassmannian Rep Th 2018-12-04 14:30:00 The Grassmannian Gr(k,V) of k-planes in a ...
Mx Matthew James Spong Two models of equivariant elliptic cohomology Rep Th 2018-12-05 16:00:00 In 1994, Grojnowski gave a construction of ...
Prof Anthony Henderson Complementary symmetry for Slodowy varieties Rep Th 2018-12-05 17:30:00 Let $\lambda$ and $\mu$ be two partitions ...
S.P. Glasby, Marvin Krings, Alice C. Niemeyer The $p$-Part of the Order of an Almost Simple Group of Lie Type Rep Th 2018-12-04 16:00:00 Primitive permutation groups are fundamental building blocks ...


text:
Amha Tume Lisan

Born:

place: Ethiopia

area of degree: Topological Semigroups

pre-doctoral education:

doctoral institution: Howard University (1988)

current (12/98) employment: Louisiana State University

Lisan served as an instructor at Howard for four years before joining the LSU mathematics department's graduate faculty.

Research

Dr. Lisan has published 8 papers.

8. Hindman, Neil; Lawson, Jimmie; Lisan, Amha Separating points of $\beta{N}$ by minimal flows. Canad. J. Math. 46 (1994), no. 4, 758--771.

7. Lawson, Jimmie; Lisan, Amha Flows, congruences, and factorizations. Topology Appl. 58 (1994), no. 1, 35--46.

6. Hindman, Neil; Lisan, Amha Tume Points very close to the smallest ideal of $\beta S$. Semigroup Forum 49 (1994), no. 2, 137--141.

5. Lisan, Amha Tume Multi-dimensional Ramsey theorems---an example. Combinatorica 12 (1992), no. 3, 363--365.

4. Lawson, J. D.; Lisan, Amha Transitive flows: a semigroup approach. Mathematika 38 (1991), no. 2, 348--361 (1992).

3. Lisan, Amha Tume Ultrafilters on a discrete set with two binary operations. Semigroup Forum 43 (1991), no. 1, 77--81.

2. Hindman, Neil; Lisan, Amha T. Does $N\sp *$ contain a topological and algebraic copy of $\beta {N}$? Topology Appl. 35 (1990), no. 2-3, 291--297.

1. Lisan, Amha Tume Free groups in $\beta {N}$ which miss the minimal ideal. Semigroup Forum 37 (1988), no. 2, 233--239.

The web pages
MATHEMATICIANS OF THE AFRICAN DIASPORA
are brought to you by

The Mathematics Department of
The State University of New York at Buffalo.

They are created and maintained by
Scott W. Williams
Professor of Mathematics


text:
# Intuition & Proof of rank(AB) $\le$ min{rank(A), rank(B)} (without inverses or maps) [Poole P217 3.6.59, 60]

I'm aware of analogous threads; I hope that mine is specific enough not to be esteemed one.

$\mathbf{a^i}$ is a row vector. $A, B$ are matrices. Prove: $1$. $\mathbf{a^i}B$ is a linear combination of the rows of $B$.
$2.$ Row space of $AB \subseteq$ row space of $B$. $\qquad$ $3.$ Column space of $AB \subseteq$ Column space of $A$.
$4.$ If $\mathbf{a_i}$ is a column vector, then $A\mathbf{a_i}$ is a linear combination of the columns of $A$.
$5. \operatorname{rank}(A\color{#B8860B}{B}) \color{#B8860B}{\le} \operatorname{rank}\color{#B8860B}{B} \qquad \qquad$ $6.\operatorname{rank}(AB) \leq \operatorname{rank} A$.
In general, $x \leq a \text{ & } x \le b \implies x \le \min\{a, b\}$.
So by $5 \, \& \, 6$, $\operatorname{rank}(AB) \leq \min\{\operatorname{rank}A,\operatorname{rank} B\}$.

$\bbox[2px,border:2px solid grey]{\text{ Proof of #5 :}} \;$ The rank of a matrix is the dimension of its row space. Need to show :
If $\operatorname{rowsp}(AB) \subseteq\operatorname{rowsp}(B)$, then $\operatorname{dim rowspace}(AB) \le \operatorname{dim rowspace}(B).$
Pick a basis for $\operatorname{rowsp}(AB)$. Say there are $p$ vectors in this basis.
By $\#2$, row space of $AB \subseteq$ row space of $B$, $\color{green}{\text{so all of these$p$vectors also$\in \operatorname{rowsp}(B)$}}$. Moreover, they must be linearly independent (hereafter dubbed l-ind).
${\Large{\color{red}{[}}} \;$ Since the dimension of a space $=$ the maximum number of l-ind vectors in that space, $\; {\Large{{\color{red}{]}}}}$
and $\color{green}{\text{$\operatorname{rowsp}(B)$has$\ge p$l-ind vectors}}$, thus $\operatorname{dim rowspace}(B) \; \ge \; \operatorname{dim rowspace}(AB) = p.$

$\bbox[2px,border:2px solid grey]{\text{ Proof of #6 :}} \;$ Apply $\operatorname{rank}M = \operatorname{rank}M^T$ and $\#5$: $\operatorname{rank}(AB)^T = \operatorname{rank}(B^T\color{#B8860B}{A^T}) \quad \color{#B8860B}{\le} \quad \operatorname{rank}\color{#B8860B}{A^T} = \operatorname{rank}(A)$.

$Q1.$ Please elucidate the above proof of $5$? I'm bewildered. What's the strategy?

$Q2.$ On P209, Poole defines dimension as the number of vectors in a basis.
So shouldn't the red bracket refer to a basis? If so, why doesn't the proof simply declare:
By $2$, the basis for $\operatorname{rowsp}(AB)$ can be reused as a basis for $\operatorname{rowsp}(B).$ ?

$Q3.$ How'd one previse to invert $AB$ and apply $\#5$ (the key strategem) for #6?

$Q4.$ What's the intuition behind results $5$ and $6$? I'd be grateful for pictures.

Sources: P147, 4.48, Schaum's Outline to Lin Alg, web.mit.edu/18.06/www/Spring01/Sol-S01-5.ps

-
I think $p = \operatorname{dim rowspace}(B)$ is wrong. Instead, $p \le \operatorname{dim rowspace}(B)$. –  NovaDenizen Dec 22 '13 at 14:16
@NovaDenizen Thank you! I emended my OP. Please let me know of any errors. –  Law Area 51 Proposal - Commit Dec 29 '13 at 7:55

Whenever you have two subspaces $V$ and $W$ with $V \subseteq W$, the $\text{dim}(V) \le \text{dim}(W)$. The proof is pretty easy. Construct a basis $B = (v_1, ..., v_n)$ for $V$. Now extend this to a basis of $W$ so that $B' = (v_1, ..., v_n, w_1, ..., w_k)$. Since the number of basis vectors in $B$ is less than or equal to the number of basis vectors in $B'$, we have $\text{dim}(V) \le \text{dim}(W)$, by definition of "dimension" as the number of vectors in a basis for the space.
I've glossed over details, like the fact that you can extend the basis of $V$ to a basis of $W$, but this is easy to show or find elsewhere. I suggest Axler's book, "Linear Algebra Done Right."


text:
Metrics:

# Measurement of the inclusive and fiducial tt¯ production cross-sections in the lepton+jets channel in pp collisions at s√=8 TeV with the ATLAS detector (2018)

• Authors:
• Autor USP: LEITE, MARCO AURELIO LISBOA - IF
• DOI: 10.1140/epjc/s10052-018-5904-z
• Subjects: COLISÕES DE ÍONS PESADOS RELATIVÍSTICOS; LHC
• Agências de fomento:
• Language: Inglês
• Abstract: The inclusive and fiducial tt¯ production cross-sections are measured in the lepton+jets channel using 20.2 fb−1 of proton–proton collision data at a centre-of-mass energy of 8 TeV recorded with the ATLAS detector at the LHC. Major systematic uncertainties due to the modelling of the jet energy scale and b-tagging efficiency are constrained by separating selected events into three disjoint regions. In order to reduce systematic uncertainties in the most important background, the W+\,jets process is modelled using Z + jets events in a data-driven approach. The inclusive tt¯ cross-section is measured with a precision of 5.7% to be σinc(tt¯)=248.3±0.7(stat.)±13.4(syst.)±4.7(lumi.) pb , assuming a top-quark mass of 172.5 GeV. The result is in agreement with the Standard Model prediction. The cross-section is also measured in a phase space close to that of the selected data. The fiducial cross-section is σfid(tt¯)=48.8±0.1(stat.)±2.0(syst.)±0.9(lumi.) pb with a precision of 4.5%.
• Imprenta:
• Source:
• Informações sobre o DOI: 10.1140/epjc/s10052-018-5904-z (Fonte: oaDOI API)
• Este periódico é de acesso aberto
• Este artigo é de acesso aberto
• URL de acesso aberto
• Cor do Acesso Aberto: gold
• Licença: cc-by

##### How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

AABOUD, M; DONADELLI, Marisílvia; ROSA NAVARRO, José Luis La; LEITE, Marco Aurelio Lisboa. Measurement of the inclusive and fiducial tt¯ production cross-sections in the lepton+jets channel in pp collisions at s√=8 TeV with the ATLAS detector. European Journal Physical C, Berlim, Springer, v. 78, n. 487, p. 1-31, 2018. DOI: 10.1140/epjc/s10052-018-5904-z.
• APA

Aaboud, M., Donadelli, M., Rosa Navarro, J. L. L., & Leite, M. A. L. (2018). Measurement of the inclusive and fiducial tt¯ production cross-sections in the lepton+jets channel in pp collisions at s√=8 TeV with the ATLAS detector. European Journal Physical C, 78( 487), 1-31. doi:10.1140/epjc/s10052-018-5904-z
• NLM

Aaboud M, Donadelli M, Rosa Navarro JLL, Leite MAL. Measurement of the inclusive and fiducial tt¯ production cross-sections in the lepton+jets channel in pp collisions at s√=8 TeV with the ATLAS detector. European Journal Physical C. 2018 ; 78( 487): 1-31.
• Vancouver

Aaboud M, Donadelli M, Rosa Navarro JLL, Leite MAL. Measurement of the inclusive and fiducial tt¯ production cross-sections in the lepton+jets channel in pp collisions at s√=8 TeV with the ATLAS detector. European Journal Physical C. 2018 ; 78( 487): 1-31.

P.W. Higgs, Broken symmetries and the masses of gauge bosons. Phys. Rev. Lett. 13, 508 (1964)
F. Englert, R. Brout, Broken symmetry and the mass of gauge vector mesons. Phys. Rev. Lett. 13, 321 (1964)
M. Baak et al., The global electroweak fit at NNLO and prospects for the LHC and ILC. Eur. Phys. J. C 74, 3046 (2014). arXiv:1407.3792 [hep-ph]
A. Buckley et al., Constraining top quark effective theory in the LHC Run II era. JHEP 04, 015 (2016). arXiv:1512.03360 [hep-ph]
M. Czakon, P. Fiedler, A. Mitov, The total top quark pair production cross-section at hadron colliders through $$O(\alpha _S^4)$$ O ( α S 4 ) . Phys. Rev. Lett. 110, 252004 (2013). arXiv:1303.6254 [hep-ph]
U. Langenfeld, S. Moch, P. Uwer, Measuring the running top-quark mass. Phys. Rev. D 80, 054009 (2009). arXiv:0906.5273 [hep-ph]
S.-Q. Wang, X.-G. Wu, Z.-G. Si, S.J. Brodsky, A precise determination of the top-quark pole mass. Eur. Phys. J. C 78, 237 (2018). arXiv:1703.03583 [hep-ph]
R. Franceschini, Wish-list for Run II top quark measurements (for BSM). In 3rd Large Hadron Collider Physics Conference (LHCP 2015), St. Petersburg, Russia, 31 Aug–5 Sept 2015 (2016). arXiv:1601.02684 [hep-ph]. http://inspirehep.net/record/1414954/files/arXiv:1601.02684.pdf
M. Cacciari et al., Top-pair production at hadron colliders with next-to-next-to-leading logarithmic soft-gluon resummation. Phys. Lett. B 710, 612 (2012). arXiv:1111.5869 [hep-ph]
P. Bärnreuther, M. Czakon, A. Mitov, Percent level precision physics at the Tevatron: first genuine NNLO QCD corrections to $$q\bar{q}\rightarrow t{\bar{t}}$$ q q ¯ → t t ¯ . Phys. Rev. Lett. 109, 132001 (2012). arXiv:1204.5201 [hep-ph]
M. Czakon, A. Mitov, NNLO corrections to top-pair production at hadron colliders: the all-fermionic scattering channels. JHEP 12, 054 (2012). arXiv:1207.0236 [hep-ph]
M. Czakon, A. Mitov, NNLO corrections to top pair production at hadron colliders: the quark-gluon reaction. JHEP 01, 080 (2013). arXiv:1210.6832 [hep-ph]
M. Czakon, A. Mitov, Top++: a program for the calculation of the top-pair cross-section at hadron colliders. Comput. Phys. Commun. 185, 2930 (2014). arXiv:1112.5675 [hep-ph]
M. Botje et al., The PDF4LHC working group interim recommendations (2011). arXiv:1101.0538 [hep-ph]
A.D. Martin, W.J. Stirling, R.S. Thorne, G. Watt, Parton distributions for the LHC. Eur. Phys. J. C 63, 189 (2009). arXiv:0901.0002 [hep-ph]
A.D. Martin, W.J. Stirling, R.S. Thorne, G. Watt, Uncertainties on $$\alpha _S$$ α S in global PDF analyses and implications for predicted hadronic cross sections. Eur. Phys. J. C 64, 653 (2009). arXiv:0905.3531 [hep-ph]
H.-L. Lai et al., New parton distributions for collider physics. Phys. Rev. D 82, 074024 (2010). arXiv:1007.2241 [hep-ph]
J. Gao et al., CT10 next-to-next-to-leading order global analysis of QCD. Phys. Rev. D 89, 033009 (2014). arXiv:1302.6246 [hep-ph]
R.D. Ball et al., Parton distributions with LHC data. Nucl. Phys. B 867, 244 (2013). arXiv:1207.1303 [hep-ph]
C. Muselli et al., Top quark pair production beyond NNLO. JHEP 08, 076 (2015). arXiv:1505.02006 [hep-ph]
N. Kidonakis, NNNLO soft-gluon corrections for the top-antitop pair production cross section. Phys. Rev. D 90, 014006 (2014). arXiv:1405.7046 [hep-ph]
CDF and D0 Collaborations, Combination of measurements of the top-quark pair production cross section from the Tevatron Collider. Phys. Rev. D 89, 072001 (2014). arXiv:1309.7570 [hep-ex]
ATLAS Collaboration, Measurement of the $$t\bar{t}$$ t t ¯ production cross-section using $$e\mu$$ e μ events with b-tagged jets in pp collisions at $$\sqrt{s} = 7$$ s = 7 and 8 TeV with the ATLAS detector. Eur. Phys. J. C 74, 3109 (2014). arXiv:1406.5375 [hep-ex] [Addendum: Eur. Phys. J. C 76, 642 (2016)]
ATLAS Collaboration, Measurement of the $$t\bar{t}$$ t t ¯ production cross-section using $$e\mu$$ e μ events with b-tagged jets in pp collisions at $$\sqrt{s} = 13$$ s = 13  TeV with the ATLAS detector. Phys. Lett. B 761, 136 (2016). arXiv:1606.02699 [hep-ex]
CMS Collaboration, Measurement of the $$t\bar{t}$$ t t ¯ production cross section in the $$e\mu$$ e μ channel in proton-proton collisions at $$\sqrt{s} = 7$$ s = 7 and 8 TeV. JHEP 08, 029 (2016). arXiv:1603.02303 [hep-ex]
CMS Collaboration, Measurement of the $$t\bar{t}$$ t t ¯ production cross section using events in the $$e\mu$$ e μ final state in pp collisions at $$\sqrt{s} = 13$$ s = 13  TeV. Eur. Phys. J. C 77, 172 (2017). arXiv:1611.04040 [hep-ex]
LHCb Collaboration, Measurement of forward $$t\bar{t}, W + b\bar{b}$$ t t ¯ , W + b b ¯ and $$W + c\bar{c}$$ W + c c ¯ production in pp collisions at $$\sqrt{s} = 8$$ s = 8  TeV. Phys. Lett. B 767, 110 (2017). arXiv:1610.08142 [hep-ex]
CMS Collaboration, Measurements of the $$t\bar{t}$$ t t ¯ production cross section in lepton+jets final states in pp collisions at 8 TeV and ratio of 8 to 7 TeV cross sections. Eur. Phys. J. C 77, 15 (2017). arXiv:1602.09024 [hep-ex]
ATLAS Collaboration, Measurement of the top pair production cross section in 8 TeV proton–proton collisions using kinematic information in the lepton+jets final state with ATLAS. Phys. Rev. D 91, 112013 (2015). arXiv:1504.04251 [hep-ex]
ATLAS Collaboration, The ATLAS experiment at the CERN large hadron collider. JINST 3, S08003 (2008)
ATLAS Collaboration, Performance of the ATLAS trigger system in 2010. Eur. Phys. J. C 72, 1849 (2012). arXiv:1110.1530 [hep-ex]
ATLAS Collaboration, The ATLAS simulation infrastructure. Eur. Phys. J. C 70, 823 (2010). arXiv:1005.4568 [physics.ins-det]
S. Agostinelli et al., GEANT4: a simulation toolkit. Nucl. Instrum. Methods A 506, 250 (2003)
T. Sjöstrand et al., An introduction to PYTHIA 8.2. Comput. Phys. Commun. 191, 159 (2015). arXiv:1410.3012 [hep-ph]
S. Alioli, P. Nason, C. Oleari, E. Re, A general framework for implementing NLO calculations in shower Monte Carlo programs: the POWHEG BOX. JHEP 06, 043 (2010). arXiv:1002.2581 [hep-ph]
S. Frixione, P. Nason, G. Ridolfi, A positive-weight next-to-leading-order Monte Carlo for heavy flavour hadroproduction. JHEP 09, 126 (2007). arXiv:0707.3088 [hep-ph]
T. Sjöstrand, S. Mrenna, P.Z. Skands, PYTHIA 6.4 physics and manual. JHEP 05, 026 (2006). arXiv:hep-ph/0603175
P.Z. Skands, Tuning Monte Carlo generators: the Perugia tunes. Phys. Rev. D 82, 074018 (2010). arXiv:1005.3457 [hep-ph]
G. Corcella et al., HERWIG 6: an event generator for hadron emission reactions with interfering gluons (including supersymmetric processes). JHEP 01, 010 (2001). arXiv:hep-ph/0011363
S. Frixione, B.R. Webber, Matching NLO QCD computations and parton shower simulations. JHEP 06, 029 (2002). arXiv:hep-ph/0204244
S. Frixione, P. Nason, B.R. Webber, Matching NLO QCD and parton showers in heavy flavor production. JHEP 08, 007 (2003). arXiv:hep-ph/0305252
J.M. Butterworth, J.R. Forshaw, M.H. Seymour, Multiparton interactions in photoproduction at HERA. Z. Phys. C 72, 637 (1996). arXiv:hep-ph/9601371
ATLAS Collaboration, New ATLAS event generator tunes to 2010 data. ATL-PHYS-PUB-2011-008 (2011). https://cds.cern.ch/record/1345343
ATLAS Collaboration, Comparison of Monte Carlo generator predictions to ATLAS measurements of top pair production at 7 TeV. ATL-PHYS-PUB-2015-002 (2015). https://cds.cern.ch/record/1981319
S. Alioli, P. Nason, C. Oleari, E. Re. NLO single-top production matched with shower in POWHEG: s- and t-channel contributions. JHEP 09, 111 (2009). arXiv:0907.4076 [hep-ph] [Erratum: JHEP 02, 011 (2010)]
E. Re, Single-top Wt-channel production matched with parton showers using the POWHEG method. Eur. Phys. J. C 71, 1547 (2011). arXiv:1009.2450 [hep-ph]
N. Kidonakis, Two-loop soft anomalous dimensions for single top quark associated production with a $$W^{-}$$ W - or $$H^{-}$$ H - . Phys. Rev. D 82, 054018 (2010). arXiv:1005.4451 [hep-ph]
P. Kant et al., HatHor for single top-quark production: updated predictions and uncertainty estimates for single top-quark production in hadronic collisions. Comput. Phys. Commun. 191, 74 (2015). arXiv:1406.4403 [hep-ph]
J.M. Campbell, R. Frederix, F. Maltoni, F. Tramontano, Next-to-leading-order predictions for t-channel single-top production at hadron colliders. Phys. Rev. Lett. 102, 182003 (2009). arXiv:0903.0005 [hep-ph]
M.L. Mangano et al., ALPGEN, a generator for hard multiparton processes in hadronic collisions. JHEP 07, 001 (2003). arXiv:hep-ph/0206293
J. Pumplin et al., New generation of parton distributions with uncertainties from global QCD analysis. JHEP 07, 012 (2002). arXiv:hep-ph/0201195
J. Alwall et al., Comparative study of various algorithms for the merging of parton showers and matrix elements in hadronic collisions. Eur. Phys. J. C 53, 473 (2008). arXiv:0706.2569 [hep-ph]
R. Gavin, Y. Li, F. Petriello, S. Quackenbush, FEWZ 2.0: a code for hadronic Z production at next-to-next-to-leading order. Comput. Phys. Commun. 182, 2388 (2011). arXiv:1011.3540 [hep-ph]
R. Gavin, Y. Li, F. Petriello, S. Quackenbush, W physics at the LHC with FEWZ 2.1. Comput. Phys. Commun. 184, 208 (2013). arXiv:1201.5896 [hep-ph]
T. Gleisberg et al., Event generation with SHERPA 1.1. JHEP 02, 007 (2009). arXiv:0811.4622 [hep-ph]
S. Hoeche, F. Krauss, S. Schumann, F. Siegert, QCD matrix elements and truncated showers. JHEP 05, 053 (2009). arXiv:0903.1219 [hep-ph]
J.M. Campbell, R.K. Ellis, C. Williams, Vector boson pair production at the LHC. JHEP 07, 018 (2011). arXiv:1105.0020 [hep-ph]
ATLAS Collaboration, Electron efficiency measurements with the ATLAS detector using 2012 LHC proton–proton collision data. Eur. Phys. J. C 77, 195 (2017). arXiv:1612.01456 [hep-ex]
ATLAS Collaboration, Electron and photon energy calibration with the ATLAS detector using LHC Run 1 data. Eur. Phys. J. C 74, 3071 (2014). arXiv:1407.5063 [hep-ex]
ATLAS Collaboration, Measurement of the muon reconstruction performance of the ATLAS detector using 2011 and 2012 LHC proton–proton collision data. Eur. Phys. J. C 74, 3130 (2014). arXiv:1407.3935 [hep-ex]
K. Rehermann, B. Tweedie, Efficient identification of boosted semileptonic top quarks at the LHC. JHEP 03, 059 (2011). arXiv:1007.2221 [hep-ph]
M. Cacciari, G.P. Salam, G. Soyez, The anti-kt jet clustering algorithm. JHEP 04, 063 (2008). arXiv:0802.1189 [hep-ph]
M. Cacciari, G.P. Salam, G. Soyez, FastJet user manual. Eur. Phys. J. C 72, 1896 (2012). arXiv:1111.6097 [hep-ph]
ATLAS Collaboration, Topological cell clustering in the ATLAS calorimeters and its performance in LHC Run 1. Eur. Phys. J. C 77, 490 (2017). arXiv:1603.02934 [hep-ex]
ATLAS Collaboration, Jet energy measurement and its systematic uncertainty in proton–proton collisions at $$\sqrt{s} = 7$$ s = 7  TeV with the ATLAS detector. Eur. Phys. J. C 75, 17 (2015). arXiv:1406.0076 [hep-ex]
ATLAS Collaboration, Performance of pile-up mitigation techniques for jets in pp collisions at $$\sqrt{s} = 8$$ s = 8  TeV using the ATLAS detector. Eur. Phys. J. C 76, 581 (2016). arXiv:1510.03823 [hep-ex]
ATLAS Collaboration, Performance of b-jet identification in the ATLAS experiment. JINST 11, P04008 (2016). arXiv:1512.01094 [hep-ex]
ATLAS Collaboration, Performance of algorithms that reconstruct missing transverse momentum in $$\sqrt{s} = 8$$ s = 8  TeV proton–proton collisions in the ATLAS detector. Eur. Phys. J. C 77, 241 (2017). arXiv:1609.09324 [hep-ex]
ATLAS Collaboration, Performance of the ATLAS muon trigger in pp collisions at $$\sqrt{s} = 8$$ s = 8  TeV. Eur. Phys. J. C 75, 120 (2015). arXiv:1408.3179 [hep-ex]
ATLAS Collaboration, Jet energy measurement with the ATLAS detector in proton–proton collisions at $$\sqrt{s} = 7$$ s = 7  TeV. Eur. Phys. J. C 73, 2304 (2013). arXiv:1112.6426 [hep-ex]
ATLAS Collaboration, Estimation of non-prompt and fake lepton backgrounds in final states with top quarks produced in proton–proton collisions at $$\sqrt{s} = 8$$ s = 8  TeV with the ATLAS Detector. ATLAS-CONF-2014-058 (2014). https://cds.cern.ch/record/1951336
M. Feindt, A neural Bayesian estimator for conditional probability densities (2004). arXiv:physics/0402093 [physics.data-an]
M. Feindt, U. Kerzel, The NeuroBayes neural network package. Nucl. Instrum. Methods A 559, 190 (2006)
ATLAS Collaboration, Measurement of the top quark mass in the $$t\bar{t}$$ t t ¯ lepton+jets and $$t\bar{t}$$ t t ¯ dilepton channels using $$\sqrt{s} =7$$ s = 7  TeV ATLAS data. Eur. Phys. J. C 75, 330 (2015). arXiv:1503.05427 [hep-ex]
CMS Collaboration, Measurement of the top quark mass using proton-proton data at $$\sqrt{s} = 7$$ s = 7 and 8 TeV. Phys. Rev. D 93, 072004 (2016). arXiv:1509.04044 [hep-ex]
D0 Collaboration, Precise measurement of the top quark mass from lepton+jets events at D0. Phys. Rev. Lett. 101, 182001 (2008). arXiv:0807.2141 [hep-ex]
CDF Collaboration, Precision top-quark mass measurements at CDF. Phys. Rev. Lett. 109, 152003 (2012). arXiv:1207.6758 [hep-ex]
ATLAS Collaboration, Data-driven determination of the energy scale and resolution of jets reconstructed in the ATLAS calorimeters using dijet and multijet events at $$\sqrt{s} = 8$$ s = 8  TeV. ATLAS-CONF-2015-017 (2015). https://cds.cern.ch/record/2008678
ATLAS Collaboration, Determination of the jet energy scale and resolution at ATLAS using $$\text{Z}/\gamma$$ Z / γ -jet events in data at $$\sqrt{s} = 8$$ s = 8  TeV. ATLAS-CONF-2015-057 (2015). https://cds.cern.ch/record/2059846
ATLAS Collaboration, Calibration of the performance of b-tagging for c and light-flavour jets in the 2012 ATLAS data. ATLAS-CONF-2014-046 (2014). https://cds.cern.ch/record/1741020
ATLAS Collaboration, Calibration of b-tagging using dileptonic top pair events in a combinatorial likelihood approach with the ATLAS experiment. ATLAS-CONF-2014-004 (2014). https://cds.cern.ch/record/1664335
J. Butterworth et al., PDF4LHC recommendations for LHC Run II. J. Phys. G 43, 023001 (2016). arXiv:1510.03865 [hep-ph]
ATLAS Collaboration, Luminosity determination in pp collisions at $$\sqrt{s} = 8$$ s = 8  TeV using the ATLAS detector at the LHC. Eur. Phys. J. C 76, 653 (2016). arXiv:1608.03953 [hep-ex]
E. Todesco, J. Wenninger, Large hadron collider momentum calibration and accuracy. Phys. Rev. Accel. Beams 20, 081003 (2017)
ATLAS Collaboration, Measurement of the cross-section for W boson production in association with b-jets in pp collisions at $$\sqrt{s} = 7$$ s = 7  TeV with the ATLAS detector. JHEP 06, 084 (2013). arXiv:1302.2929 [hep-ex]
ATLAS Collaboration, Measurement of the $$t\bar{t}$$ t t ¯ production cross-section using $$e\mu$$ e μ events with b-tagged jets in pp collisions at $$\sqrt{s} = 7$$ s = 7 and 8 TeV with the ATLAS detector. Eur. Phys. J. C 74, 3109 (2014). arXiv:1406.5375 [hep-ex]
ATLAS Collaboration, ATLAS computing acknowledgements. ATL-GEN-PUB-2016-002. https://cds.cern.ch/record/2202407

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020


text:
## puzzles & riddles

Posted in Books, Kids, R, Statistics with tags , , , , , , , , on January 3, 2021 by xi'an

A rather simplistic game on the Riddler of 18 December:

…two players, each of whom starts with a whole number of points. Players take turns “attacking” each other, which involves subtracting their own number of points from their opponent’s until one of the players is out of points.

Easy to code in R:

g=function(N,M)ifelse(N<M,-g(M-N,N),1)

f=function(N,M=N){
while(g(N,M)>0)M=M+1
return(M)}

which converges to the separating ratio 1.618. If decomposing the actions until one player wins, one gets a sequence of upper and lower bounds associated with the Fibonacci sequence: 1⁻, 2⁺, 3/2⁻, 5/3⁺, 8/5⁻, &tc, converging to the “golden ratio” φ.

As an aside, I also solved a relatively quick codegolf challenge, where the question was to find the sum of all possible binary values from a bitmask. Meaning that for a binary input, e.g., 101X0XX0…01X, with some entries masked by X’s, one had to find the sum of all binary numbers compatible with the input. Which can be solved succinctly by counting the number of X’s, k, and adding the visible bits $2^k$ times and replacing the invisible ones by  $2^{k-1}$. With some help, and using 2 instead of X, my R code moved from 158 bytes to 50:

function(x)2^sum(a<-x>1)*rev(x/4^a)%*%2^(seq(x)-1)

## Le Monde puzzle [#1164]

Posted in Books, Kids, R with tags , , , , , , , , , , , , , on November 16, 2020 by xi'an

The weekly puzzle from Le Monde is quite similar to older Diophantine episodes (I find myself impossible to point out):

Give the maximum integer that cannot be written as 105x+30y+14z. Same question for 105x+70y+42z+30w.

These are indeed Diophantine equations and the existence of a solution is linked with Bézout’s Lemma. Take the first equation. Since 105 and 30 have a greatest common divisor equal to 3×5=15, there exists a pair (x⁰,y⁰) such that

105 x⁰ + 30 y⁰ = 15

hence a solution to every equation of the form

105 x + 30 y = 15 a

for any relative integer a. Similarly, since 14 and 15 are co-prime,

there exists a pair (a⁰,b⁰) such that

15 a⁰ + 14 b⁰ = 1

hence a solution to every equation of the form

15 a⁰ + 14 b⁰ = c

for every relative integer c. Meaning 105x+30y+14z=c can be solved in all cases. The same result applies to the second equation. Since algorithms for Bézout’s decomposition are readily available, there is little point in writing an R code..! However, the original question must impose the coefficients to be positive, which of course kills the Bézout’s identity argument. Stack Exchange provides the answer as the linear Diophantine problem of Frobenius! While there is no universal solution for three and more base integers, Mathematica enjoys a FrobeniusNumber solver. Producing 271 and 383 as the largest non-representable integers. Also found by my R code

o=function(i,e,x){
if((a<-sum(!!i))==sum(!!e))sol=(sum(i*e)==x) else{sol=0
for(j in 0:(x/e[a+1]))sol=max(sol,o(c(i,j),e,x))}
sol}
a=(min(e)-1)*(max(e)-1)#upper bound
M=b=((l<-length(e)-1)*prod(e))^(1/l)-sum(e)#lower bound
for(x in a:b){sol=0
for(i in 0:(x/e[1]))sol=max(sol,o(i,e,x))
M=max(M,x*!sol)}

(And this led me to recover the earlier ‘Og entry on the coin problem! As of last November.) The published solution does not bring any useful light as to why 383 is the solution, except for demonstrating that 383 is non-representable and any larger integer is representable.

## Le Monde puzzle [#1158]

Posted in Books, Kids, R with tags , , , , , on November 10, 2020 by xi'an

A weekly puzzle from Le Monde on umbrella sharing:

Four friends, Antsa, Cyprien, Domoina and Fy, are leaving school to return to their common housing. It is raining and they only have one umbrella with only room for two. Given walking times, x¹, x², x³ and x⁴, find the fastest time by which all of the four will be home, assuming they all agree to come back with the umbrella if need be.

A recursive R function produces the solution

bez=function(starz=rexp(4),finiz=rep(0,4),rtrn=F){
if((!rtrn)&(sum(starz>0)==2)){return(max(starz))
}else{
tim=1e6
if(rtrn){
for(i in (1:4)[finiz>0]){
nstart=starz;nstart[i]=finiz[i]
nfini=finiz;nfini[i]=0
targ=finiz[i]+bez(nstart,nfini,FALSE)
if(targ<tim){tim=targ}}
}else{
for(i in (1:4)[starz>0])
for(j in (1:4)[starz>0]){
if(i!=j){
nstar=starz;nstar[i]=nstar[j]=0
nfini=finiz;nfini[i]=starz[i];nfini[j]=starz[j]
targ=max(starz[i],starz[j])+bez(nstar,nfini,TRUE)
if (targ<tim){tim=targ}
}}}
return(tim)}

which gives for instance

> bez()
[1] 3.297975
> bez(1:4)
[1] 11
> bez(rep(3,4))
[1] 15

## asymmetric information

Posted in Kids, R with tags , , , , , on November 4, 2020 by xi'an

Take a real number θ uniformly distributed over (0,100). Among three players, the winner is whoever guessed the closest price without going over θ. In the event all guesses exceeded θ, the contestant with the lowest (and therefore closest) guess is declared the winner. The second player knows the first player’s guess and the third player knows both other guesses. What is the optimal guess for the first player, assuming all players maximise their probability of winning?

Looking at the optimal solution z for the third player leads to six possible choices, depending on the connection between the other guesses, x and y. Which translates in the R code

topz=function(x,y){
if((2*y>=x)&(y>=1-x))  z=y-.001
if(max(4*y,1+y)<=2*x)  z=y+.001
if((2*x<=1+y)&(x<=1-y))z=x+.001
z}

third=function(x,y) ifelse(y<x,topz(x,y),topz(y,x))

For there, the optimal choice y for the second player follows and happens on a boundary of one of the six regions, which itself returns that the optimal choice for the first player is x=2/3, leading to equal chances of winning (although there is some uncertainty on the boundaries). It is thus feasible to beat the asymmetric information. The picture above was my attempt at representing the probabilities of gain for all three players, some of the six regions being clearly visible, with first axis being x and second being y [and z is one of x⁻,x⁺,y⁻,y⁺]. The R code is too pedestrian to be reproduced!

## Le Monde puzzle [#1159]

Posted in Books, Kids, R with tags , , , , , , on October 6, 2020 by xi'an

The weekly puzzle from Le Monde is quite similar to #1157:

Is it possible to break the ten first integers, 1,…,10, into two groups such that the sum over the first group is equal to the product over the second? Is it possible that the second group is of cardinal 4? of cardinal 3?

An exhaustive R search returns 3 solutions by

library(R.utils)
bitz<-function(i)
c(rev(as.binary(i)),rep(0,10))[d<-1:10]
for (i in 1:2^10)
if (sum(d[!!bitz(i)])==prod(b<-d[!bitz(i)])) print(b)
[1]  1  4 10 #40
[1] 6 7 #42
[1] 1 2 3 7 #42

which brings a positive reply to the question. Moving from N=10 to N=19 produces similar results

[1]  1  9 18 #162
[1]  2  6 14 #168
[1]  1  3  4 14 #168
[1]  1  2  7 12 #168

with this interesting pattern of only two acceptable products, but I am obviously unable to run the same code for N=49, which is the subsidiary question to the puzzle. Turning to a more conceptual (!) approach, over a long insomnia bout (!!) and a subsequent run, I realised that if there are three terms, x¹,x² and x³, in the second group, they need satisfy

x¹x²x³+x¹+x²+x³=½N(N+1)

and if in addition one of them is equal to 1, x¹ say, this equation simplifies into

(x²+1)(x³+1)=½N(N+1)

which always leads to a solution, as e.g. for N=49,

x¹=1, x²=24 and x³=48.

A brute-force search also led to a four term solution in that case

x¹=1, x²=7, x³=10 and x⁴=17.


text:
# Products of random stochastic matrices

As I mentioned, Behrouz Touri gave a really great presentation at ITA on some of his work with Angelia Nedić on products of stochastic matrices, some of which was in this paper on ArXiV. The setup of the paper is relatively straightforward — we have a sequence of independent random matrices $\{W(k)\}$, each of which is row-stochastic almost surely, and we want to know when the product $\lim_{k \to \infty} W(k) W(k-1) \cdots W(t_0)$ converges almost surely. The main result is that if the chain is balanced and strongly aperiodic, then the limit is a random stochastic matrix such that the rows in the same connected component of the infinite flow graph are equal.

Recall that for a chain $W$ a lazy version of the chain is $\alpha W + (1 - \alpha) I$. Laziness helps avoid periodicity by letting the chain be “stuck” with probability $(1 - \alpha)$. Strongly aperiodic means that there is a $\gamma \in (0,1]$ such that $\mathbb{E}[ W_{ii}(k) W_{ij}(k) ] \ge \gamma \mathbb{E}[ W_{ij}(k) ]$. Basically this is a sort of “expected laziness condition” which says that there is enough self-transition probability to avoid some sort of weak periodicity in the chain.

Consider a cut of the chain into a set of states $S$ and a set $\bar{S}$. A chain is balanced if there is an $\alpha > 0$ such that for all cuts $(S,\bar{S})$, we have $\mathbb{E}[ W_{S \bar{S}}(k) ] \ge \alpha \mathbb{E}[ W_{\bar{S} S}(k) ]$. So this is saying that at each time, the flow out of $S$ is commensurate with the flow into $S$.

The infinite flow graph has the same vertex set as the original chain, but with edge $(i,j)$ existing only if $\sum_{k} W_{ij}(k) + W_{ji}(k) = \infty$. That is, the edge has to exist infinitely often in the graph.

So to add it all up, the well-behaved independent products of stochastic matrices that converge are those which don’t behave badly over time — for each time $k$, they don’t shift around the mass too much and they are not too periodic. Basically, they don’t become volatile and cyclical, which sounds perfectly reasonable. So how does he prove it?

The first part is to connect the problem with a dynamic system whose state $x(k+1) = W(k+1) x(k)$ and look to see if the state converges in the limit. The next part uses a connection to absolute probability processes, which were used by Kolmogorov in 1936. A random vector process $\pi(k)$ is an absolute probability process for $\{W(k)\}$ if it is adapted to the same filtration as the chain, it’s stochastic almost surely, and

$\mathbb{E}[ \pi(k+1) W(k+1) | \mathcal{F}_k ] = \pi(k)$

Kolmogorov showed that for a deterministic sequence of stochastic matrices there is always an deterministic absolute probability process, so for independent chains we can always find a random absolute probability process. Using this, Touri and Nedić define a class of comparison functions which are super-martingales for each $\latex x(0)$ and have a limit. By choosing a particular comparison function they can get a version of the main result. It’s a nicely written paper and worth a skim if you’re interested in these things (as I am).