text:
Work with images¶

The pyagme.image module provides methods for loading and saving images. The method load() loads an image from the file system and returns a Surface object. The method convert() optimizes the image format and makes drawing faster:

img = pygame.image.load('bird.png')
img.convert()

Download the image bird.png to the same folder where your program resides:

bird.png

The method get_rect() returns a Rect object from an image. At this point only the size is set and position is placed at (0, 0). We set the center of the Rect to the center of the screen:

rect = img.get_rect()
rect.center = w//2, h//2

To recapitulate, we are working with 3 objects:

• screen is the Surface object representing the application window
• img is the Surface object of the image to display
• rect is the Rect object which is the bounding rectangle of the image

To display the image we fill the screen with a background color (GRAY). Then we blit the image, draw a red rectangle around it and finally update the screen:

screen.fill(GRAY)
screen.blit(img, rect)
pygame.draw.rect(screen, RED, rect, 1)
pygame.display.update()

Move the image with the mouse¶

At the beginning of the programm we set a boolean variable moving to False. Only when the mouse button is pressed, and when the mouse position is within the image (collidepoint) we set it to True:

elif event.type == MOUSEBUTTONDOWN:
if rect.collidepoint(event.pos):
moving = True

When the mouse button is released, we set it to False again:

elif event.type == MOUSEBUTTONUP:
moving = False

When the mouse moves, and the flag moving is True, then we move the image by the amount of relative movement (event.rel):

elif event.type == MOUSEMOTION and moving:
rect.move_ip(event.rel)

This is the whole code:

"""Move an image with the mouse."""

import pygame
from pygame.locals import *

RED = (255, 0, 0)
GRAY = (150, 150, 150)

pygame.init()
w, h = 640, 240
screen = pygame.display.set_mode((w, h))
running = True

img.convert()
rect = img.get_rect()
rect.center = w//2, h//2
moving = False

while running:
for event in pygame.event.get():
if event.type == QUIT:
running = False

elif event.type == MOUSEBUTTONDOWN:
if rect.collidepoint(event.pos):
moving = True

elif event.type == MOUSEBUTTONUP:
moving = False

elif event.type == MOUSEMOTION and moving:
rect.move_ip(event.rel)

screen.fill(GRAY)
screen.blit(img, rect)
pygame.draw.rect(screen, RED, rect, 1)
pygame.display.update()

pygame.quit()

image1.py

Rotate and Scale the image¶

The pygame.transform module provides methods for scaling, rotating and flipping images. As we are going to modify the image img we keep the original image in a variable called img0:

img0 = pygame.image.load(path)
img0.convert()

In order to show the image rectangle, we add a green border to the original image:

rect0 = img0.get_rect()
pygame.draw.rect(img0, GREEN, rect0, 1)

Then we place the place the image in the center of the screen:

center = w//2, h//2
img = img0
rect = img.get_rect()
rect.center = center

First we define the global variables scale and angle:

angle = 0
scale = 1

We use the R key to increment rotation by 10 degrees and (decrement if the SHIFT key is pressed). The function rotozoom() allows to combine rotation and scaling. We always transform the orignial image (img0). Repeated rotation or scaling of an image would degrade its quality:

if event.type == KEYDOWN:
if event.key == K_r:
if event.mod & KMOD_SHIFT:
angle -= 10
else:
angle += 10
img = pygame.transform.rotozoom(img0, angle, scale)

We use the S key to increment the scale by 10% (decrease if the SHIFT key is pressed):

elif event.key == K_s:
if event.mod & KMOD_SHIFT:
scale /= 1.1
else:
scale *= 1.1
img = pygame.transform.rotozoom(img0, angle, scale)

As the image is transformed the bounding rectangle changes size. It must be recalulated and placed at the center again:

rect = img.get_rect()
rect.center = center

Reset the image to the original¶

We use the O key to reset the image to its original state:

elif event.key == K_o:
img = img0
angle = 0
scale = 1

Flip the image¶

We use the H key to flip the image horizontally:

elif event.key == K_h:
img = pygame.transform.flip(img, True, False)

and the V key to flip the image vertically:

elif event.key == K_v:
img = pygame.transform.flip(img, False, True)

Detect edges with the Laplacian¶

The fonction laplacien(img) allows to detect the outline of the image:

elif event.key == K_l:
img = pygame.transform.laplacian(img)

The fonction scale2x(img) doubles the size of a pixel:

elif event.key == K_2:
img = pygame.transform.scale2x(img)

Transform the image with the mouse¶

In this section we show how to use the mouse to scale and rotate an image. At the beginning we import the math module:

import math

At the beginning we store the initial mouse position:

mouse = pygame.mouse.get_pos()

When the mouse moves we update the mouse position mouse and calculate the x, y coordinates from the center of the image. We also calculate the center-mouse distance d

elif event.type == MOUSEMOTION:
mouse = event.pos
x = mouse[0] - center[0]
y = mouse[1] - center[1]
d = math.sqrt(x ** 2 + y ** 2)

The atan2(y, x) math function allows to find the rotation angle. We need to transform radians in degrees. From the distance mouse-center we calculate the scale argument:

angle = math.degrees(-math.atan2(y, x))
scale = abs(5 * d / w)
img = pygame.transform.rotozoom(img0, angle, scale)
rect = img.get_rect()
rect.center = center

To finally draw the transformed image we first fille the whole screen background (GRAY), blit the transformed image, surround it with a red rectangle.

In order to give visual feedback for the mouse action when transforming an image, we

• draw a green line between the center of the image and the mouse position,

• place two circles on the center and on the mouse position:

screen.fill(GRAY)
screen.blit(img, rect)
pygame.draw.rect(screen, RED, rect, 1)
pygame.draw.line(screen, GREEN, center, mouse, 1)
pygame.draw.circle(screen, RED, center, 6, 1)
pygame.draw.circle(screen, RED, mouse, 6, 1)
pygame.display.update()

Here is the full code.

"""Rotate, scale and flip an image."""

import pygame
import math, sys, os
from pygame.locals import *

RED = (255, 0, 0)
GREEN = (0, 255, 0)
GRAY = (150, 150, 150)

pygame.init()
w, h = 640, 240
screen = pygame.display.set_mode((w, h))
running = True

module = sys.modules['__main__']
path, name = os.path.split(module.__file__)
path = os.path.join(path, 'bird.png')

img0.convert()

# draw a green border around img0
rect0 = img0.get_rect()
pygame.draw.rect(img0, GREEN, rect0, 1)

center = w//2, h//2
img = img0
rect = img.get_rect()
rect.center = center

angle = 0
scale = 1

mouse = pygame.mouse.get_pos()

while running:
for event in pygame.event.get():
if event.type == QUIT:
running = False

if event.type == KEYDOWN:
if event.key == K_r:
if event.mod & KMOD_SHIFT:
angle -= 10
else:
angle += 10
img = pygame.transform.rotozoom(img0, angle, scale)

elif event.key == K_s:
if event.mod & KMOD_SHIFT:
scale /= 1.1
else:
scale *= 1.1
img = pygame.transform.rotozoom(img0, angle, scale)

elif event.key == K_o:
img = img0
angle = 0
scale = 1

elif event.key == K_h:
img = pygame.transform.flip(img, True, False)

elif event.key == K_v:
img = pygame.transform.flip(img, False, True)

elif event.key == K_l:
img = pygame.transform.laplacian(img)

elif event.key == K_2:
img = pygame.transform.scale2x(img)

rect = img.get_rect()
rect.center = center

elif event.type == MOUSEMOTION:
mouse = event.pos
x = mouse[0] - center[0]
y = mouse[1] - center[1]
d = math.sqrt(x ** 2 + y ** 2)

angle = math.degrees(-math.atan2(y, x))
scale = abs(5 * d / w)
img = pygame.transform.rotozoom(img0, angle, scale)
rect = img.get_rect()
rect.center = center

screen.fill(GRAY)
screen.blit(img, rect)
pygame.draw.rect(screen, RED, rect, 1)
pygame.draw.line(screen, GREEN, center, mouse, 1)
pygame.draw.circle(screen, RED, center, 6, 1)
pygame.draw.circle(screen, RED, mouse, 6, 1)
pygame.display.update()

pygame.quit()

image2.py


text:
# Homework Help: Solving for time

1. Feb 19, 2015

### Calpalned

1. The problem statement, all variables and given/known data
A ball is launched from a height of 1.9m with a speed of 40 m/s at an angle of 10 degrees above the horizontal. Find the total time in the air.

2. Relevant equations
$y_f = y_0 + v_0y t + \frac{1}{2} t^2$

3. The attempt at a solution
Taking y0 = 1.9 m and v0 = 40sin(10), then using the quadratic formula, I got the answers t = 1.65 or t = -0.23. Clearly the former is what we need. However, my solutions guide got t = 3.3 instead (that is, double my answer). The solution guide used the equation $t = \frac{-v_0 sin(θ) - \sqrt{v_0^2 sin^2(θ) + 2gy_0}}{-\frac{1}{2}g}$ and got 3.3 seconds. Why is this the case?

2. Feb 19, 2015

### Staff: Mentor

They failed to multiply the coefficient of the squared term by 2 in the denominator. For the quadratic ax2 + bx + c = 0, the quadratic formula puts "2a" in the denominator.

format: plain


text:
Matematicheskie Trudy
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Tr.: Year: Volume: Issue: Page: Find

 Mat. Tr., 2013, Volume 16, Number 1, Pages 121–140 (Mi mt252)

On the upper bound in the large deviation principle for sums of random vectors

A. A. Mogul'skiĭab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia

Abstract: We consider the random walk generated by a sequence of independent identically distributed random vectors. The known upper bound for normalized sums in the large deviation principle was established under the assumption that the Laplace–Stieltjes transform of the distribution of the walk jumps exists in a neighborhood of zero. In the present article, we prove that, for a two-dimensional random walk, this bound holds without any additional assumptions.

Key words: large deviation principle, upper bound in the large deviation principle, deviation function, Cramér's condition.

Full text: PDF file (243 kB)
References: PDF file   HTML file

English version:
Siberian Advances in Mathematics, 2014, 24:2, 140–152

Bibliographic databases:

UDC: 519.21

Citation: A. A. Mogul'skiǐ, “On the upper bound in the large deviation principle for sums of random vectors”, Mat. Tr., 16:1 (2013), 121–140; Siberian Adv. Math., 24:2 (2014), 140–152

Citation in format AMSBIB
\Bibitem{Mog13} \by A.~A.~Mogul'ski{\v\i} \paper On the upper bound in the large deviation principle for sums of random vectors \jour Mat. Tr. \yr 2013 \vol 16 \issue 1 \pages 121--140 \mathnet{http://mi.mathnet.ru/mt252} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3156676} \elib{https://elibrary.ru/item.asp?id=19000375} \transl \jour Siberian Adv. Math. \yr 2014 \vol 24 \issue 2 \pages 140--152 \crossref{https://doi.org/10.3103/S1055134414020047}

• http://mi.mathnet.ru/eng/mt252
• http://mi.mathnet.ru/eng/mt/v16/i1/p121

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles
•  Number of views: This page: 252 Full text: 68 References: 32 First page: 4


text:
# What is the magnitude of the force of the car on the truck?

1. Sep 22, 2007

### aligass2004

1. The problem statement, all variables and given/known data
A 1100 kg car pushes a 1700 kg truck that has a dead battery. When the driver steps on the accelerator, the drive wheels of the car push against the ground with a force of 4500N. a.) What is the magnitude of the force of the car on the truck? b.) What is the magnitude of the force of the truck on the car?

2. Relevant equations
F=ma

3. The attempt at a solution
I tried drawing a free body diagram for this, but it didn't work out well.

2. Sep 22, 2007

### learningphysics

First do the freebody diagram of the truck+car system. That gives you acceleration...

Then do the freebody diagram of the car alone. that'll give the force of the truck on the car.

3. Sep 23, 2007

### aligass2004

I got the acceleration to be 1.607 m/s^2. I tried using F=ma, but it didn't work.

4. Sep 23, 2007

### learningphysics

The acceleration is correct. What equation did you get when you used F=ma for the car?

5. Sep 23, 2007

### aligass2004

The number I got was 1767.7N

6. Sep 23, 2007

### learningphysics

That's not right. What are the forces acting on the car?

7. Sep 23, 2007

### aligass2004

The forces acting on the car are weight, the normal force, and the force of the truck.

8. Sep 23, 2007

### learningphysics

You're missing one force. The main one.

9. Sep 23, 2007

### aligass2004

I don't understand.

10. Sep 23, 2007

### learningphysics

The 4500N.

11. Sep 23, 2007

### aligass2004

Ok, so the normal force equal 4500N as well. So how do I go about finding the force of the truck on the car with all of that information?

12. Sep 23, 2007

### learningphysics

It's not the normal force... It is a forward force exerted at the back of the car... (it's the same force you used for the truck+car part).

Write out the F = ma equation for the car in the horizontal direction.

13. Sep 23, 2007

### aligass2004

I am still confused.

14. Sep 23, 2007

### learningphysics

There's a 4500N forward force at the back of the car... there's a backward force from the truck.

$$\Sigma{F} = ma$$

$$4500 - F_{truck} = m_{car}a$$

15. Sep 23, 2007

### aligass2004

I got the answer to be 2732.3, but I still understand the forward force at the back of the car thing.

16. Sep 23, 2007

### learningphysics

How did you do the first part?

17. Sep 23, 2007

### aligass2004

I found the acceleration.

18. Sep 23, 2007

### learningphysics

Yes, how did you find the acceleration? You used the 4500N force... how did you use it... how did you know how to use it?

19. Sep 23, 2007

### aligass2004

I used F=ma and manipulated the equation around to a=F/m. I don't know why I knew to use it though.

20. Sep 23, 2007

### learningphysics

Draw a picture... the 4500N force is pushing the car forward... and the car is pushing the truck forward...


text:
# vertex coloring of a graph $G$ such that colors appear twice

1. Let $G=(V,E)$ be a graph whose vertices can be colored with $m$-colors, such that each color appears at least twice.

2. Let $\lambda(G)$ denote the minimum number of colors needed for a vertex-coloring of $G$

Use 1. to prove that such a coloring can be achieved with $\lambda(G)$ colors

Let $\alpha$ denote a coloring with property 1. and $\beta$ a coloring with $\lambda(G)$ colors. $\beta$ has a color class with only one vertex if $\beta$ doesn't have property 1.

I don't know how that helps to prove that such a coloring can be achieved with $\lambda(G)$ colors

Edit: A coloring of the graph $G$ is a proper coloring. $u,v$ have different colors if $(u,v)\in E$

Would appreciate any help

• In 1 and 2, are the colorings supposed to be proper colorings, i.e., adjacent vertices have different colors?
– bof
Jun 17 '18 at 23:35
• Is $\lambda(G)$ the chromatic number of $G$? If so, why do you use $\lambda$ instead of the usual $\chi$?
– bof
Jun 17 '18 at 23:44
• @bof Sry, you're right. The vertex coloring is supposed to be a proper coloring and I used $\lambda$ because the script I am learning from used it as well Jun 19 '18 at 1:30


text:
## 過去の記録

#### 代数学コロキウム

16:40-17:40   数理科学研究科棟(駒場) 056号室

Special values of zeta functions of singular varieties over finite fields via higher chow groups (JAPANESE)

### 2013年05月14日(火)

#### トポロジー火曜セミナー

16:30-18:00   数理科学研究科棟(駒場) 056号室
Tea: 16:00 - 16:30 コモンルーム

Vanishing cycles and homotopies of wrinkled fibrations (JAPANESE)
[ 講演概要 ]
Wrinkled fibrations on closed 4-manifolds are stable
maps to closed surfaces with only indefinite singularities. Such
fibrations and variants of them have been studied for the past few years
to obtain new descriptions of 4-manifolds using mapping class groups.
Vanishing cycles of wrinkled fibrations play a key role in these studies.
In this talk, we will explain how homotopies of wrinkled fibrtions affect
their vanishing cycles. Part of the results in this talk is a joint work
with Stefan Behrens (Max Planck Institute for Mathematics).

#### 講演会

16:30-18:00   数理科学研究科棟(駒場) 118号室
5/10(金) 5/14(火) 5/21(火) 5/24(金)の4回連続講演です。部屋と時間は毎回同じです

Laurent Lafforgue 氏 (IHES)
Kernels of Langlands' automorphic transfer and non-linear Poisson formulas (ENGLISH)

### 2013年05月13日(月)

#### 複素解析幾何セミナー

10:30-12:00   数理科学研究科棟(駒場) 126号室

Geometry and analysis of isolated essential singularities and their applications (JAPANESE)
[ 講演概要 ]
We establish a rescaling principle for isolated essential singularities of holomorphic curves and quasiregular mappings, and gives several applications of it in the theory of value distribution and dynamics. This is a joint work with Pekka Pankka.

### 2013年05月11日(土)

#### 保型形式の整数論月例セミナー

13:30-16:00   数理科学研究科棟(駒場) 123号室

Symplectic-orthogonal theta lifts and explicit formulas for archimedean Whittaker functions (JAPANESE)

Mumford形式の無限積表示とSelbergゼータ値への応用 (JAPANESE)
[ 講演概要 ]

#### 東京無限可積分系セミナー

10:30-12:00   数理科学研究科棟(駒場) 117号室
Anatol Kirillov 氏 (RIMS Kyoto Univ.)
Saga of Dunkl elements (ENGLISH)
[ 講演概要 ]
The Dunkl operators has been introduced by C. Dunkl in the middle of
80's of the last century as a powerful mean in the study of orthogonal
polynomials related with finite Coxeter groups. Later it was discovered
a deep connection of the the Dunkl operators with the theory of
Integrable systems and Invariant Theory.
In my talk I introduce and study a certain class of nonhomogeneous
quadratic algebras together with the distinguish set of mutually
commuting elements inside of each, the so-called universal Dunkl elements.
The main problem I would like to discuss is : What is the algebra
generated by universal Dunkl elements in a different representations of
I'm planning to present partial answers on that problem related with
classical and quantum Schubert and Grothendieck Calculi as well as the
theory of elliptic series.
Also some interesting algebraic properties of the quadratic algebra(s)
in question will be described.

### 2013年05月10日(金)

#### 講演会

16:30-18:00   数理科学研究科棟(駒場) 118号室
5/10(金) 5/14(火) 5/21(火) 5/24(金)の4回連続講演です。

Laurent Lafforgue 氏 (IHES)
Kernels of Langlands' automorphic transfer and non-linear Poisson formulas (ENGLISH)

### 2013年05月09日(木)

#### 幾何コロキウム

10:00-11:30   数理科学研究科棟(駒場) 122号室

[ 講演概要 ]

### 2013年05月08日(水)

#### 作用素環セミナー

16:30-18:00   数理科学研究科棟(駒場) 118号室
Paul Muhly 氏 (University of Iowa)
Boundaries for Tensor Algebras (ENGLISH)

### 2013年05月07日(火)

#### トポロジー火曜セミナー

16:30-18:00   数理科学研究科棟(駒場) 056号室
Tea: 16:00 - 16:30 コモンルーム

Homological intersection in braid group representation and dual
Garside structure (JAPANESE)
[ 講演概要 ]
One method to construct linear representations of braid groups is to use
an action of braid groups on certain homology of local system coefficient.
Many famous representations, such as Burau or Lawrence-Krammer-Bigelow
representations are constructed in such a way. We show that homological
intersections on such homology groups are closely related to the dual
Garside structure, a remarkable combinatorial structure of braid, and
prove that some representations detects the length of braids in a
surprisingly simple way.
This work is partially joint with Bert Wiest (Univ. Rennes1).

#### 数値解析セミナー

16:30-18:00   数理科学研究科棟(駒場) 123号室

[ 講演概要 ]

この講演では、まず外接半径条件とそれに関する数値実験の結果を示し、「外接半径条件によりわかったこと」、「外接半径条件でも説明がつかないこと」を説明する。さらに、外接半径条件の発見から派生した諸問題、あるいは有限要素解析の数学的基礎理論において、現在においても未解決な問題について解説し、特に若い研究者の注意を喚起したい。
[ 講演参考URL ]
http://www.infsup.jp/utnas/

### 2013年04月30日(火)

#### Lie群論・表現論セミナー

16:30-18:00   数理科学研究科棟(駒場) 126号室

The homomorphisms between scalar generalized Verma modules of gl(n,C) with regular infinitesimal characters (JAPANESE)
[ 講演概要 ]
We will explain the classification of the homomorphisms between scalar generalized Verma modules of gl(n,C) with regular infinitesimal characters. In fact, they are compositions of elementary homomorphisms. The main ingredient of our proof is the translation principle in the mediocre region.

#### トポロジー火曜セミナー

16:30-18:00   数理科学研究科棟(駒場) 056号室
Tea: 16:00 - 16:30 コモンルーム
Francis Sergeraert 氏 (L'Institut Fourier, Univ. de Grenoble)
Discrete vector fields and fundamental algebraic topology.
(ENGLISH)
[ 講演概要 ]
Robin Forman invented the notion of Discrete Vector Field in 1997.
A recent common work with Ana Romero allowed us to discover the notion
of Eilenberg-Zilber discrete vector field. Giving the topologist a
totally new understanding of the fundamental tools of combinatorial
algebraic topology: Eilenberg-Zilber theorem, twisted Eilenberg-Zilber
theorem, Serre and Eilenberg-Moore spectral sequences,
Eilenberg-MacLane correspondence between topological and algebraic
classifying spaces. Gives also new efficient algorithms for Algebraic
Topology, considerably improving our computer program Kenzo, devoted
to Constructive Algebraic Topology. The talk is devoted to an
introduction to discrete vector fields, the very simple definition of
the Eilenberg-Zilber vector field, and how it can be used in various
contexts.

### 2013年04月24日(水)

#### 代数学コロキウム

17:30-18:30   数理科学研究科棟(駒場) 056号室

Good reduction of ramified affinoids in the Lubin-Tate perfectoid space (ENGLISH)
[ 講演概要 ]
Recently, Weinstein finds some affinoids in the Lubin-Tate perfectoid space and computes their reduction in equal characteristic case. The cohomology of the reduction realizes the local Langlands correspondence for some representations of GL_h, which are unramified in some sense. In this talk, we introduce other affinoids in the Lubin-Tate perfectoid space in equal characteristic case, whose reduction realizes "ramified" representations of conductor exponent h+1. We call them ramified affinoids. We study the cohomology of the reduction and its relation with the local Langlands correspondence. This is a joint work with Takahiro Tsushima.

(本講演は「東京北京パリ数論幾何セミナー」として、インターネットによる東大数理, Morningside Center of MathematicsとIHESの双方向同時中継で行います.)

#### Kavli IPMU Komaba Seminar

17:00-18:30   数理科学研究科棟(駒場) 002号室

Calabi-Yau threefolds of Type K (ENGLISH)
[ 講演概要 ]
We will provide a full classification of Calabi-Yau threefolds of Type
K studied by Oguiso and Sakurai. Our study completes the
classification of Calabi-Yau threefolds with infinite fundamental
group. I will then discuss special Lagrangian T3-fibrations of
Calabi-Yau threefolds of type K. This talk is based on a joint work
with Kenji Hashimoto.

### 2013年04月23日(火)

#### 数値解析セミナー

16:30-18:00   数理科学研究科棟(駒場) 002号室

[ 講演概要 ]

[ 講演参考URL ]
http://www.infsup.jp

#### トポロジー火曜セミナー

16:30-18:00   数理科学研究科棟(駒場) 056号室
Tea: 16:00 - 16:30 コモンルーム
Andrei Pajitnov 氏 (Univ. de Nantes)
Twisted Novikov homology and jump loci in formal and hyperformal spaces (ENGLISH)
[ 講演概要 ]
Let X be a CW-complex, G its fundamental group, and R a repesentation of G.
Any element of the first cohomology group of X gives rise to an exponential
deformation of R, which can be considered as a curve in the space of
representations. We show that the cohomology of X with local coefficients
corresponding to the generic point of this curve is computable from a spectral
sequence starting from the cohomology of X with R-twisted coefficients. We
compute the differentials of the spectral sequence in terms of Massey products,
and discuss some particular cases arising in Kaehler geometry when the spectral
sequence degenerates. We explain the relation of these invariants and the
twisted Novikov homology. This is a joint work with Toshitake Kohno.

### 2013年04月22日(月)

#### 講演会

16:45-18:15   数理科学研究科棟(駒場) 126号室
Stefano Olla 氏 (Univ. Paris-Dauphine)
Thermal conductivity and weak coupling (ENGLISH)
[ 講演概要 ]
We investigate the macroscopic thermal conductivity of a chain of anharmonic oscillators and more general systems, under weak coupling limits and energy conserving stochastic perturbations of the dynamics. In particular we establish a series expansion in the coupling parameter.

#### 代数幾何学セミナー

16:30-18:00   数理科学研究科棟(駒場) 118号室
Professor Igor Reider 氏 (Universite d'Angers / RIMS)
Kodaira-Spencer classes, geometry of surfaces of general type and Torelli
theorem (ENGLISH)
[ 講演概要 ]
In this talk I will explain a geometric interpretation of Kodaira-Spencer classes and apply
it to the study of the differential of the period map of weight 2 Hodge structures for surfaces
of general type.
My approach is based on interpreting Kodaira-Spencer classes as higher rank bundles and
then studing their stability. This naturally leads to two parts:
1) unstable case
2) stable case.
I will give a geometric characterization of the first case and show how to relate the second
case to a special family of vector bundles giving rise to a family of rational curves. This family
of rational curves is used to recover the surface in question.

#### 複素解析幾何セミナー

10:30-12:00   数理科学研究科棟(駒場) 126号室

Kobayashi hyperbolic imbeddings into low degree surfaces in three dimensional projective spaces (JAPANESE)
[ 講演概要 ]
We construct smooth irreducible curves of the lowest possible degree in quadric and cubic surfaces whose complements are Kobayashi hyperbolically imbedded into those surfaces. This is a joint work with Atsushi Ito.

### 2013年04月20日(土)

#### 調和解析駒場セミナー

13:00-18:00   数理科学研究科棟(駒場) 128号室
このセミナーは,月に1度程度,不定期に開催されます.

Directional maximal operators and radial weights on the plane
(JAPANESE)
[ 講演概要 ]
Let $\\Omega$ be a set of unit vectors and $w$ be a radial weight on the plane. We consider the weighted directional maximal operator defined by
$M_{\\Omega,w}f(x):=\\sup_{x\\in R\\in \\cB_{\\Omega}}\\frac{1}{w(R)}\\int_{R}|f(y)|w(y)dy$,
where $\\cB_{\\Omega}$ denotes the all rectangles on the plane whose longest side is parallel to some unit vector in $\\Omega$ and $w(R)$ denotes $\\int_{R}w$.
In this talk we give a sufficient condition of the weight
for an almost-orthogonality principle related to these maximal operators to hold. The condition allows us to get weighted norm inequality
$\\|M_{\\Omega,w}f\\|_{L^2(w)}\\le C \\log N \\|f\\|_{L^2(w)}$,
when $w(x)=|x|^a$, $a>0$, and $\\Omega$ is a set of unit vectors on the plane with cardinality $N\\gg 1$.

[ 講演概要 ]

### 2013年04月19日(金)

#### PDE実解析研究会

10:30-11:30   数理科学研究科棟(駒場) 056号室

An approximation scheme for the anisotropic and the planar crystalline curvature flow (JAPANESE)
[ 講演概要 ]
In 2004 Chambolle proposed an algorithm for the mean curvature flow based on a variational problem. Since then, some extensions of his algorithm have been studied.
In this talk we would like to discuss the convergence of the anisotropic variant of his algorithm by use of the anisotropic signed distance function. An application to the approximation for the planar motion by crystalline curvature is also discussed.

### 2013年04月18日(木)

#### 幾何コロキウム

10:00-11:30   数理科学研究科棟(駒場) 122号室

Harmonic maps into Grassmannian manifolds (JAPANESE)
[ 講演概要 ]
A harmonic map from a Riemannian manifold into a Grassmannian manifold is characterized by a vector bundle, a space of sections of the bundle and the Laplace operator. This characterization can be considered as a generalization of Theorem of Takahashi on minimal immersions into a sphere (J.Math.Soc.Japan 18 (1966)) and implies the well-known fact that the Kodaira embedding is a harmonic map.

We apply the main result to generalize a Theorem of do Carmo and Wallach (Ann.of Math. 93 (1971)) and describe a moduli space of harmonic maps with constant energy densities and some properties about pull-back bundles and connections from a Riemannian homogeneous space into a Grassmannian. We give some applications including a rigidity of minimal immersions from the complex projective line to complex projective spaces (S.Bando and Y.Ohnita, J. Math. Soc. Japan 39 (1987)).

The ADHM-construction of instantons gives a family of maps into Grassmannians via monad theory on the twistor space. These maps are, in general, not harmonic maps, but are similar to maps obtained in our generalized do Carmo-Wallach theorem. We compare these two constructions of moduli spaces.

### 2013年04月17日(水)

#### 作用素環セミナー

16:30-18:00   数理科学研究科棟(駒場) 118号室
Tamar Friedmann 氏 (Univ. Rochester)
Singularities, algebras, and the string landscape (ENGLISH)

### 2013年04月16日(火)

#### Lie群論・表現論セミナー

16:30-18:30   数理科学研究科棟(駒場) 126号室
Michael Pevzner 氏 (Reims University) 16:30-17:30
Non-standard models for small representations of GL(n,R) (ENGLISH)
[ 講演概要 ]
We shall present new models for some parabolically induced
unitary representations of the real general linear group which involve Weyl symbolic calculus and furnish very efficient tools in studying branching laws for such representations.
Pierre Clare 氏 (Penn. State University, USA) 17:30-18:30
Degenerate principal series of symplectic groups (ENGLISH)
[ 講演概要 ]
We will discuss properties of representations of symplectic groups induced from maximal parabolic subgroups of Heisenberg type, including K-types formulas, expressions of intertwining operators and the study of their spectrum.


text:
Fixed Error Probability Asymptotics For Erasure and List Decoding

Fixed Error Probability Asymptotics For Erasure and List Decoding

Vincent Y. F. Tan and Pierre Moulin V. .Y. F. Tan is with the Department of Electrical and Computer Engineering (ECE) and the Department of Mathematics, National University of Singapore (Email: vtan@nus.edu.sg). P. Moulin is with the Department of Electrical and Computer Engineering (ECE), University of Illinois at Urbana-Champaign (Email: moulin@ifp.uiuc.edu).
Abstract

We derive the optimum second-order coding rates, known as second-order capacities, for erasure and list decoding. For erasure decoding for discrete memoryless channels, we show that second-order capacity is where is the channel dispersion and is the total error probability, i.e., the sum of the erasure and undetected errors. This total error probability, as are other error probabilities in this paper, is fixed at a non-zero constant. We show numerically that the expected rate at finite blocklength for erasures decoding can exceed the finite blocklength channel coding rate. We also show that the analogous result also holds for lossless source coding with decoder side information, i.e., Slepian-Wolf coding. For list decoding, we consider list codes of deterministic sizes that scale as and show that the corresponding second-order capacity is , where is the permissible error probability, i.e., the probability that the true message is not in the list. We also consider lists of polynomial size and derive bounds on the third-order coding rate in terms of the order of the polynomial . These bounds are tight for symmetric and singular channels. The direct parts of the coding theorems leverage on the simple threshold decoder and converses are proved using variants of the hypothesis testing converse.

I Introduction

In many communication scenarios, it is advantageous to allow the decoder to have the option of either not deciding at all or putting out more than one estimate of the message. These are respectively known as erasure and list decoding respectively and have been studied extensively in the information theory literature [1, 2, 3, 4, 5, 6, 7]. The erasure and list options generally allow for smaller undetected error probabilities so these options are useful in practice.

In this paper, we revisit the problem or erasure and list decoding from the viewpoint of second- and third-order asymptotics. The study of second-order asymptotics for fixed (non-vanishing) error probability was first done by Strassen [8, Thm. 1.2] who showed for a well-behaved discrete memoryless channel (DMCs) that the maximum number of codewords at (average or maximum) error probability , namely , satisfies

 logM∗(Wn,ϵ)=nC+√nVΦ−1(ϵ)+O(logn), (1)

where and are respectively the capacity and the dispersion of and is the inverse of the standard Gaussian cumulative distribution function (cdf). Also see Kemperman [9, Thm. 11.3] for the corresponding result for constant composition codes. This line of work has been revisited by numerous authors recently and they considered various other channel models such as the additive white Gaussian (AWGN) channel [10, 11], bounds on the third-order (logarithmic) term [12, 13, 14, 15] and extensions to multi-terminal problems such as the two-encoder Slepian-Wolf problem and the multiple-access channel [16].

I-a Main Contributions

In this paper, for erasure decoding, we consider constant undetected and total (sum of undetected and erasure) error probabilities (numbers between and ) and we obtain the analogue of the second-order term in (1). We show that the coefficient of the second-order term, termed the second-order capacity, is where is the total error probability. The second-order capacity is thus completely independent of the undetected error probability. We then compute the expected rate at finite blocklength allowing erasures and show that it can exceed the finite blocklength rate without the erasure option, i.e., usual channel coding. We show that these results carry over in a straightforward manner to the problem of lossless source coding with side information, i.e., the Slepian-Wolf problem [17] which was previously studied in the for the case without the erasure option [16].

For list decoding, we consider lists of deterministic size of order and show that the second-order capacity is , where is the permissible error probability. We also consider lists of polynomial size and demonstrate bounds on the third-order term in terms of the degree of the polynomial . These bounds turn out to tight for channels that are symmetric and singular–a canonical example being the binary erasure channel [14]. To the best of the authors’ knowledge, this is the first time that lists of size other than constant or exponential have been considered in the literature. Practically, the advantage of smaller lists is that they result in lower search complexity for the true message within the decoded list.

I-B Related Work

Previously, the study of erasure and list decoding has been primarily from the error exponents perspective. We summarize some existing works here. Forney [1] derived optimal decision rules by generalizing the Neyman-Pearson lemma and also proved exponential upper bounds for the error probabilities using Gallager’s Chernoff bounding techniques [18]. Shannon-Gallager-Berlekamp [2] proved exponential lower bounds for the error probabilities and also considered lists of exponential size . They showed that sphere packing error exponent (evaluated at the code rate minus ) is an upper bound on the reliability function [19, Ex. 10.28]. Bounds for the error probabilities were derived by Telatar [3] using a general decoder parametrized by an asymmetric relation which is a function of the channel law. Blinovsky [4] studied the exponents of the list decoding problem at low (and even ) rate. Csiszár-Körner [19, Thm. 10.11] present exponential upper bounds for universally attainable erasure decoding using the method of types. Moulin [5] generalized the treatment there and presented improved error exponents under some conditions. Recently, Merhav also considered alternative methods of analysis [6] and expurgated exponents for these problems [7]. The same author also derived erasure and list exponents for the Slepian-Wolf problem [20].

Another related line of work concerns constant error probability non-asymptotic fundamental limits of channel coding with various forms of feedback. Polyanskiy-Poor-Verdú [21] studied various incremental redundancy schemes and derived performance bounds under receiver- and transmitter-confirmation. In incremental redundancy systems/schemes, one is allowed to transmit a sequence of coded symbols with numerous opportunities for confirmation before the codeword is resent if necessary. In contrast in our study of channel coding with the erasure option in Sec. III-B, we analyze the expected performance of the easily-implementable Forney-style [1] single-codeword repetition scheme that allows for confirmation (or erasure) at the end of a complete codeword block and repeats the same message until the erasure event no longer occurs. We compare a quantity termed the expected rate and to the ordinary channel coding rate. Inspired by [21], Chen et al. [22] derived non-asymptotic bounds for feedback systems using incremental redundancy with noiseless transmitter confirmation. Williamson-Chen-Wesel [23] also improved on the bounds in [21] for variable-length feedback coding.

I-C Structure of Paper

This paper is structured as follows: In Sec. II, we set the stage by introducing our notation and defining relevant quantities such as the second-order capacity. In Sec. III, we state our main results for channel coding with the decoding and list option. In Sec. IV, we show that the channel coding results carry over to the Slepian-Wolf problem [17]. All the proofs are detailed in Sec. V.

Ii Problem Setting and Main Definitions

Let be a random transformation (channel) from a discrete input alphabet to a discrete output alphabet . We denote length- deterministic (resp. random) strings (resp. ) by lower case (resp. upper case) boldface. If satisfies for every and the sets and are finite, is said to be a DMC. We focus on DMCs in this paper but extensions to other channels such as the AWGN channel are straightforward. For a sequence , its type is the empirical distribution . For a finite alphabet , let and be the set of probability mass functions and -types [19] (types with denominator at most ) respectively. For two sequences , we say that is a conditional type of given if for all . ( is not unique if for some .) The -shell of a sequence , denoted as is the set of all such that the joint type of is . The set of all conditional types for which is non-empty for some with type is denoted as . All logs are to the base with the understanding that .

For information-theoretic quantities, we will mostly follow the notation in Csiszár and Körner [19]. We denote the information capacity of the DMC as . We let be the set of capacity-achieving input distributions. If has joint distribution , define to be the induced output distribution and

 V(P,W):=EX[Var(logW(Y|X)PW(Y)∣∣X)] (2)

to be the conditional information variance. The -dispersion of the DMC [8, 11, 10] is defined as

 Vϵ:={Vmin:=minP∈ΠV(P,W)ϵ<1/2Vmax:=maxP∈ΠV(P,W)ϵ≥1/2. (3)

We will assume throughout that the DMC satisfies . For integers , we denote and . Let be the cdf of a standard Gaussian and its inverse. We now define erasure codes.

Definition 1.

An -erasure code for is a pair of mappings such that and . The disjoint decoding regions are denoted as ; the erasure region is denoted as ; and the conditional undetected, erasure and total error probabilities are defined as

 λu(m) :=∑~m∈[M]∖{m}W(D~m|f(m)) (4) λe(m) :=W(D0|f(m)) (5) λt(m) :=∑~m∈[0:M]∖{m}W(D~m|f(m)) (6)

Note that . Typically, the code is designed so that as the cost of making an undetected error is much higher than that of declaring an erasure.

Definition 2.

An -erasure code for is an -erasure code for the same channel where

1. If ,

 maxm∈[M]λu(m)≤ϵu,maxm∈[M]λt(m)≤ϵt. (7)
2. If

 maxm∈[M]λu(m)≤ϵu,1M∑m∈[M]λt(m)≤ϵt. (8)
3. If ,

 1M∑m∈[M]λu(m)≤ϵu,maxm∈[M]λt(m)≤ϵt. (9)
4. If ,

 1M∑m∈[M]λu(m)≤ϵu,1M∑m∈[M]λt(m)≤ϵt. (10)

In Definition 2, we consider erasure codes with constraints on the undetected and total error probabilities similar to [6, 1, 5]. An alternate formulation would be to consider -erasure codes where is the erasure probability. We find the former formulation more traditional and the analysis is also somewhat easier.

Definition 3.

A number is an -achievable erasure second-order coding rate for the DMC with capacity if there exists a sequence of -erasure codes such that

 liminfn→∞1√n(logMn−nC) ≥r, (11) limsupn→∞ϵu,n ≤ϵu,and (12) limsupn→∞ϵt,n ≤ϵt. (13)

The -erasure second-order capacity is the supremum of all -achievable erasure second-order coding rates.

We now turn our attention to codes which allow their decoders to output a list of messages. Let be the set of subsets of of size . Furthermore, we use the notation to denote the set of subsets of of size not exceeding .

Definition 4.

An -list code for is a pair of mappings such that and . The (not-necessarily disjoint) decoding regions are denoted as and the conditional error probability is defined as

 λ(m):=W(Y∖Dm|f(m)). (14)
Definition 5.

An -list code for is an -list code for the same channel where if ,

 maxm∈[M]λ(m)≤ϵ, (15)

or if ,

 1M∑m∈[M]λ(m)≤ϵ. (16)
Definition 6.

A number is an -achievable list second-order coding rate for the DMC with capacity if there exists a sequence of -list codes such that in addition to (11), the following hold

 limsupn→∞1√nlogLn ≤l,and (17) limsupn→∞ϵn ≤ϵ. (18)

The -list second-order capacity is the supremum of all -achievable list second-order coding rates.

According to (17), we stipulate that the list size grows as . This differs from previous works on list decoding in which the list size is either constant [18, 7] or exponential [19, 3, 5, 2, 6, 7, 4, 20]. This scaling affects the second-order (dispersion) term. To understand how the list size may affect the higher-order term, consider the following definition.

Definition 7.

A number is an -achievable list third-order coding rate for the DMC with capacity and positive -dispersion if there exists a sequence of -list codes such that

 liminfn→∞1logn(logMn−nC−√nVϵnΦ−1(ϵn)) ≥s, (19) limsupn→∞logLnlogn ≤α,and (20) limsupn→∞√n(ϵn−ϵ) <∞. (21)

The -list third-order capacity is the supremum of all -achievable list third-order coding rates.

Inequality (20) implies that the size of the list grows polynomially and in particular it scales as . This scaling affects the third-order (logarithmic) term studied by a number of authors [13, 12, 15, 14] in the context of ordinary channel coding (without list decoding). By (19), if is -achievable, there exists a sequence of codes of sizes satisfying

 logMn≥nC+√nVϵnΦ−1(ϵn)+slogn+o(logn), (22)

and having list sizes and average error probabilities not exceeding . The more stringent condition on the sequence of error probabilities in (21) (relative to (18)) is because appears as the argument in the function, which forms part of the coefficient of the second-order term in the asymptotic expansion of . If the weaker condition (18) were in place, the approximation error between and the target which is of the order would affect the third-order term, which is the object of study here. The stronger condition in (21) ensures that the third-order (logarithmic) term is unaffected by the approximation error between and which is now of the order .

Iii Main Results for Channel Coding

In this section, we summarize the main results of this paper concerning channel coding with an erasure or list option. For simplicity, we assume that the DMC satisfies though our results can be extended in a straightforward manner to the case where .

Iii-a Decoding with Erasure Option

Theorem 1.

For any ,

 r∗era,a,b(ϵu,ϵt)=√VϵtΦ−1(ϵt), (23)

where can be any element in .

The proof of Theorem 1 can be found in Section V-A.

A few comments are in order: First, Theorem 1 implies that if is the maximum number of codewords that can be transmitted over with undetected and total error and respectively, then

 logM∗(Wn;ϵu,ϵt)=nC+√nVϵtΦ−1(ϵt)+o(√n). (24)

We see that the backoff from the capacity at blocklength is approximately independent of . (This backoff is positive for .) Observe that the second-order term does not depend on , the undetected error probability. Only the total error probability comes into play in the asymptotic characterization of . In fact, in the proof, we first argue that it suffices to show that is an achievable -erasure second-order coding rate for , i.e., the undetected error probability is asymptotically . Clearly, any achievable -erasure second-order coding rate is also an achievable -erasure second-order coding rate for any .

Second, in the direct part of the proof of Theorem 1, we use threshold decoding, i.e. declare that message is sent if the empirical mutual information is higher than a threshold. If no message’s empirical mutual information exceeds the threshold, then an erasure is declared. This simple rule, though universal, is not the optimal one (in terms of minimizing the total error while holding the undetected error fixed). The optimal rule was derived using a generalized version of the Neyman-Pearson lemma by Forney [1, Thm. 1] and it is stated as

 D∗m:={y:Wn(y|f(m))≥ψ∑~m∈[M]∖{m}Wn(y|f(~m))}, (25)

for some threshold . However, this rule appears to be difficult for second-order analysis and is more amenable to error exponent analysis [5, 7]. Because the likelihood of the second most likely codeword is usually much higher than the rest (excluding the first), Forney also suggested the simpler but, in general, suboptimal rule [1, Eq. (11a)]

 D′m:={y:Wn(y|f(m))≥ψmax~m∈[M]∖{m}Wn(y|f(~m))}. (26)

We analyzed this rule in the asymptotic setting (i.e., as tends to infinity) in the same way as one analyzes the random coding union (RCU) bound [10, Thm. 16] [12, Sec. 7] for ordinary channel coding but the analysis is more involved than threshold decoding which suffices for proving the second-order achievability of (23). What was somewhat surprising to the authors is that the optimal decoding scheme in (25) (a generalization of the Neyman-Pearson lemma to arbitrary non-negative measures) and the suboptimal scheme in (26) are somewhat difficult to analyze, but the simpler empirical mutual information thresholding rule can be shown to be second-order optimal. This is in contrast to error exponent analysis of erasure decoding where the rules (25) and (26) and their variants are ubiquitously analyzed in the literature, e.g., [19, 3, 5, 6].

Third, the converse is based on Strassen’s idea [8, Eq. (4.18)], establishing a clear link between point-to-point channel coding and binary hypothesis testing. Also see Kemperman’s general converse bound [9, Lem. 3.1] and for a more modern treatment, the various forms of the meta-converse in [10, Sec. III-E]. The hypothesis testing converse technique only depends on the total error probability, explaining the presence of and not in (23).

Finally, we remark that Theorem 1 (as well as Theorem 2 to follow bar the statement in (37)) carries over verbatim for the AWGN channel where the capacity and dispersion are and respectively and is the signal-to-noise ratio (SNR) of the AWGN channel.

Iii-B The Expected Rate and An Example

We now compare the expected rate achieved using decoding with the erasure option to ordinary channel coding. Define

 ϵe:=ϵt−ϵu (27)

as the erasure probability and note from the assumption of Theorem 1 that . Now consider sending independent blocks of information each of length . Because transmission succeeds (no erasure declared) with probability , the total number of bits we can transmit in each block is well approximated by the random variable

 R(n)e:={C+√Vϵt/nΦ−1(ϵt)w.p.1−ϵe0w.p.ϵe (28)

This random variable has expectation

 (29)

Fix . By Hoeffding’s inequality, the total number of bits we can transmit over the blocks is in the interval

 [(1−ϵe−δ)⋅b⋅(nC+√nVϵtΦ−1(ϵt)),(1−ϵe+δ)⋅b⋅(nC+√nVϵtΦ−1(ϵt))] (30)

with probability exceeding . This reduction in rate in (29)–(30) by the factor of in the so-called single-codeword repetition scheme was first observed by Forney [1, Eq. (49)]. Essentially, one may use an automatic repeat request (ARQ) scheme111Forney [1] calls this class of retransmission schemes decision feedback schemes in his paper, but nowadays the term ARQ is more common. to resend the entire block of information if there is an erasure.

For ordinary channel coding with error probability , we can send approximately

 b⋅(nC+√nVϵuΦ−1(ϵu)) (31)

bits over the independent blocks and so, dividing by , the non-asymptotic channel coding rate (analogue of (29)) can be approximated [10] by

 R(n)c:=C+√VϵunΦ−1(ϵu). (32)

In the analysis in (28)–(32), we have assumed that the Gaussian approximation is sufficiently accurate. It was numerically shown in [10] that the Gaussian approximation is accurate for some channels (such as the binary symmetric channel, binary erasure channel and additive white Gaussian noise channel) and moderate blocklengths (of order ) and error probabilities (or order ). Also see Fig. 1 for a precise quantification of the accuracy of the Gaussian approximation in our setting.

Clearly if are constants,

 C=limn→∞R(n)c>limn→∞E[R(n)e]=(1−ϵe)C, (33)

so there is no advantage in allowing for erasures asymptotically. However, in finite blocklength (by this we mean the per-block blocklength ) regime, for “moderate” , we may have

 R(n)c

so erasure decoding may be advantageous in expectation. We illustrate the difference between and with a concrete example.

Example: In Fig. 1, we consider a binary symmetric channel (BSC) with crossover probability so bits/channel use and bits/channel use. (For the BSC, does not depend on .) We keep the undetected error probability at and vary the erasure error probability in the interval . We chose two blocklengths . We observe that for blocklength and a moderate erasure probability of , the gain of coding with the erasure option over ordinary channel coding is rather pronounced. This can be seen by comparing either the Gaussian approximations or the finite blocklength bounds. This gain is reduced if (i) is increased because we retransmit the whole block more often on average via the use of decision feedback or (ii) becomes large so the second-order term becomes less significant (cf. (33)). We also note from the left plot that the Gaussian approximation is reasonably accurate when compared to the dependence-testing [10, Thm. 34] and meta-converse [10, Thm. 35] finite blocklength bounds under the current settings. The DT bound is especially close to the Gaussian approximation when the performance of coding with erasures peaks.

Finally, we remark that the advantage of coding with the erasures option over ordinary channel coding was also shown from the error exponents perspective by Forney in [1]. More precisely, Forney [1, Eq. (55)] showed that the feedback exponent has slope for rates near and below capacity, thus improving on the ordinary exponent which has slope in the same region.

Iii-C List Decoding

Theorem 2.

For any , we have the second-order result

 r∗list,a(l,ϵ)=l+√VϵΦ−1(ϵ). (35)

where . Furthermore, if and , we also have the third-order result

 α≤s∗list(α,ϵ)≤12+α. (36)

If the DMC is symmetric in the Gallager sense222A DMC is symmetric in the Gallager sense [18, Sec. 4.5, pp. 94] if the set of channel outputs can be partitioned into subsets such that within each subset, the matrix of transition probabilities satisfies the following: every row (resp. column) is a permutation of every other row (resp. column). and singular,333A DMC is singular if for all , with it is true that . then we can make the stronger statement

 s∗list(α,ϵ)=α. (37)

The proof of Theorem 2 which is partly based on Proposition 3 below can be found in Section V-B.

Theorem 2 shows that if we allow the list to grow as , then the second-order capacity is increased by . This is concurs with the intuition we obtain from the analysis of error exponents for list decoding by Shannon-Gallager-Berlekamp [2]. See also the exercises in Gallager [18, Ex. 5.20] and Csiszár-Körner [19, Ex. 10.28] which are concerned solely with first-order (capacity) analysis.

For the third-order result in (36), we observe that there is a gap. This is, in part, due to the fact that we use threshold decoding to decide which messages belong to the list. This decoding strategy appears to be suboptimal in the third-order sense for DMCs [12, Sec. 7] [24, Thm. 53] and AWGN channels [15]. It also appears that one needs to use a version of maximum-likelihood (ML) decoding as in (26) and analyze an analogue of the RCU bound [10, Thm. 16] carefully to obtain the additional for the direct part. Whether this can be done for channel coding with list decoding to obtain a tight third-order result general DMCs is an open question. Nonetheless for singular and symmetric channels considered by Altuğ and Wagner [14], such as the BEC, the converse (upper bound) can be tightened and this results in the conclusive result in (37).

A by-product of the proof of Theorem 2 is the following non-asymptotic converse bound for list-decoding which may be of independent interest. Kostina-Verdú [25, Thm. 4] developed and used a version of this bound for the purposes of fixed error asymptotics of joint source-channel coding, just as Csiszár [26] also used a list decoder in his study of the error exponents for joint source-channel coding.

Proposition 3.

Let be the best (smallest) type-II error in a (deterministic) hypothesis test between and subject to the type-I error being no larger than . Every -list code for satisfies

 ML≤infQ∈P(Y)supP∈P(X)1β1−ϵ(P×W,P×Q). (38)

This bound immediately reduces to the so-called meta-converse in [10, Sec. III-E] by setting . We will see that the ratio plays a critical role in both the converse and direct parts. This is also evident in existing works such as Shannon-Gallager-Berlekamp [2, Sec. IV] but the non-asymptotic bound in (38) appears to be novel.

Iv An Extension to Slepian-Wolf Coding

In this section, we show that the techniques developed are also applicable to lossless source coding with decoder side information, i.e., the Slepian-Wolf problem [17]. Let be a correlated source where the alphabets and are finite. The assumption that and are finite sets can be dispensed at the cost of non-universality in the coding scheme [27].

Definition 8.

An -code for the correlated source is defined by two functions and where represents the erasure symbol.

Definition 9.

An -code for the correlated source is an -code satisfying

 ≤ϵu,and (39) ∑x,yPXY(x,y)1{φ(f(x),y)≠x} ≤ϵt. (40)

The parameters and are known as the undetected and total error probabilities respectively.

We consider discrete, stationary and memoryless sources in which the source alphabet is and the side-information alphabet is .

Definition 10.

A number is said to be an -achievable second-order coding rate for the correlated source if there exists a sequence of -codes such that

 limsupn→∞1√n(logMn−nH(X|Y)) ≤r (41) limsupn→∞ϵu,n ≤ϵu (42) limsupn→∞ϵt,n ≤ϵt. (43)

The infimum of all -achievable second-order coding rates is the optimum second-order coding rate .

Hence, we are allowing the erasure option for the Slepian-Wolf problem but we restrict the undetected and total errors to be at most and respectively. The second-order asymptotics for the Slepian-Wolf problem with two encoders without erasures was studied by Tan and Kosut in [16].

Define to be the conditional varentropy [28] of the stationary, memoryless source . The following result here parallels Theorem 1 pertaining to channel coding with the erasure option.

Theorem 4.

For any ,

 r∗era(ϵu,ϵt)=√V(X|Y)Φ−1(1−ϵt). (44)

The proof of Theorem 4 can be found in Section V-C. The direct part uses random binning [29] and thresholding of the empirical conditional entropy [16] and the converse uses a non-asymptotic information spectrum converse bound by Miyake and Kanaya [30]. Also see [31, Thm. 7.2.2].

Again, we observe that the optimum second-order coding rate does not depend on the undetected error probability as long as it is smaller than the total error probability . Hence, the observation we made in Fig. 1–namely that at finite blocklengths the expected performance with the erasure option can exceed that without the erasure option–also applies in the Slepian-Wolf setting.

V Proofs

In this section, we provide the proofs of the theorems in the paper.

V-a Decoding with Erasure Option: Proof of Theorem 1

V-A1 Converse Part

Recall that is the best (smallest) type-II error in a hypothesis test (without randomization) of versus subject to the condition that the type-I error is no larger than . This function was studied extensively in [32]. Let us fix any -erasure code for . This means that

 minm∈[Mn]Wn(Dm|f(m))≥1−ϵt,n. (45)

Note that only the total error comes into play in (45) and thus the second-order capacity in (23) only depends on . In essence, an -erasure code for is an -channel code for (a channel code for with codewords and maximum error probability at most ) so any converse for usual channel coding also applies here with the error probability for usual channel coding being the total error in erasure decoding. We describe some details of the converse proof to make the paper self-contained.

We now assume that the code is constant composition, i.e. all codewords are of the same type . This only leads to a penalty in which does not affect the second-order term. Now, for any permutation invariant output distribution (this means that for every permutation ), we have

 1 ≥Mn∑m=1Q(Dm) (46) (47) =Mn∑m=1β1−ϵt,n(Wn(⋅|f(m)),Q) (48) =Mnβ1−ϵt,n(Wn(⋅|x),Q), (49)

where (46) follows because are disjoint; (47) follows from (45); (48) uses the definition of ; and finally (49) follows from the fact that does not depend on for permutation invariant (which is what we choose to be) and constant composition codes [8]. We also used to denote any element in the type class . Choose to be the product distribution . Since satisfies (13), for every , there exists sufficiently large such that . Hence, from (49),

 Mn≤β−11−ϵt−η(Wn(⋅|x),Q). (50)

Now, we use [8, Sec. 2] to assert that for all ,

 −logβ1−ϵ(Wn(⋅|x),Q)=nI(P,W)+√nV(P,W)Φ−1(ϵ)+O(logn). (51)

Hence, by putting (50) and (51) together, we obtain

 logMn≤maxP∈P(X)nI(P,W) +√nV(P,W)Φ−1(ϵt+η)+O(logn) (52)

By using the usual continuity arguments (e.g. [13, Lem. 7]),

 logMn≤nC+√nVϵt+ηΦ−1(ϵt+η)+O(logn). (53)

Thus, by letting ,

 limsupn→∞1√n(logMn−nC)≤√Vϵt+ηΦ−1(ϵt+η). (54)

The converse proof is complete for the case by taking . Note that even though is, in general, discontinuous at (i.e., when ), we may let and use the fact that to assert that as desired.

To get to the setting, first we let be the maximum number of codewords in an erasure with undetected and total error probabilities respectively under the -setting. By using an expurgation argument as in [10, Eq. (284)] it is easy to show that for all ,

 M∗ave,ave(Wn,ϵu,ϵt)≤(11−1/τ)2M∗max,max(Wn,τϵu,τϵt). (55)

Setting proves the claim for all the other 3 cases.

V-A2 Direct Part

It suffices to prove that is an achievable -erasure second-order coding rate for . Indeed, here the total error . However, any achievable -second-order coding rate is also an achievable -second-order coding rate for any . Furthermore, by an expurgation argument similar to (55), the same statement can be proved under the setting.

For this proof, we show that the second-order capacity in (23) is also universally attainable–i.e. the code does not require channel knowledge. A simpler proof based on thresholding the likelihood can also be be used; however, channel knowledge is required. See Sec. V-B3 for an analogue of the alternative strategy.

Fix a type . Generate codewords uniformly at random from the type class . Denote the random codebook as . The number is to be chosen later. Let be some threshold to be chosen later. At the receiver, we decode to if and only if is the unique message to satisfy

 ^I(X(^m)∧Y)≥γ (56)

where is the empirical mutual information of , i.e. the mutual information of the random variables whose distribution is the joint type . Assume as usual that the true message . We use the following elementary result which is shown in the proof of the packing lemma [19, Lem. 10.1].

Lemma 5.

Let be any -type. Let and be selected independently and uniformly at random from the type class . Let be the channel output when is the input, i.e. . Then, for every and every ,

 Pr[^I(¯¯¯¯¯X∧Y)>γ]≤(n+1)|X|+|X||Y|exp(−nγ). (57)

The undetected error probability is bounded as

 Pr[Eu] ≤Pr[maxm∈[Mn]∖{1}^I(X(m)∧Y)≥γ] (58) ≤(Mn−1)Pr[^I(X(2)∧Y)≥γ] (59) ≤(Mn−1)(n+1)|X||Y|+|X|exp(−nγ), (60)

where (59) follows from the union bound and the fact that the codewords are generated in an identical manner, and (60) follows from Lemma 5 noting that is independent of , the channel output when is the input.

The erasure event can be expressed as

 Ee:=E(1)e∪E(2)e (61)

where

 E(1)e :={^I(X(m)∧Y)<γ,∀m∈[Mn]},and (62) E(2)e :={^I(X(m)∧Y)≥γ,% for at least 2 messages m∈[Mn]}. (63)

Clearly, we have that

 E(1)e ⊂F(1)e:={^I(X(1)∧Y)<γ},and (64) E(2)e ⊂F(2)e:={maxm∈[Mn]∖{1}^I(X(m)∧Y)≥γ}. (65)

Note that the probability of was already bounded in (58)–(60). Hence it remains to upper bound the probability of defined in (64). We let the random conditional type of given be . Then, we have

 Pr[F(1)e] ≤Pr[^I(X(1)∧Y)≤γ] (66) =Pr[I(P,W)+∑x,y(U(y|x)−W(y|x))I′W(y|x)+O(∥U−W∥2)≤γ] (67)

where the final step follows by Taylor expanding around and . We also can bound the remainder term uniformly [33] yielding

 Pr[F(1)e]≤Pr[I(P,W)+∑x,y(U(y|x)−W(y|x))I′W(y|x)≤γ+O(lognn)]+O(n−2). (68)

Wang-Ingber-Kochman [33] computed the relevant first-, second- and third-order statistics of the random variable allowing us to apply the Berry-Esseen theorem [34, Ch. XVI.5] to the probability in (68), leading to

 Pr[F(1)e]≤Φ⎛⎝γ+O(lognn)−I(P,W)√V(P,W)/n⎞⎠+O(n−1/2).


text:
# integration by substitution

• May 3rd 2010, 10:55 PM
demode
integration by substitution
http://img413.imageshack.us/img413/6839/49887281.gif

(a) Let $u=x^4$ then $du=4x^3dx$ and therefore $\frac{du}{4x^3}=dx$. We get:

$\int^b_{a} f(x^4)dx= \int^{1^4}_{(-1)^4} 1+u \frac{du}{4x^3} =\int^{1}_{1} 1+u \frac{du}{4x^3}$

Both limits of integration in the new integral are 1, so the value of the definite integral is 0.

(b)
$\frac{du}{dx}=4x^3$

It is only zero when x=0. Jacobian become zero at (0,0) so it vanishes at this point.

(c) This is the part I'm really stuck on: from part (a) I know what to substitute for "dx" when I make the substitution $u=x^4$. So I think this is what the question is asking for:

$\int^0_{-1} 1+u \frac{du}{4x^3} + \int^1_0 1+u \frac{du}{4x^3}$

But expressions involving x should not appear in the new integrals. How do I get rid of the " $4x^3$"? Can anyone show me how to do this part?
• May 3rd 2010, 11:07 PM
drumist
Since $u=x^4$ is the substitution being made, you can take a fourth root on both sides to get $x=\pm \sqrt[4]{u}$. The $\pm$ is important here, and is why the integral needs to be split into two regions.

In the region $-1, we should get $x=-\sqrt[4]{u}$ because x is always negative in this region. Using the same logic, for $0, we should use $x=\sqrt[4]{u}$. Now that you have an expression for x in both regions you can make the substitution.

By the way, make sure you use parentheses in your integral. It should be like this:

$\int^0_{-1} (1+u) \frac{du}{4x^3} + \int^1_0 (1+u) \frac{du}{4x^3}$
• May 3rd 2010, 11:12 PM
CalculusCrazed
I'm pretty sure that you need to set the limits also. For each of your integrals you approach a value that is undefined.


text:
# Revision history [back]

### Can't find opencv.hpp, however it is not installed in /usr/include/

Context: I am a new Ubuntu 16.04 user and I am trying to get OpenCV running on my system. I had some problems downloading and installing OpenCV with CUDA installed, so I used the solution as proposed by daveselinger in his last post here: https://github.com/opencv/opencv/issues/6677.
This left me with OpenCV installed at: ~/Documents/my\ folder/opencv/. Notably, this also includes: ~/Documents/my\ folder/opencv/include/opencv2/opencv.hpp.
Now as far as I have been able to figure out, there should (also?) be a copy at: /usr/include/opencv2/opencv.hpp. At least, if I have interpreted the answer here correctly: http://www.answers.opencv.org/question/14712/opencvhpp-not-in-opencv2/. Now the issue is that there is no folder "openCV2" (nor a folder "openCV") in /usr/include/. This probably is the reason why "#include <opencv2 opencv.hpp="">" leads to "fatal error: opencv2/opencv.hpp: No such file or directory". Does anyone know how to solve this error? Normally I would try several times of reinstalling, but installing openCV took around 4 hours, so I'd like to take a more structured approach if possible.

### Can't find opencv.hpp, however it is not installed in /usr/include/

Context: I am a new Ubuntu 16.04 user and I am trying to get OpenCV running on my system. I had some problems downloading and installing OpenCV with CUDA installed, so I used the solution as proposed by daveselinger in his last post here: https://github.com/opencv/opencv/issues/6677.
This left me with OpenCV installed at: ~/Documents/my\ folder/opencv/. folder/opencv/. Notably, this also includes: ~/Documents/my\ folder/opencv/include/opencv2/opencv.hpp. folder/opencv/include/opencv2/opencv.hpp.
Now as far as I have been able to figure out, there should (also?) be a copy at: /usr/include/opencv2/opencv.hpp. /usr/include/opencv2/opencv.hpp. At least, if I have interpreted the answer here correctly: http://www.answers.opencv.org/question/14712/opencvhpp-not-in-opencv2/. Now the issue is that there is no folder "openCV2" (nor a folder "openCV") in /usr/include/. /usr/include/. This probably is the reason why "#include <opencv2 opencv.hpp="">" #include <opencv2/opencv.hpp> leads to "fatal error: opencv2/opencv.hpp: No such file or directory". Does anyone know how to solve this error? Normally I would try several times of reinstalling, but installing openCV took around 4 hours, so I'd like to take a more structured approach if possible.

### Can't find opencv.hpp, however it is not installed in /usr/include/

Context: I am a new Ubuntu 16.04 user and I am trying to get OpenCV running on my system. I had some problems downloading and installing OpenCV with CUDA installed, so I used the solution as proposed by daveselinger in his last post here: https://github.com/opencv/opencv/issues/6677.
This left me with OpenCV installed at: ~/Documents/my\ folder/opencv/. Notably, this also includes: ~/Documents/my\ folder/opencv/include/opencv2/opencv.hpp.
Now as far as I have been able to figure out, there should (also?) be a copy at: /usr/include/opencv2/opencv.hpp. At least, if I have interpreted the answer here correctly: http://www.answers.opencv.org/question/14712/opencvhpp-not-in-opencv2/. Now the issue is that there is no folder "openCV2" (nor a folder "openCV") in /usr/include/. This probably is the reason why #include <opencv2/opencv.hpp> leads to "fatal error: opencv2/opencv.hpp: No such file or directory". Does anyone know how to solve this error? Normally I would try several times of reinstalling, but installing openCV took around 4 hours, so I'd like to take a more structured approach if possible.

Edit: the solution was that I failed to use sudo make install in the installation of openCV. This caused the files to fail to be copied to /usr/local/include. That in turn made them impossible to find for programs trying to use those files.


text:
## MechStiff tutorialÂ¶

This is an example how to use Mechanical Stiffness Calculations implemented in ProDy package.

The theory of MechStiff has been describe in:

Eyal E, Bahar I (2008) Toward a molecular understanding of the anisotropic response of proteins to external forces: insights from elastic network models Biophys J 94: 3424-35. PMID: 18223005; PMC2292382

http://www.ncbi.nlm.nih.gov/pubmed/18223005?ordinalpos=5&itool=EntrezSystem2.PEntrez.Pubmed.Pubmed_ResultsPanel.Pubmed_RVDocSum

In [1]:
%matplotlib inline
from prody import *
import matplotlib.pylab as plt

In [2]:
gfp, header = parsePDB('1gfl', header=True)

@> PDB file is found in the local folder (/data/prody_tutorials/.../1gfl.pdb.gz).
@> 3950 atoms and 1 coordinate set(s) were parsed in 0.06s.

In [3]:
gfp

Out[3]:
<AtomGroup: 1gfl (3950 atoms)>
In [4]:
calphas = gfp.select('protein and chain A and name CA')

In [5]:
calphas

Out[5]:
<Selection: 'protein and chain A and name CA' from 1gfl (230 atoms)>

## Building Hessian using ANM modelÂ¶

We instantiate an ANM instance and we are building Hessian matrix by passing selected atoms.

In [6]:
anm = ANM('GFP ANM analysis')

In [7]:
anm.buildHessian(calphas, cutoff=13.0)

@> Hessian was built in 0.08s.

In [8]:
anm.getHessian().round(3)

Out[8]:
array([[ 9.017,  2.741, -0.979, ...,  0.   ,  0.   ,  0.   ],
[ 2.741,  5.32 ,  1.181, ...,  0.   ,  0.   ,  0.   ],
[-0.979,  1.181,  5.663, ...,  0.   ,  0.   ,  0.   ],
...,
[ 0.   ,  0.   ,  0.   , ...,  4.794, -0.052, -3.557],
[ 0.   ,  0.   ,  0.   , ..., -0.052,  3.885,  1.827],
[ 0.   ,  0.   ,  0.   , ..., -3.557,  1.827,  7.321]])

## Mechanical Stiffness Matrix CalculationsÂ¶

We can perfom MechStiff calculations for selected group of 230 Ca's atoms.

In [9]:
anm.buildMechStiff(calphas)

@> 690 modes were calculated in 0.45s.
@> Calculating stiffness matrix.
@> Stiffness matrix calculated in 0.57s.
@> The range of effective force constant is: 5.27141824578 to 17.3849094465.

In [10]:
anm.getStiffness()

Out[10]:
array([[ 0.        ,  8.54744466,  8.55133411, ...,  8.73270017,
8.36529536,  7.42692504],
[ 8.54744466,  0.        ,  8.89990284, ...,  8.98097054,
8.61849698,  7.77257692],
[ 8.55133411,  8.89990284,  0.        , ...,  8.87863489,
8.55675667,  7.84521673],
...,
[ 8.73270017,  8.98097054,  8.87863489, ...,  0.        ,
8.87731778,  8.36590599],
[ 8.36529536,  8.61849698,  8.55675667, ...,  8.87731778,
0.        ,  9.52997339],
[ 7.42692504,  7.77257692,  7.84521673, ...,  8.36590599,
9.52997339,  0.        ]])

To obtain matrix with effective spring constant values use:

In [11]:
showMechStiff(anm, calphas, 'jet_r')

@> 690 modes were calculated in 0.62s.
@> Calculating stiffness matrix.
@> Stiffness matrix calculated in 0.24s.
@> The range of effective force constant is: 5.27141824578 to 17.3849094465.

Out[11]:
(<matplotlib.image.AxesImage at 0x7f7be0830590>,
<matplotlib.colorbar.Colorbar at 0x7f7bc988ba90>)


text:
Article Contents
Article Contents

# Identifying defects in an unknown background using differential measurements

• We present a new qualitative imaging method capable of selecting defects in complex and unknown background from differential measurements of farfield operators: i.e. far measurements of scattered waves in the cases with and without defects. Indeed, the main difficulty is that the background physical properties are unknown. Our approach is based on a new exact characterization of a scatterer domain in terms of the far field operator range and the link with solutions to so-called interior transmission problems. We present the theoretical foundations of the method and some validating numerical experiments in a two dimensional setting.
Mathematics Subject Classification: 35R60, 35R30, 65M32.

 Citation:

•  [1] L. Audibert and H. Haddar, A generalized formulation of the linear sampling method with exact characterization of targets in terms of farfield measurements, Inverse Problems, 30 (2014), 035011, 20pp.doi: 10.1088/0266-5611/30/3/035011. [2] G. Bal, L. Carin, D. Liu and K. Ren, Experimental validation of a transport-based imaging method in highly scattering environments, Inverse Problems, 23 (2007), 2527-2539.doi: 10.1088/0266-5611/23/6/015. [3] L. Borcea, F. González del Cueto, G. Papanicolaou and C. Tsogka, Filtering deterministic layer effects in imaging, SIAM Rev., 54 (2012), 757-798.doi: 10.1137/120880975. [4] L. Borcea, J. Garnier, G. Papanicolaou and C. Tsogka, Enhanced statistical stability in coherent interferometric imaging, Inverse Problems, 27 (2011), 085004, 33pp.doi: 10.1088/0266-5611/27/8/085004. [5] H. Brezis, Functional Analysis, SObolev Spaces and Partial Differential Equations, Universitext, Springer, New York, 2011. [6] F. Cakoni and D. Colton, Qualitative Methods in Inverse Scattering Theory. An Introduction, Interaction of Mechanics and Mathematics, Springer-Verlag, Berlin, 2006. [7] F. Cakoni, M. Fares and H. Haddar, Analysis of two linear sampling methods applied to electromagnetic imaging of buried objects, Inverse Problems, 22 (2006), 845-867.doi: 10.1088/0266-5611/22/3/007. [8] D. Colton and R. Kress, Inverse Acoustic and Electromagnetic Scattering Theory, 3rd edition, Applied Mathematical Sciences, 93, Springer, New York, 2013.doi: 10.1007/978-1-4614-4942-3. [9] J.-P. Fouque, J. Garnier, G. Papanicolaou and K. Sølna, Wave Propagation and Time Reversal in Randomly Layered Media, Stochastic Modelling and Applied Probability, 56, Springer, New York, 2007.doi: 10.1007/978-0-387-49808-9_4. [10] Y. Grisel, V. Mouysset, P.-A. Mazet and J.-P. Raymond, Determining the shape of defects in non-absorbing inhomogeneous media from far-field measurements, Inverse Problems, 28 (2012), 055003, 19pp.doi: 10.1088/0266-5611/28/5/055003. [11] H. Haddar, Sampling 2d, 2013, http://sourceforge.net/projects/samplings-2d/. [12] A. Kirsch and N. Grinberg, The Factorization Method for Inverse Problems, Oxford Lecture Series in Mathematics and its Applications, 36, Oxford University Press, Oxford, 2008. [13] A. I. Nachman, L. Päivärinta and A. Teirilä, On imaging obstacles inside inhomogeneous media, J. Funct. Anal., 252 (2007), 490-516.doi: 10.1016/j.jfa.2007.06.020. [14] B. P. Rynne and B. D. Sleeman, The interior transmission problem and inverse scattering from inhomogeneous media, SIAM J. Math. Anal., 22 (1991), 1755-1762.doi: 10.1137/0522109. [15] J. Sylvester, Discreteness of transmission eigenvalues via upper triangular compact operators, SIAM J. Math. Anal., 44 (2012), 341-354.doi: 10.1137/110836420.


text:
## Polar Bonds

Of these three separate and individual elements: F, Ra, and As, Arsenic is more likely to form polar bonds. Why and how do you tell?


text:
# The capital balances, prior to the liquidation of the XYZ partnership, were as follows: X, Y, and... 1 answer below »

The capital balances, prior to the liquidation of the XYZ partnership, were as follows:

## Plagiarism Checker

Submit your documents and get free Plagiarism report

Free Plagiarism Checker

## Recent Questions in Managerial Accounting

Happy with Solution Ask a Similar Question


text:
## Gluing and Wormholes for the Einstein constraint equations.(English)Zbl 1013.83008

Summary: We establish a general gluing theorem for constant mean curvature solutions of the vacuum Einstein constraint equations. This allows one to take connected sums of solutions or to glue a handle (wormhole) onto any given solution. Away from this handle region, the initial data sets we produce can be made as close as desired to the original initial data sets. These constructions can be made either when the initial manifold is compact or asymptotically Euclidean or asymptotically hyperbolic, with suitable corresponding conditions on the extrinsic curvature. In the compact setting a mild nondegeneracy condition is required. In the final section of the paper, we list a number ways this construction may be used to produce new types of vacuum spacetimes.

### MSC:

 83C05 Einstein’s equations (general structure, canonical formalism, Cauchy problems) 53Z05 Applications of differential geometry to physics
Full Text:


text:
CCC '05 S5 - Pinball Ranking

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem types
Canadian Computing Competition: 2005 Stage 1, Senior #5

Pinball is an arcade game in which an individual player controls a silver ball by means of flippers, with the objective of accumulating as many points as possible. At the end of each game, the player's score and rank are displayed. The score, an integer between and , is that achieved by the player in the game just ended. The rank is displayed as " of ". is the total number of games ever played on the machine, and is the position of the score for the just-ended game within this set.

More precisely, is one greater than the number of games whose score exceeds that of the game just ended.

Input Specification

You are to implement the pinball machine's ranking algorithm. The first line of input contains a positive integer, , the total number of games played in the lifetime of the machine. lines follow, given the scores of these games, in chronological order.

Output Specification

You are to output the average of the ranks (rounded to two digits after the decimal) that would be displayed on the board. At least one test case will have . All test cases will have .

Sample Input

5
100
200
150
170
50

Sample Output

2.20

Explanation

The pinball screen would display (in turn):

1 of 1
1 of 2
2 of 3
2 of 4
5 of 5

The average rank is .

• Lemonsity  commented on Dec. 2, 2018, 4:16 p.m.

Can we assume no two input are the same?

If they are the same, what should I output?

• icyblue87  commented on Dec. 3, 2018, 6:58 p.m.

Inputs are not necessarily distinct

• Xue_Alex  commented on July 29, 2017, 9:22 p.m.

tfw changing all floats to doubles AC's

• Pleedoh  commented on May 15, 2017, 5:14 p.m.

Round to 2 decimal places?

• mse387  commented on May 15, 2017, 5:38 p.m.

Output Specification

"...output the average of the ranks (rounded to two digits after the decimal) that...."

• Pleedoh  commented on May 15, 2017, 6:41 p.m.

Right,sorry.

• septence123  commented on Jan. 5, 2017, 11:48 p.m.
Still getting TLE?

I implemented BST and still got TLE? Is there something faster?

• ZQFMGB12  commented on Jan. 6, 2017, 12:25 a.m.

• Kirito  commented on July 31, 2016, 8:18 p.m. edit 3
NVM

Saw the site update popup.

• Xyene  commented on July 31, 2016, 8:19 p.m.

Yes.

• MathBunny123  commented on Jan. 29, 2016, 10:11 p.m.
Too slow? Help?

According to DMOJ my code is too slow, but I run the test-files from CCC's website and it finishes all of them instantly. Is my approach wrong? I feel like the 1sec time limit is too close to my solution or something.

• jeffreyxiao  commented on Jan. 29, 2016, 11:03 p.m.

Your solution is $(O(N^2\ log N)$ because insertion into an ArrayList at an arbitrary position is $O(N)$ time

• MathBunny  commented on Jan. 30, 2016, 12:10 p.m.

Really? Okay thanks a lot!

• bobhob314  commented on Jan. 24, 2015, 9:20 a.m.
Score

Will the scores be repeated?

• Sentient  commented on Jan. 24, 2015, 11:00 a.m.

Yes, scores can be repeated; they are not guaranteed to be distinct

• lolzballs  commented on March 19, 2015, 11:53 a.m.

When they are repeated, is the rank the same, lower or higher?

• quantum  commented on March 19, 2015, 12:04 p.m.

Look at the italicized line.

• FatalEagle  commented on March 19, 2015, 11:59 a.m.

More precisely, is one greater than the number of games whose score exceeds that of the game just ended.

• quantum  commented on Dec. 1, 2014, 2:11 p.m.
Partial Points

This problem now have partial points enabled. The test cases have been re-weighted to give reasonable points for different algorithms to solve this problem. All non-AC submissions have been rejudged.

• BMP  commented on Nov. 28, 2014, 5:01 p.m.
moar time limit

plz

• FatalEagle  commented on Nov. 28, 2014, 6:05 p.m.

Your program isn't going to pass within a resasonable amount of time. Brute force like you are doing will not pass every problem on the judge. The best solution so far uses 0.057s in the worst case.


text:
# American Institute of Mathematical Sciences

March  2016, 15(2): 341-365. doi: 10.3934/cpaa.2016.15.341

## The stability of nonlinear Schrödinger equations with a potential in high Sobolev norms revisited

 1 Department of Applied Mathematics, Hankyong National University, Ansong 456-749 2 Department of Mathematical Sciences, Korea Advanced Institute of Science and Technology, 335 Gwahangno, Yuseong-gu, Daejeon, Korea 305-701

Received  February 2015 Revised  November 2015 Published  January 2016

We consider the nonlinear Schrödinger equations with a potential on $\mathbb T^d$. For almost all potentials, we show the almost global stability in very high Sobolev norms. We apply an iteration of the Birkhoff normal form, as in the formulation introduced by Bourgain [4]. This result reproves a dynamical consequence of the infinite dimensional Birkhoff normal form theorem by Bambusi and Grebert [2].
Citation: Myeongju Chae, Soonsik Kwon. The stability of nonlinear Schrödinger equations with a potential in high Sobolev norms revisited. Communications on Pure and Applied Analysis, 2016, 15 (2) : 341-365. doi: 10.3934/cpaa.2016.15.341
##### References:
 [1] D. Bambusi, Birkhoff normal form for some nonlinear PDEs, Comm. Math. Phys., 234 (2003), 253-285. doi: 10.1007/s00220-002-0774-4. [2] D. Bambusi and B. Grebert, Birkhoff normal form for PDE's with tame modulus, Duke Math. J., 135 (2006), 507-567. doi: 10.1215/S0012-7094-06-13534-2. [3] J. Bourgain, On the growth in time of higher Sobolev norms of smooth solutions of Hamiltonian PDE, Intern. Math. Res. Notices, 6 (1996), 277-304. doi: 10.1155/S1073792896000207. [4] J. Bourgain, On diffusion in High-dimensional Hamiltonian systems and PDE, J. d'analyse Math., 80 (2000), 1-34. doi: 10.1007/BF02791532. [5] J. Bourgain, Remarks on stability and diffusion in high-dimensional Hamiltonian systems and partial differential equations, Ergodic Theory Dynam. Syst., 24 (2004), 1331-1357. doi: 10.1017/S0143385703000750. [6] D. Cohen, E. Hairer and C. Lubich, Long-time analysis of nonlinearly perturbed wave equations via modulated Fourier expansions, Arch. Rational Mech. Anal., 187 (2008), 341-368. doi: 10.1007/s00205-007-0095-z. [7] J. Colliander, S. Kwon and T. Oh, A remark on normal forms and the "upside-down" I -method for periodic NLS: growth of higher Sobolev norms, J. d'analyse Math., 118 (2012), 55-82. doi: 10.1007/s11854-012-0029-z. [8] J. Colliander, M. Keel, G. Staffilani, H. Takaoka and T. Tao, Transfer of energy to high frequencies in the cubic defocusing nonlinear Schrödinger equation, Invent. Math., 181 (2010), 39-113. doi: 10.1007/s00222-010-0242-2. [9] L. H. Eliasson and S. B. Kuksin, KAM for nonlinear Schrödinger equation, Annals of Math., 172 (2010), 371-435. doi: 10.4007/annals.2010.172.371. [10] E. Faou, and B. Grebert, A Nekhoroshev type theorem for the nonlinear Schrödinger equation on the d-dimensional torus, Analysis and PDE, 6 (2013), 1243-1262. doi: 10.2140/apde.2013.6.1243. [11] B. Grebert, Birkhoff normal form and Hamiltonian PDEs, Partial Differential Equations and Applications, 1-46, Sémin. Congr., 15, Soc. Math. France, Paris, 2007. [12] B. Grebert, T. Kappeler and J. Pöschel, Normal form theory for the NLS equatons,, preprint, (). [13] B. Grebert, E. Paturel and L. Thomann, Modiifed scattering for the cubic Schrödinger equation on product spaces: the non resonance case, preprint,, \arXiv{1502.07699}., (). [14] M. Guardia, Growth of Sobolev norms in the cubic nonlinear Schrödinger equation with a convolution potential, Comm. Math. Phys., 329 (2014), 405-434. doi: 10.1007/s00220-014-1977-1. [15] M. Guardia, and V. Kaloshin, Growth of Sobolev norms in the cubic defocusing nonlinear Schrödinger equation, J. Eur. Math. Soc., 17 (2015), 71-149. doi: 10.4171/JEMS/499. [16] Z. Hani, B. Pausader, N. Tzvetkov and N. Visciglia, Modified scattering for the cubic Schrödinger equation on product spaces and applications, Forum of mathematics, Pi, 3 (2015), e4, 63pages. doi: 10.1017/fmp.2015.5. [17] T. Kappeler and J. Pöschel, KdV and KAM, A Series of Modern Surveys in Mathematics, Springer, 2003. doi: 10.1007/978-3-662-08054-2. [18] S. B. Kuksin, Oscillations in space-periodic nonlinear Schrodinger equations, Geom. Funct. Anal., 7 (1997), 338-363. doi: 10.1007/PL00001622. [19] V. Sohinger, Bounds on the growth of high Sobolev norms of solutions to nonlinear Schrödinger equations on $R$, Indiana Univ. Math. J., 60 (2011), 1487-1516. doi: 10.1512/iumj.2011.60.4399. [20] V. Sohinger, Bounds on the growth of high Sobolev norms of solutions to 2D Hartree equations, Discret. Contin. Dyn. Syst., 32 (2012), 3733-3771. doi: 10.3934/dcds.2012.32.3733. [21] G. Staffilani, On the growth of high sobolev norms of solutions for kdv and Schrödinger equations, Duke Math. J., 86 (1997), 109-142. doi: 10.1215/S0012-7094-97-08604-X. [22] W.-M. Wang, Long time anderson localization for the nonlinear random Schrödinger equation, J. Stat. Physics, 134 (2009), 953-968. doi: 10.1007/s10955-008-9649-1.

show all references

##### References:
 [1] D. Bambusi, Birkhoff normal form for some nonlinear PDEs, Comm. Math. Phys., 234 (2003), 253-285. doi: 10.1007/s00220-002-0774-4. [2] D. Bambusi and B. Grebert, Birkhoff normal form for PDE's with tame modulus, Duke Math. J., 135 (2006), 507-567. doi: 10.1215/S0012-7094-06-13534-2. [3] J. Bourgain, On the growth in time of higher Sobolev norms of smooth solutions of Hamiltonian PDE, Intern. Math. Res. Notices, 6 (1996), 277-304. doi: 10.1155/S1073792896000207. [4] J. Bourgain, On diffusion in High-dimensional Hamiltonian systems and PDE, J. d'analyse Math., 80 (2000), 1-34. doi: 10.1007/BF02791532. [5] J. Bourgain, Remarks on stability and diffusion in high-dimensional Hamiltonian systems and partial differential equations, Ergodic Theory Dynam. Syst., 24 (2004), 1331-1357. doi: 10.1017/S0143385703000750. [6] D. Cohen, E. Hairer and C. Lubich, Long-time analysis of nonlinearly perturbed wave equations via modulated Fourier expansions, Arch. Rational Mech. Anal., 187 (2008), 341-368. doi: 10.1007/s00205-007-0095-z. [7] J. Colliander, S. Kwon and T. Oh, A remark on normal forms and the "upside-down" I -method for periodic NLS: growth of higher Sobolev norms, J. d'analyse Math., 118 (2012), 55-82. doi: 10.1007/s11854-012-0029-z. [8] J. Colliander, M. Keel, G. Staffilani, H. Takaoka and T. Tao, Transfer of energy to high frequencies in the cubic defocusing nonlinear Schrödinger equation, Invent. Math., 181 (2010), 39-113. doi: 10.1007/s00222-010-0242-2. [9] L. H. Eliasson and S. B. Kuksin, KAM for nonlinear Schrödinger equation, Annals of Math., 172 (2010), 371-435. doi: 10.4007/annals.2010.172.371. [10] E. Faou, and B. Grebert, A Nekhoroshev type theorem for the nonlinear Schrödinger equation on the d-dimensional torus, Analysis and PDE, 6 (2013), 1243-1262. doi: 10.2140/apde.2013.6.1243. [11] B. Grebert, Birkhoff normal form and Hamiltonian PDEs, Partial Differential Equations and Applications, 1-46, Sémin. Congr., 15, Soc. Math. France, Paris, 2007. [12] B. Grebert, T. Kappeler and J. Pöschel, Normal form theory for the NLS equatons,, preprint, (). [13] B. Grebert, E. Paturel and L. Thomann, Modiifed scattering for the cubic Schrödinger equation on product spaces: the non resonance case, preprint,, \arXiv{1502.07699}., (). [14] M. Guardia, Growth of Sobolev norms in the cubic nonlinear Schrödinger equation with a convolution potential, Comm. Math. Phys., 329 (2014), 405-434. doi: 10.1007/s00220-014-1977-1. [15] M. Guardia, and V. Kaloshin, Growth of Sobolev norms in the cubic defocusing nonlinear Schrödinger equation, J. Eur. Math. Soc., 17 (2015), 71-149. doi: 10.4171/JEMS/499. [16] Z. Hani, B. Pausader, N. Tzvetkov and N. Visciglia, Modified scattering for the cubic Schrödinger equation on product spaces and applications, Forum of mathematics, Pi, 3 (2015), e4, 63pages. doi: 10.1017/fmp.2015.5. [17] T. Kappeler and J. Pöschel, KdV and KAM, A Series of Modern Surveys in Mathematics, Springer, 2003. doi: 10.1007/978-3-662-08054-2. [18] S. B. Kuksin, Oscillations in space-periodic nonlinear Schrodinger equations, Geom. Funct. Anal., 7 (1997), 338-363. doi: 10.1007/PL00001622. [19] V. Sohinger, Bounds on the growth of high Sobolev norms of solutions to nonlinear Schrödinger equations on $R$, Indiana Univ. Math. J., 60 (2011), 1487-1516. doi: 10.1512/iumj.2011.60.4399. [20] V. Sohinger, Bounds on the growth of high Sobolev norms of solutions to 2D Hartree equations, Discret. Contin. Dyn. Syst., 32 (2012), 3733-3771. doi: 10.3934/dcds.2012.32.3733. [21] G. Staffilani, On the growth of high sobolev norms of solutions for kdv and Schrödinger equations, Duke Math. J., 86 (1997), 109-142. doi: 10.1215/S0012-7094-97-08604-X. [22] W.-M. Wang, Long time anderson localization for the nonlinear random Schrödinger equation, J. Stat. Physics, 134 (2009), 953-968. doi: 10.1007/s10955-008-9649-1.
 [1] Dario Bambusi, A. Carati, A. Ponno. The nonlinear Schrödinger equation as a resonant normal form. Discrete and Continuous Dynamical Systems - B, 2002, 2 (1) : 109-128. doi: 10.3934/dcdsb.2002.2.109 [2] Jason Murphy, Fabio Pusateri. Almost global existence for cubic nonlinear Schrödinger equations in one space dimension. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 2077-2102. doi: 10.3934/dcds.2017089 [3] Jan Prüss, Gieri Simonett, Rico Zacher. On normal stability for nonlinear parabolic equations. Conference Publications, 2009, 2009 (Special) : 612-621. doi: 10.3934/proc.2009.2009.612 [4] Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete and Continuous Dynamical Systems - S, 2021, 14 (5) : 1693-1716. doi: 10.3934/dcdss.2020450 [5] Santosh Bhattarai. Stability of normalized solitary waves for three coupled nonlinear Schrödinger equations. Discrete and Continuous Dynamical Systems, 2016, 36 (4) : 1789-1811. doi: 10.3934/dcds.2016.36.1789 [6] Andrew Comech, Scipio Cuccagna. On asymptotic stability of ground states of some systems of nonlinear Schrödinger equations. Discrete and Continuous Dynamical Systems, 2021, 41 (3) : 1225-1270. doi: 10.3934/dcds.2020316 [7] Rémi Carles. Global existence results for nonlinear Schrödinger equations with quadratic potentials. Discrete and Continuous Dynamical Systems, 2005, 13 (2) : 385-398. doi: 10.3934/dcds.2005.13.385 [8] Masahoto Ohta, Grozdena Todorova. Remarks on global existence and blowup for damped nonlinear Schrödinger equations. Discrete and Continuous Dynamical Systems, 2009, 23 (4) : 1313-1325. doi: 10.3934/dcds.2009.23.1313 [9] Zaihui Gan, Boling Guo, Jian Zhang. Blowup and global existence of the nonlinear Schrödinger equations with multiple potentials. Communications on Pure and Applied Analysis, 2009, 8 (4) : 1303-1312. doi: 10.3934/cpaa.2009.8.1303 [10] Olivier Goubet, Ezzeddine Zahrouni. Global attractor for damped forced nonlinear logarithmic Schrödinger equations. Discrete and Continuous Dynamical Systems - S, 2021, 14 (8) : 2933-2946. doi: 10.3934/dcdss.2020393 [11] Todor Mitev, Georgi Popov. Gevrey normal form and effective stability of Lagrangian tori. Discrete and Continuous Dynamical Systems - S, 2010, 3 (4) : 643-666. doi: 10.3934/dcdss.2010.3.643 [12] Benjamin Dodson. Improved almost Morawetz estimates for the cubic nonlinear Schrödinger equation. Communications on Pure and Applied Analysis, 2011, 10 (1) : 127-140. doi: 10.3934/cpaa.2011.10.127 [13] Alp Eden, Elİf Kuz. Almost cubic nonlinear Schrödinger equation: Existence, uniqueness and scattering. Communications on Pure and Applied Analysis, 2009, 8 (6) : 1803-1823. doi: 10.3934/cpaa.2009.8.1803 [14] Luigi Chierchia, Gabriella Pinzari. Planetary Birkhoff normal forms. Journal of Modern Dynamics, 2011, 5 (4) : 623-664. doi: 10.3934/jmd.2011.5.623 [15] Alexander Komech, Elena Kopylova, David Stuart. On asymptotic stability of solitons in a nonlinear Schrödinger equation. Communications on Pure and Applied Analysis, 2012, 11 (3) : 1063-1079. doi: 10.3934/cpaa.2012.11.1063 [16] Changxing Miao, Bo Zhang. Global well-posedness of the Cauchy problem for nonlinear Schrödinger-type equations. Discrete and Continuous Dynamical Systems, 2007, 17 (1) : 181-200. doi: 10.3934/dcds.2007.17.181 [17] J. Colliander, Justin Holmer, Monica Visan, Xiaoyi Zhang. Global existence and scattering for rough solutions to generalized nonlinear Schrödinger equations on $R$. Communications on Pure and Applied Analysis, 2008, 7 (3) : 467-489. doi: 10.3934/cpaa.2008.7.467 [18] Tadahiro Oh. Global existence for the defocusing nonlinear Schrödinger equations with limit periodic initial data. Communications on Pure and Applied Analysis, 2015, 14 (4) : 1563-1580. doi: 10.3934/cpaa.2015.14.1563 [19] Yonggeun Cho, Gyeongha Hwang, Tohru Ozawa. Global well-posedness of critical nonlinear Schrödinger equations below $L^2$. Discrete and Continuous Dynamical Systems, 2013, 33 (4) : 1389-1405. doi: 10.3934/dcds.2013.33.1389 [20] Zaihui Gan, Jian Zhang. Blow-up, global existence and standing waves for the magnetic nonlinear Schrödinger equations. Discrete and Continuous Dynamical Systems, 2012, 32 (3) : 827-846. doi: 10.3934/dcds.2012.32.827

2020 Impact Factor: 1.916


text:
# Control Systems - State equations

I'm starting to learn about the state-space representation and i'm facing some difficulties. Suppose we have a system with connected blocks, like the one below:

where

Sometimes we want to choose variables that have physical meaning as the state equations. Suppose that these physical variables are the output of the second order block, the derivative of this output and also the output of the first order block. But by writing the time-domain equation of the transfer function of the second order block, we see that a derivative of the input will appear. Since we cant have an input derivative in a state equation, it makes me believe that I cant choose those variables, since:

If we took this block as an entire system, we couldn't do much more. But in an interconnected system, like the one above, is there a way i can relate the state equations of the other blocks so i can represent the second order block with those variables? For instance, we see that the derivative of the second order block input is equal to the derivative of the output of the first order one, since they differ by a constant, and also the output of the second order one is related with the input of the first order block. So is there a way i can represent the second block with those variables considering the interconnection?

Thank you.

It seems like the issue you're having trouble with is how to incorporate transfer function zeroes into a state space model. Once you can do that, the rest of your question might become easier.

I think the presentation in Dorf and Bishop on this matter is pretty clever. Let's take your second-order subsystem $G(s) = \frac{Y(s)}{U(s)} = \frac{s+4}{3s^2+5s+6}$ as our working example.

Inject a factor of unity into this expression and you get

$$\frac{Y(s)}{U(s)} = \frac{s+4}{3s^2+5s+6} \frac{Z(s)}{Z(s)}.$$

If all the fractions are fully reduced, we can match the numerators $$Y(s) = (s+4)Z(s)$$ and match denominators $$U(s) = (3s^2+5s+6)Z(s).$$

The inverse Laplace transforms of these equations suggest the following time-domain differential equation relationships

$$y(t) = z^\prime(t) +4z(t)$$ and $$u(t) = 3z^{\prime\prime}(t) +5z^\prime(t) +6z(t).$$

We have at most two derivatives of this weird $z(t)$ function, so let's climb the ladder when defining our state in terms of $z(t)$: $$x_1 = z \\ x_2 = z^\prime.$$

Can you deduce the A, B, C, and D matrices from here?

• Thank you for your reply, It's a clever and simple method, indeed, thank you for showing me that. But i wanted to use $$x_1=y$$ and $$x_2=y'$$ as state equations, for they are supposed to be physical quantities. I know it doesn't make any difference from a dynamics point of view, but it's more convenient to express them in terms of measurable quantities. Am I unable to do that because of that zero? – Edson Mar 30 '18 at 22:33
• as state variables* (just correcting my reply) – Edson Mar 30 '18 at 22:41
• That's right, I don't see a way to use the quantities you want as state variables (with a minimal realization). – HermitianCrustacean Mar 31 '18 at 1:40