text:
# All Questions

39 views

### Luminous Efficacy problem for LED. Semiconductor Physics [closed]

You have a white light LED with 100 lumens/W luminous efficacy when biased at 100 mA  and 0.8V.  Assume the diode has ideal characteristics and that luminous flux is linear with  diode current (a ...
31 views

### Doubt in a question about a body rolling up a ramp [closed]

I encountered a question in this year's paper of an exam, and I am in confusion. The question says: A body with mass $m$ and radius $R$ and rolling without slipping with speed $V$, moves up a ...
49 views

### Is Buoyant force a reaction?

When we fall on water. The surface molecules are pushed down and as a consequence molecules below the surface molecules and molecules beneath them and so on are also pushed down. Some of them are ...
35 views

### Sinusoidal variation of a generalised coordinate with its conjugate momentum

The hamiltonian of a system with 2 degrees of freedom is given by: H= 0.5(p12q14+p22q12-2aq1) where 'a' is a constant. I am to show that q1 varies sinusoidally with p1. My attempt was to write down ...
29 views

### Working of electric-tester [closed]

How does the circuit gets completed when we put an electric-tester glow when we put it in the +ve terminal, when actually the electrons flow from the -ve terminal ?
218 views

### On a molecular level, how does heat transfer take place?

When an ice molecule hits a water molecule, the water molecule adds kinetic energy to the ice molecule. Why do the water molecules lose kinetic energy? In other words, why does heat like to go where ...
96 views

### Why doesn't saturation photocurrent depend on frequency of incident ray, keeping intensity constant?

We know that intensity I = nhf, where n is no. of photons striking metal surface per second per unit sq unit area, and f is frequency of incident ray. In the book it was said that if we change the ...
61 views

### Light and Gravity

The gravitational force does not affect the speed of light rather affects the frequency of light (hence light changes colors, red to blue and vice-versa). I know this has been verified but I have ...
35 views

### Bose-Einstein condensate in external field at finite temperature

Suppose at some finite temperature macroscopically large number of interacting bosons condense to form Bose-Einstein condensate (BEC) with some macroscopic wave function. There also exist excitations ...
36 views

### Value of $\langle x | p \rangle$ [duplicate]

In a context of quantum mechanics, why does: $$\langle x | p \rangle = \left(\frac{1}{2\pi\hbar}\right)^{3/2} e^{ipx/\hbar}$$ Is there any proof for this?
17 views

### Motion in Spaces [duplicate]

How does a shuttle move in the space as, the whole mechanism of a rocket is based on 3rd law of newton but, we can not apply 3rd law of newton in space because there is no reactive force in space?
63 views

### Can blue light encounter slower clock time over red?

I am aware that matter with mass experiences dilation and photon is massless. there is no inertial frame where photon is at rest. However, wave form of light has momentum and energy. Blue light wave ...
67 views

### Head on collision of two black holes

LHC was built to collide two atomic particles to study contents within them. There are millions and billions of black holes present throughout galaxies. As collision between the galaxies is common in ...
81 views

48 views

### Existence of a solution for geodesic differential equations for a singular metric

In order to determine the geodesics, one must solve the following set of differential equations \begin{align} \frac{d^2 x^j}{ds^2} + {j\brace h\,\,k}\frac{dx^h}{ds}\frac{dx^k}{ds} = 0, \end{align} ...
68 views

### How the infinite electric field of an electron goes through a slit? [closed]

An electron is an indivisible particle and its electric field has to be a constant too. Going through a slit how the electric field goes through the wall and how it will be regenerated behind the ...
121 views

### Explain this contradiction of violation of “ energy conservation ” using classical mechanics

Consider a rocket moves upward with some acceleration for a very small time say '$dt$' then the kinetic energy increases (for acceleration). as well as as the potential energy increases (due to height ...


text:
# Chapter 14 - Graph Theory - 14.3 Hamilton Paths and Hamilton Circuits - Exercise Set 14.3 - Page 921: 11

(a) This graph must have Hamilton circuits because it is a complete graph. (b) The graph has 120 Hamilton circuits.

#### Work Step by Step

(a) This graph is a complete graph. Therefore, the graph must have Hamilton circuits. (b) This complete graph has 6 vertices. We know that the number of Hamilton circuits in a complete graph with $n$ vertices is $(n-1)!$. The number of Hamilton circuits in this graph is $(6-1)!$ which is $5!$. Since $5! = 120$, this graph has 120 Hamilton circuits.

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.

format: plain


text:
## A Sender-Receiver Game: Gambit’s Python API vs gtree

Here is a jupyter notebook by Valeria Burdea that creates a sender-receive game using Gambit’s Python interface. For a comparison, this tutorial shows how one can create and analyse the same game in a relatively simple fashion using gtree.

I just copy the game description from the Jupyter notebook:

“This is a 2-player sequential game the structure of which is inspired by Glazer and Rubinstein (2004, 2006). In the first stage, the sender is dealt 2 cards - one card orange, one card blue. Each card can take a value between 1 and 9; each combination of values is equally likely. A hand is good if the sum of the two cards is at least 9; a hand is bad otherwise. Upon observing the two cards, the sender chooses one to reveal to the receiver. The receiver observes the revealed card and chooses an action between ‘Accept’ and ‘Reject’. The incentives are such that the sender would always want the receiver to accept, while the receiver would only want to accept if the hand is good and reject otherwise.”

Here is the implementation of the game using gtree (the exact payoffs were taken from the Python code):

library(gtree)
game = new_game(
params = list(numPlayers=2, maxVal=9),
options = make_game_options(verbose=FALSE),
stages = list(
stage("DrawStage",
nature = list(
natureMove("orange", ~1:maxVal),
natureMove("blue", ~1:maxVal)
)
),
stage("RevealStage",
player=1,
observe = c("orange","blue"),
actions = list(
action("reveal",c("orange","blue"))
)
),
stage("AcceptStage",
player=2,
compute = list(
shownVal ~ ifelse(reveal=="orange", orange, blue)
),
observe = c("shownVal"),
actions = list(
action("accept",c(TRUE, FALSE))
)
),
stage("PayoffStage",
player=1:2,
compute=list(
payoff_1 ~ ifelse(accept, 1,0), # Sender wants accept
payoff_2 ~ case_distinction(
accept & hand=="good", 1,
!accept & hand=="good",0,
)
)
)
)
)

I would argue that gtree’s game definition using stages follows in a straightforward and simple fashion the verbal game description.

Gambit’s Python API is instead designed to directly specify game trees. For comparison, take a look here.

## Huge number of strategy profiles

Shall we try to compute all pure SPE?

game %>% game_solve()
## Error in compute.tg.fields.for.internal.solver(tg, verbose = verbose): Even using subgames there are 1.23794003928538e+27 relevant strategy profile.
## Yet as an upper bound the internal gtree solver only attempts to fully compile and solve the game
## if there are fewer than 1e+06 relevant strategy profiles.
##  You can change this bound e.g. to 2 Mio by calling
##
## options(gtree.max.sp = 2000000)
##
## Some Gambit solvers, like gambit-logit, use algorithms that can still find one equilibrium
## in reasonable time for certain but not all games with a very large number of strategy profiles.
## So try out game_gambit_solve with a fitting Gambit command line tool (see Gambit documention).

Ups… looks like the game is too large to be solved. Here is some additional size information.

# Get some size information about the game
game %>%
game_print_size_info()
##
##
## Size Information:
##   - 324 possible outcomes
##   - 90 information sets (81 + 9)
##   - 1.23794e+27 pure strategy profiles (2.41785163922926e+24 * 512)
##   - 1 subgames
##   - 1.23794e+27 relevant pure strategy profiles in subgames

The game has a gigantic number of strategy profiles.

## Only one subgame???

Interestingly, the game also has only 1 subgame, even though player 1 perfectly observes the values of the orange and blue card. For an illustration, why there is only one subgame, we export a smaller version of the game in which cards only take values of 1 or 2 to a Gambit efg file.

game %>%
game_change_param(maxVal = 2) %>%
game_write_efg("sender_receiver.efg")

I have manually opened the efg file with Gambit and exported the following game tree as an svg graphic:

Recall the definition of a subgame, e.g. from Wikipedia:

1. It has a single initial node that is the only member of that node’s information set (i.e. the initial node is in a singleton information set).
2. If a node is contained in the subgame then so are all of its successors.
3. If a node in a particular information set is in the subgame then all members of that information set belong to the subgame.

Even though the moves of player 1 start at singleton information sets (Condition 1), candidate subgames starting at these nodes violate Condition 3.

## Find a mixed strategy equilibrium using the gambit-logit solver from gtree

If we cannot reduce the number of relevant strategy profiles by subgames, our internal gtree solver cannot practically solve games with so many strategy profiles. However, Gambit has solvers that can find at least one equilibrium of this game. Here we let gambit-logit solver do its magic.

To make the vignette build quicker I reduce the size of the game, but you can change maxVal to 9. (Takes then around 2 minutes to solve on my notebook).

game %>%
game_change_param(maxVal = 4) %>%
game_print_size_info() %>%
game_gambit_solve("gambit-logit -q -e")
##
##
## Size Information:
##   - 64 possible outcomes
##   - 20 information sets (16 + 4)
##   - 1 048 576 pure strategy profiles (65536 * 16)
##   - 1 subgames
##   - 1 048 576 relevant pure strategy profiles in subgames
game %>%  eq_tables()
## $reveal ## # A tibble: 24 x 5 ## # Groups: orange, blue, reveal [24] ## orange blue reveal .prob eq.inds ## <int> <int> <chr> <dbl> <chr> ## 1 1 1 blue 0.5 1 ## 2 1 1 orange 0.5 1 ## 3 1 2 blue 0.500 1 ## 4 1 2 orange 0.500 1 ## 5 1 3 blue 1 1 ## 6 1 4 blue 1 1 ## 7 2 1 blue 0.500 1 ## 8 2 1 orange 0.500 1 ## 9 2 2 blue 0.5 1 ## 10 2 2 orange 0.5 1 ## # ... with 14 more rows ## ##$accept
## # A tibble: 4 x 4
## # Groups:   shownVal, accept [4]
##   shownVal accept .prob eq.inds
##      <int> <lgl>  <dbl> <chr>
## 1        1 FALSE      1 1
## 2        2 FALSE      1 1
## 3        3 TRUE       1 1
## 4        4 TRUE       1 1

The results seem intutive: Player 2 only accepts if and only if the shown card is at least a 6. Player 1 always shows a card that is at least 6 if he has one.

## Find a quantal response equilibrium

You may first take a look at the Wikipedia page for quantal response equilibria. The following code uses the gambit-logit solver to compute a logit agent quantal response equilibrium using the parameter lambda=3.

game %>%
game_change_param(maxVal = 4) %>%
game_print_size_info() %>%
game_gambit_solve("gambit-logit -q -e -m 3") %>%
eq_tables()
##
##
## Size Information:
##   - 64 possible outcomes
##   - 20 information sets (16 + 4)
##   - 1 048 576 pure strategy profiles (65536 * 16)
##   - 1 subgames
##   - 1 048 576 relevant pure strategy profiles in subgames
## $reveal ## # A tibble: 32 x 5 ## # Groups: orange, blue, reveal [32] ## orange blue reveal .prob eq.inds ## <int> <int> <chr> <dbl> <chr> ## 1 1 1 blue 0.5 1 ## 2 1 1 orange 0.5 1 ## 3 1 2 blue 0.801 1 ## 4 1 2 orange 0.199 1 ## 5 1 3 blue 0.928 1 ## 6 1 3 orange 0.0722 1 ## 7 1 4 blue 0.928 1 ## 8 1 4 orange 0.0722 1 ## 9 2 1 blue 0.199 1 ## 10 2 1 orange 0.801 1 ## # ... with 22 more rows ## ##$accept
## # A tibble: 8 x 4
## # Groups:   shownVal, accept [8]
##   shownVal accept  .prob eq.inds
##      <int> <lgl>   <dbl> <chr>
## 1        1 FALSE  0.881  1
## 2        1 TRUE   0.119  1
## 3        2 FALSE  0.425  1
## 4        2 TRUE   0.575  1
## 5        3 FALSE  0.0451 1
## 6        3 TRUE   0.955  1
## 7        4 FALSE  0.0451 1
## 8        4 TRUE   0.955  1

The python code called gambit-logit without the option -e. It then returns a table of (approximated) equilibria for many values of lambda up to the maximum specified by the option -m. I have currently not implemented a feature in gtree to automatically parse that whole table. But if there is interest, just let me know, via Github issue or email.


text:
Accelerating the pace of engineering and science

# Documentation

### Contents

Bit error rate (BER) for Rayleigh and Rician fading channels

## Alternatives

As an alternative to the berfading function, invoke the BERTool GUI (bertool), and use the Theoretical tab.

## Description

### For All Syntaxes

The first input argument, EbNo, is the ratio of bit energy to noise power spectral density, in dB. If EbNo is a vector, the output ber is a vector of the same size, whose elements correspond to the different Eb/N0 levels.

Most syntaxes also have an M input that specifies the alphabet size for the modulation. M must have the form 2k for some positive integer k.

berfading uses expressions that assume Gray coding. If you use binary coding, the results may differ.

For cases where diversity is used, the Eb/N0 on each diversity branch is EbNo/divorder, where divorder is the diversity order (the number of diversity branches) and is a positive integer.

### For Specific Syntaxes

ber = berfading(EbNo,'pam',M,divorder) returns the BER for PAM over an uncoded Rayleigh fading channel with coherent demodulation.

ber = berfading(EbNo,'qam',M,divorder) returns the BER for QAM over an uncoded Rayleigh fading channel with coherent demodulation. The alphabet size, M, must be at least 4. When $k={\mathrm{log}}_{2}M$ is odd, a rectangular constellation of size $M=I×J$ is used, where $I={2}^{\frac{k-1}{2}}$ and $J={2}^{\frac{k+1}{2}}$.

ber = berfading(EbNo,'psk',M,divorder) returns the BER for coherently detected PSK over an uncoded Rayleigh fading channel.

ber = berfading(EbNo,'depsk',M,divorder) returns the BER for coherently detected PSK with differential data encoding over an uncoded Rayleigh fading channel. Only M = 2 is currently supported.

ber = berfading(EbNo,'oqpsk',divorder) returns the BER of coherently detected offset-QPSK over an uncoded Rayleigh fading channel.

ber = berfading(EbNo,'dpsk',M,divorder) returns the BER for DPSK over an uncoded Rayleigh fading channel. For DPSK, it is assumed that the fading is slow enough that two consecutive symbols are affected by the same fading coefficient.

ber = berfading(EbNo,'fsk',M,divorder,coherence) returns the BER for orthogonal FSK over an uncoded Rayleigh fading channel. coherence should be 'coherent' for coherent detection, or 'noncoherent' for noncoherent detection.

ber = berfading(EbNo,'fsk',2,divorder,coherence,rho) returns the BER for binary nonorthogonal FSK over an uncoded Rayleigh fading channel. rho is the complex correlation coefficient. See Nonorthogonal 2-FSK with Coherent Detection for the definition of the complex correlation coefficient and how to compute it for nonorthogonal BFSK.

ber = berfading(EbNo,...,K) returns the BER over an uncoded Rician fading channel, where K is the ratio of specular to diffuse energy in linear scale. For the case of 'fsk', rho must be specified before K.

ber = berfading(EbNo,'psk',2,1,K,phaserr) returns the BER of BPSK over an uncoded Rician fading channel with imperfect phase synchronization. phaserr is the standard deviation of the reference carrier phase error in radians.

[BER,SER] = berfading(EbNo, ...) returns both the BER and SER.

## Examples

The following example computes and plots the BER for uncoded DQPSK (differential quaternary phase shift keying) modulation over a flat Rayleigh fading channel for several diversity order values.

```EbNo = 8:2:20;
M = 16; % Use 16 QAM
semilogy(EbNo,ber);
text(18.5, 0.02, sprintf('L=%d', L))
hold on
% Loop over diversity order, L, 2 to 20
for L=2:20
semilogy(EbNo,ber);
end
text(18.5, 1e-11, sprintf('L=%d', L))
title('QAM over fading channel with diversity order 1 to 20')
xlabel('E_b/N_o (dB)')
ylabel('BER')
grid on```

## Limitations

The numerical accuracy of this function's output is limited by approximations related to the numerical implementation of the expressions

You can generally rely on the first couple of significant digits of the function's output.

## References

[1] Proakis, John G., Digital Communications, 4th ed., New York, McGraw-Hill, 2001.

[2] Modestino, James W., and Mui, Shou Y., Convolutional code performance in the Rician fading channel, IEEE Trans. Commun., 1976.

[3] Cho, K., and Yoon, D., "On the general BER expression of one- and two-dimensional amplitude modulations", IEEE Trans. Commun., Vol. 50, Number 7, pp. 1074-1080, 2002.

[4] Lee, P. J., "Computation of the bit error rate of coherent M-ary PSK with Gray code bit mapping", IEEE Trans. Commun., Vol. COM-34, Number 5, pp. 488-491, 1986.

[5] Lindsey, W. C., "Error probabilities for Rician fading multichannel reception of binary and N-ary signals", IEEE Trans. Inform. Theory, Vol. IT-10, pp. 339-350, 1964.

[6] Simon, M. K , Hinedi, S. M., and Lindsey, W. C., Digital Communication Techniques – Signal Design and Detection, Prentice-Hall, 1995.

[7] Simon, M. K., and Alouini, M. S., Digital Communication over Fading Channels – A Unified Approach to Performance Analysis, 1st ed., Wiley, 2000.

[8] Simon, M. K , "On the bit-error probability of differentially encoded QPSK and offset QPSK in the presence of carrier synchronization", IEEE Trans. Commun., Vol. 54, pp. 806-812, 2006.


text:
# Percolation: Slipping through the Cracks

The existence of a critical probability makes percolation a mathematically interesting and rich subject. ...

David Austin
Grand Valley State University
david at merganser.math.gvsu.edu

### Introduction

My backyard has an area where the soil is mainly clay and another where it's mainly sand. The day after a hard rain, the sandy region is usually dry while the clay region is still damp. The process by which water moves through a medium, like sand or clay, is called percolation and is currently the focus of significant mathematical activity, some of which we'll describe in this article.

Geoffrey Grimmett begins his book Percolation with the question: "Suppose we immerse a large porous stone in a bucket of water. What is the probability that the centre of the stone is wetted?" To begin creating a mathematical model, we will imagine a two-dimensional lattice of channels running through the rock (a more realistic three-dimensional model can wait).

This is known as the square lattice, and we will denote it by Z2. We choose a parameter p between 0 and 1 and declare that each edge is open with probability p. Think of an open edge as a channel that is large enough to conduct water through it. Here are examples for two different values of p.

 p = 0.3 p = 0.6

If we imagine that the size of the channels is much smaller than the size of the rock, it is reasonable to assume that the lattice is infinite in extent. To rephrase Grimmett's question, we may ask, "What is the probability that there is a path of open edges from the origin that travels infinitely far?

We can easily make two statements. When p = 0, every edge is closed so there will be no infinite open path containing the origin. However, when p = 1, every edge will be open so there must be an infinite open path.

What happens for intermediate values of p? For small p, there will be few open channels so any open paths will most likely be short. However, as p increases, there are more open channels, and eventually it is likely that there is an infinite open path starting at the origin. If there is a positive probability of having such an infinite path, we say that percolation occurs. We will see that there is a critical probability, that we denote pc, representing a threshold; percolation occurs above pc but not below. A result due to Harris and Kesten, which we'll outline later, states that the critical probability for the square lattice is pc = 1/2.

The existence of a critical probability makes percolation a mathematically interesting and rich subject. On either side of the critical probability, the system behaves in fundamentally different ways (as water drains easily through sandy soil but not through clay). As such, it serves as a model for more complex systems that experience a phase transition when some parameter, such as temperature, passes through a critical value. Percolation provides a model that is simple enough to be mathematically accessible while still displaying many of the features of more complex systems.

### A simple example

Let's begin with a simple example that illustrates some general principles. We will study percolation on the infinite binary tree, a portion of which is shown below.

If p is the probability that each edge is open, we want to find θ(p), the probability that there is an infinite open path containing the root of the tree v0. We begin by letting Pn be the probability that there is an open path from v0 to a vertex n levels below. Notice that we have P0 = 1. Shown in red below is a path from v0 to a vertex three levels below.

This path moves through another vertex v1. The probability that an open path from v0 to a vertex n levels below passes through v1 is pPn-1, the probability p that the edge from v0 to v1 is open times the probability Pn-1 that a path from v1 to a vertex n - 1 levels below it is open. Therefore, the probability that there is no open path from v0 to a vertex n levels below passing through v1 is 1 - pPn-1.

Since any path from v0 to a vertex n levels below must pass through one of the children of v0, we find that the probability that there is not an open path from v0 to a vertex n levels below is

and therefore

If we define the function fp(x) = 1 - (1 - px)2, we have Pn = fp(Pn-1). The graph of fp is shown below in two different cases, depending on the derivative fp'(0) = 2p.

 fp'(0) = 2p > 1 fp'(0) = 2p < 1

In the first case, 2p > 1 , we see that there is a fixed point

and if 2p < 1, the only fixed point is x0 = 0.

From the graph, we see that if 2p > 1 and x > x0, then x0 < fp(x) < x. Since P0 = 1, we have

 and and so on.

It then follows that

if p > 1/2. The graph of θ(p) is therefore shown below:

Here we see that the critical probability, pc = 1/2; above pc, θ(p) > 0 and we have percolation. Below the critical probability, θ(p) = 0 and there is no percolation.

This example is unusual in that it is difficult to compute the critical probability and θ(p) exactly for most combinatorial graphs. As we'll see toward the end of this article, however, it is thought that the specific form that θ(p) takes here shares features with that from other graphs.

### Percolation on the square lattice

Percolation theory was introduced to mathematicians by Broadbent and Hammersley in 1957. For two decades, work in this new field concentrated mainly on finding critical probabilities. For instance, Broadbent and Hammersley showed that the critical probability for the square lattice Z2, shown below, is between 1/3 and 2/3.

On the basis of Monte Carlo simulations, Hammersley later suggested that this probability should be 1/2. Indeed, through work of Harris and later Kesten, it was eventually proven that pc = 1/2. We will outline the proof of this theorem later. For now, let's develop a feel for how configurations behave for various values of p.

Here is one configuration of open edges that results when p = 0.4.

Given a configuration of open edges and a vertex v in the lattice, the cluster Cv will denote the collection of vertices connected to v by open edges.

Below we show a configuration when p = 0.3 and C0, the cluster containing the origin, in blue.

Remember that θ(p) is the probability that there is an infinite path containing the origin, which is the same event as the cluster C0 being infinite. Here's what happens as we increase p.

 p = 0.2 p = 0.3 p = 0.4 p = 0.45 p = 0.5 p = 0.55 p = 0.6 p = 0.8

Based on these examples, two things can be observed. First, if we look at a fixed value of p, we see that the size of the clusters is relatively small for small values of p. A theorem of Menshikov allows us to state this quantitatively.

If E is some event, we will use Pp(E) to denote the probability that E holds when the edges are open with probability p. By Sx,n, we will denote the event that there is an open path from a vertex x to another vertex whose distance from x, measured in the lattice, is n. (We measure distances in the lattice as the number of edges in the shortest possible path between the two vertices.) Though proven in considerably more generality, Menshikov's theorem roughly says that

 For a given p < pc, there is a constant a such that P(Sx,n) ≤ e-an.

This means that the probability of having an open path decreases exponentially as the distance traveled by the path increases.

### The Harris-Kesten Theorem

For our second observation, imagine increasing p as we consider the size of the cluster C0. It is relatively small for small values of p, but around p = 0.45, its size begins to grow significantly. This leads us to suspect that the critical probability pc, the probability that marks the transition from θ(p) = 0 to θ(p) > 0 occurs around 1/2.

In fact, one of the first significant results in percolation theory is the Harris-Kesten Theorem

 For the square lattice, pc = 1/2.

In what follows, we will outline a proof of this theorem, which divides naturally into two parts. The first half, originally proven by Harris in 1960, states that θ(1/2) = 0. In particular, this implies that pc ≥ 1/2. The second half, proven later by Kesten in 1982, says that pc ≤ 1/2. The result that pc = 1/2 naturally follows.

We'll begin outlining an argument for Harris' theorem by considering the dual of the square lattice. This graph is formed from the square lattice by placing one vertex in the center of each square and joining vertices with an edge when their corresponding squares in the square lattice share an edge.

Notice that if we are given an edge in the lattice, there is exactly one edge crossing it in the dual. Also, the dual lattice is a copy of the square lattice translated so that the vertices are in the centers of the squares. For this reason, we say the square lattice is self-dual.

Suppose we are given a configuration of open edges in the square lattice. We will consider an edge in the dual lattice to be open exactly when the edge it crosses in the square lattice is closed. Shown below in red is a configuration for the square lattice and, in blue, the corresponding configuration in the dual lattice.

In this way, requiring that the edges in the square lattice are open with probability p is the same as requiring that edges in the dual lattice are open with probability 1 - p.

Now consider C0, the cluster in the square lattice containing the origin. If p < pc, then this cluster is almost surely finite. As the figure below shows, this means that there is almost surely an open cycle in the dual lattice containing the origin in its interior (shown in green).

To summarize, we see that θ(p) = 0 for those values of p for which there is almost surely an open cycle in the dual lattice containing the origin in its interior. We will therefore assume that p = 1/2 and show that there is almost surely an open cycle in the dual lattice containing the origin in its interior. From this it follows that θ(1/2) = 0 and hence pc ≥ 1/2.

To do this, we will find the probability that there is an open cycle in the dual lattice contained in an annulus and composed of four separate open paths as shown below.

Breaking the problem down even further, we will look at one of the four sides of this rectangular annulus, a rectangle whose dimensions are 3n by n, and find the probability that there is an open path running horizontally across this rectangle. We begin, however, by studying a square.

Here is a fundamental observation: Suppose we consider R, a rectangular portion of the square lattice with k by l vertices. We may also consider R', a k - 1 by l + 1 rectangular portion of the dual lattice:

 We will show that there is either an open path moving horizontally across R or there is an open vertical path in R'. To see this, imagine constructing the figure on the right: there is a hexagon on each vertex in R and R'. Hexagons corresponding to vertices in R are shaded. The squares between hexagons correspond to edges, and these are shaded if the corresponding edge is open in R (and hence closed in R'). White squares therefore correspond to open edges in R'. Since we are interested in horizontal open paths in R, we consider all the edges on the left and right sides to be open. Similarly, we consider all edges at the top and bottom to be open in R'. Imagine that we start at the corner A and walk on the border between the white and gray regions. This path may only end at B or C since the gray region is always on our right. If we end at B, we have a horizontal open path across R, and if we end at C, we have a vertical open path across R'.

Recall that Pp(H(R)) denotes the probability that there is a horizontal open path across R when edges are open with probability p. In the same way, P1-p(V(R')) is the probability that there is an open vertical path across R'.

Since there is either a horizontal open path across R or an open vertical path across R', we must have

 and so

If we consider the case that R is an n + 1 by n rectangle, then R' is an n by n + 1 rectangle. We then have P1/2(H(R)) = P1/2(V(R')) = 1/2. If instead we take R to be an n by n square S, a horizontal path has a shorter distance to travel so we have

Notice that this is independent of n, the size of the square.

Now that we understand the probability of having an open path across a square, we would like to use this understanding to study more general rectangles. Remember that we would eventually like to understand rectangles of dimension 3n by n. The following technique is due to Russo, Seymour and Welsh.

Consider the figure to the left, in which we have two squares of sides n and 2n. Consider the event F1 described by a configuration of open paths, like the blue and red ones shown below. We know that the probability of an open vertical path in the smaller square is greater than 1/2. In the same way, the probability of having a horizontal path, like the red one, open is greater than 1/2 as well. The fact that we want the red path to enter the smaller square introduces another factor of 1/2:

Now let F2 be the event that there is an open path across a 3n by 2n rectangle. We break this into smaller pieces by considering the rectangle to consist of two squares of dimension 2n by 2n overlapping in an n by 2n rectangle. Applying our previous result, we have

Continuing in this way, we may continue to understand wider rectangles by breaking them into smaller rectangles that overlap in a square. For instance, the figure to the right illustrates an argument showing that the probability there is an open path across a 2n by n rectangle is greater than 2-15.

With some additional work, we see that the probability that there is an open horizontal path across a 3n by n rectangle is greater than 2-25.

Remember that we are interested in finding an open cycle around the annulus shown below. Decomposing the annulus into four rectangles whose dimensions are 3n by n, we see that the probability of having an open cycle in the annulus is greater than (2-25)4 = 2-100. That's a pretty small number, but it's enough to do the trick. Again, the important point is that this number does not depend on the size of the annulus.

We now imagine ringing the origin with a set of concentric annuli as shown.

We now know that the probability there is no open cycle in an annulus is smaller than 1 - 2-100. Therefore, if we look at k concentric annuli, the probability that there is an open cycle encircling the origin is smaller than (1 - 2-100)k. Since 1 - 2-100 < 1, we see, by allowing k to become arbitrarily large, that the probability that there is no open cycle encircling the origin is smaller than any positive number and hence zero. Therefore, there is almost surely an open cycle encircling the origin, which means that C0 is almost surely finite and hence θ(1/2) = 0 and pc ≥ 1/2. This completes the proof of Harris' Theorem.

To complete the proof of the Harris-Kesten theorem, we also need to prove Kesten's theorem, which says that pc ≤ 1/2. We will do this by assuming that pc > 1/2 and arriving at a contradiction. The argument sketched here is not Kesten's original proof.

If we assume that pc > 1/2, then p = 1/2 is below the critical probability. Recalling Menshikov's theorem, which we stated earlier, we then have

 P1/2(Sx,n) ≤ e-an, for some constant a,

where Sx,n is the event that an open path runs from x to a vertex whose distance from x is n.

Consider an n by n square S. Since there are n vertices on the left side of the square and any horizontal path has length at least n - 1, we have

By choosing n to be very large, we can make the term n e-an as small as we like. For instance, we may choose n to be so large that n e-an < 1/4. The inequality above then says that P1/2(H(S)) < 1/4. However, this contradicts the fact that P1/2(H(S)) ≥ 1/2. Therefore, our assumption that 1/2 < pc must be incorrect, which completes the proof of Kesten's theorem.

### Some other results

The early days of mathematical work in percolation focused on finding critical probabilities for various combinatorial graphs. After a considerable amount of effort, relatively little is known. Here is a summary.

The scenario we have presented, where edges are declared to be open or closed, is usually known as bond percolation. Alternatively, we may also consider site percolation, in which the vertices of the graph are declared to be open with probability p. We then study paths in which every vertex visited is open.

Shown below, for instance, are the vertices in the triangular lattice T and a configuration of open vertices with p = 0.3.

 We may consider replacing the vertices by hexagonal tiles, coloring the open ones, and asking if there is an infinite connected set of colored tiles. In 1982, Kesten proved that pc = 1/2 for site percolation on the triangular lattice. For bond percolation on the triangular lattice, Wierman showed in 1981 that pc = 2 sin(π/18) ≈ 0.347. It should not be surprising that this critical probability for bond percolation is lower than that for the square lattice since each vertex in the triangular lattice has six edges compared to four in the square lattice. Since the triangular lattice T is dual to the hexagonal lattice H, it is not surprising that the critical probability for bond percolation on H is pc = 1 - 2 sin(π/18).

Aside from these results and those for regular graphs, which are similar to the binary tree we looked at earlier, very little is known about the exact values of critical probabilities for other graphs.

### Conformal Invariance

As mentioned before, early work in percolation theory concentrated on finding critical probabilities. Recently, however, theoretical physics has raised interesting questions in some different directions.

It should be clear that the critical probability depends on geometric properties of the graph. However, there is evidence that certain percolation probabilities remain unchanged under "conformal maps."

A conformal map of the plane is a function from one region in the plane to another that may distort distances but must preserve angles. Examples are provided by complex analytic functions such as f(z) = ez. Motivated by theoretical physics and numerical experiments, Aizenman and Langlands, Pouliot and Saint-Aubin conjectured that certain "crossing probabilities" were unchanged after the application of a conformal map, as we'll now explain.

To begin, we will consider a region D in the plane with four marked points P1, P2, P3, and P4. These points divide the boundary of D into four arcs A1, A2, A3, and A4. We will call this data a 4-marked region and denote it by D4.

If L is some lattice in the plane, we may consider the portion inside D and a configuration in which either sites or bonds are open with probability p.

By P(D4,L, p), we mean the probability that there is an open crossing from arc A1 to A3 contained inside D. The example P(H(R)) that we considered earlier is a special case of this construction.

Finally, imagine that the lattice L is scaled by a parameter δ to obtain δL. Here are some examples:

 δ = 0.5 δ = 0.25

Consider what happens as δ → 0. Since the distance between the two arcs in δL grows arbitarily large and, if p < pc, Menshikov's theorem says that the size of the clusters decays exponentially, we must have P(D4, δL, p) → 0 if p < pc.

Conversely, if p > pc, we are guaranteed to have an infinite cluster, and it follows that P(D4, δL, p) → 1.

The interesting question is what happens if p = pc.

 Conjecture (Aizenman and Langland, Pouliot, Saint-Aubin): For any "reasonable" lattice L, the limiting probability   exists, lies in the open interval (0, 1) and is independent of the lattice L. Moreover, if D4' is the result of applying a conformal map to D4, then P(D4) = P(D4').

This is a remarkable conjecture for it says that the limiting probability does not depend on the lattice and is unchanged when the region is changed by a conformal map. In fact, Cardy, motivated by ideas from conformal field theory, proposed an exact formula for the limiting probability.

To understand Cardy's formula, we note that conformal maps provides a great deal of versatility. For instance, any two regions D3 with three marked points are related to one another by a conformal map, a fact that follows from the Riemann mapping theorem. If we consider a 4-marked region D4 and momentarily forget about the fourth point P4, there is then a conformal map carrying the region D and the three marked points P1, P2, and P3 into the equilateral triangle D' with vertices P'1 = (1, 0), P'2 = (1/2, /2), and P'3 = (0, 0). Now the fourth point P4 corresponds to a point P'4 = (x, 0) as shown below.

Assuming that conformal invariance holds, Cardy's remarkable formula, interpreted in this way, says that P(D4) = x. As yet, conformal invariance and Cardy's formula have only been rigorously proven for the case of site percolation on the triangular lattice T, a result due to Smirnov in 2001. However, there is considerable evidence to suggest that they hold in wide generality.

### Power laws and universality

Theoretical physics also predicts that a number of properties depend, not on the geometric properties of the graph, but only on its dimension. For instance, we know that the critical probability for site percolation on the triangular lattice is 1/2. This says that θ(p) = 0 for p < 1/2. If, however, we ask how θ(p) behaves for values of p above 1/2, physics indicates that the following should hold:

 θ(p) ≈ (p - 1/2)5/36 for values of p just above 1/2.

We call such an expression a power law. Besides demonstrating the relatively simple behavior of θ(p) in the case of site percolation on the triangular lattice, the conjecture further says that the exponent 5/36 should describe θ(p) for percolation on any planar lattice near its critical probability pc. That is, θ(p) ≈ (p - pc)5/36 for any planar lattice. This is an indication of universality, the hypothesis, based on physical reasoning, that there are critical exponents, such as 5/36, that depend only on the dimension and not on the details of the particular lattice.

In fact, it has been mathematically verified, by Lawler, Schramm, and Werner, that, for site percolation on the triangular lattice, θ(p) has this form. At present, however, we are not able to say that this result holds more generally.

Other, similar results hold as well. If we consider χ(p), the average number of vertices in C0 when p < pc, physics tells us that it should be true that

 χ(p) ≈ (pc - p)-43/18.

Also, suppose that p = pc and consider P(n ≤ |C0| < ∞), the probability that the cluster containing the origin contains a finite number of vertices greater than or equal to n. Physics again predicts that

 P(n ≤ |C0| < ∞) ≈ n-5/91.

Both of these power laws have been proven for site percolation on the triangular lattice by the work of Kesten, Lawler, Schramm, Smirnov, and Werner.

At this time, it appears that theoretical physics, more specifically, conformal field theory and quantum gravity, have a great deal to say about percolation. One of the challenges before mathematicians is to create a mathematically rigorous theory to support these physical insights by, in particular, verifying conformal invariance for percolation on two-dimensional lattices and the universality of power laws.

Mathematics has traditionally been tightly connected to physics. It is interesting to see that the link between these two disciplines is still so vital. The mathematical importance of this field is demonstrated by the fact that Wendelin Werner was awarded mathematics' highest honor, the Fields Prize, in part for his work in percolation.

### References

• Béla Bollobás, Oliver Riordan, Percolation, Cambridge University Press. 2006
• Geoffrey Grimmett, Percolation, Second Edition. Springer. 1999
The above are two excellent references from which I have borrowed heavily.
• Harry Kesten, What is ... Percolation?, Notices of the American Mathematical Society, 53 (5), May 2006. 572-573.
• S.R. Broadbent, J.M. Hammersley, Percolation processes. I. Crystals and mazes. Proceedings of the Cambridge Philosophical Society 53, 1957. 629-641.
• T.E. Harris, A lower bound for the critical probability in a certain percolation process. Proceedings of the Cambridge Philosophical Society, 56, 1960. 13-20.
• H. Kesten, The critical probability of bond percolation on the square lattice equals 1/2. Communications in Mathematical Physics, 74, 1980. 41-59.
• R.P. Langlands, P. Pouliot, Y. Saint-Aubin, Conformal invariance in two-dimensional percolation, Bulletin of the American Mathematical Society, 30, 1994. 1-61.
• S. Smirnov, W. Werner, Critical exponents for two-dimensional percolation, Mathematics Research Letters, 8, 2001. 729-744.
• Fields Medal Citation for Wendelin Werner

David Austin
Grand Valley State University
david at merganser.math.gvsu.edu

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services.

Welcome to the
Feature Column!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.


text:
# Pi is a perfect square!

Explaining math is hard, but when 'squaring the circle' came up in class, I could not resist to explain the connection between circles and squares.

I started easy by introducing Pythagoras' theorem

Then I introduced pi as the is the ratio of a circle's circumference to its diameter, and continued with explaining more geometry, esp. $$sin^2+cos^2 = 1$$;

Having established the connection, I could see the class was already very confused by this 'useless' information, so I continued quickly with

"Pi is a perfect square!"

Now I completely lost my class, who thought they knew better.
One said: "Pi is not a perfect square, e.g. Four is."
After this it was clear that even the brightest of my students did not get it. After all, four clearly is not a square.

So I switched to some number theory

"An integer number is 9142057518"
"Yes", said the class.
"A real number is 2571.72"
"Yes" said the class.
"A version number is 2.3.5569.6739151"
The class looked confused but agreed.
"An odd number is 4.193.2"
One started smiling. I thought she finally understood it, but then she said jokingly: "That is an odd number!"
"Of course not! That is an even number", I said.

As last one I mentioned:
"An imaginary number is 3300647498274i/300"

No matter how hard I tried to explain it; they did not understand it.

Can you explain the class why 3300647498274i/300 is imaginary? (and remove any remaining confusion)

A minor hint for if you still want to solve this, but avoid the big spoiler when reading the answer:

Apply Pythagoras on the bottom picture - why is it correct?
or
Look at the statement about integers, this exact integer is chosen for a reason.

• Pi is a square of what? geometrically or 3.14 algebraically? So what's the square root of PI?1.77... Sep 16 at 6:39
• @LifeInTheTrees I find it hard to say something useful without spoiling the puzzle. I added some hints that hopefully do not confuse you even more. Sep 16 at 7:15

Your students should probably brush up on their

A1Z26/alphanumeric substitution knowledge. Under this substitution, the letter A becomes the number 1, B becomes 2, and so on until Z, which becomes 26. For example, the word NUMBER under the A1Z26 substitution is 1421132518 - the N becomes 14, the U becomes 21, etc.

So let's clear things up, shall we?

Why is pi a perfect square?

Because under A1Z26, PI becomes 169, which is 13 squared. The diagram is correct because according to the modified Pythagorean Theorem, 42 + 32 = 16 + 9 = P + I (under A1Z26) = PI (concatenation) = 169 = 132 (thanks @T. Dirks for spotting that!).

Why is four not a perfect square?

Because FOUR is 6142118, whose square root is not an integer as can be checked on a standard calculator.

What's going on with the number theory?

Each number encodes the word before "number" with an additional twist: a decimal point in the numbers represents the act of multiplying. Hence, we have

INTEGER <--> 9142057518
REAL <--> 185112 = 2571 × 72
VERSION <--> 225181991514 = 2 × 3 × 5569 × 6739151
ODD <--> 1544 = 4 × 193 × 2

"That is an even number" - why?

Because the last digit of the A1Z26 encoding of THAT is 0, so it is an even number (the mathematical kind), not odd.

Why is that weird expression an imaginary number?

This one requires putting everything we've learned together. First, convert the i into the digit 9 to get the expression 33006474982749/300. Evaluate it to get 110021583275.83. Finally, treat the decimal point as a multiplication sign and evaluate to get 9131791411825, which is IMAGINARY encoded in A1Z26. Phew!

• I'm not sure what.. You have to apply Pythagoras and then it should be clear. Sep 16 at 6:10
• I believe for the Pythagoras part rot13(vs jr svyy va 4 sbe n naq 3 sbe o va n²+o²=p² jr trg 16+9=p². Pbairegvat gurfr gb yrggref lbh trg C+V=p² fb gur fdhnerq qvntbany rdhnyf CV) Sep 16 at 9:44
• @T.Dirks ohh how in the world did I miss that? Thanks, the answer should be complete now!
– HTM
Sep 16 at 17:38


text:
# Haskell FFT 4: A Simple Application

Before we go on to look at how to deal with arbitrary input vector lengths (i.e. not just powers of two), let’s try a simple application of the powers-of-two FFT from the last article.

We’re going to do some simple frquency-domain filtering of audio data. We’ll start with reading WAV files. We can use the Haskell WAVE package to do this–it provides functions to read and write WAV files and has data structures for representing the WAV file header information and samples.

We’ll use a sort of sliding window FFT to process the samples from each channel in the WAV file. Here’s how this works:

We split the audio samples up into fixed-length “windows” (each $w$ samples long) with adjacent windows overlapping by $o$ samples. We select $w$ to be a power of 2 so that we can use our power-of-two FFT algorithm from the last section. We calculate the FFT of each window, and apply a filter to the spectral components (just by multiplying each spectral component by a frequency-dependent number). Then we do an inverse FFT, cut off the overlap regions and reassemble the modified windows to give a filtered signal.

I’m not going to talk much about the details of audio filtering here. Suffice it to say that what we’re doing isn’t all that clever and is mostly just for a little demonstration–we’ll definitely be able to change the sound of our audio, but this isn’t a particularly good approach to denoising speech. There are far better approaches to that, and I may talk about them at some point in the future.

Anyway, let’s look at some code:

-- A filter specifies a window size, a window overlap (both in terms
-- of numbers of samples) and a filter function (which should be a
-- window size length vector).
data Filter = Filter { fWindowSize :: Int
, fWindowOverlap :: Int
, fFilterFunc :: Vector (Complex Double) }

-- Helper for building filter functions.
build :: [(Int, Int)] -> Vector (Complex Double)
build segs = map realToFrac $concat$ P.map (\(n, v) -> replicate n v) segs

-- Smooth filter function.
smooth :: Vector (Complex Double)
smooth = map realToFrac $generate 1024$ \i ->
cos (2 * pi * fromIntegral i / 1023)

-- Some filters: at a sampling rate of 44100 Hz, 1024 samples is about
-- 0.02 seconds.
filt_noop, filt_hard, filt_hard_olap :: Filter
filt_smooth, filt_smooth_olap :: Filter
filt_noop = Filter 1024 0 (build [(1024,1)])
filt_hard = Filter 1024 0 (build [(128,1), (768,0), (128,1)])
filt_hard_olap = Filter 1024 256 (build [(128,1), (768,0), (128,1)])
filt_smooth = Filter 1024 0  smooth
filt_smooth_olap = Filter 1024 256 smooth
filters :: [Filter]
filters = [filt_noop, filt_hard, filt_hard_olap, filt_smooth, filt_smooth_olap]

First we define a very simple data structure for holding the information about a filter and we define some filters. The filtering function is defined as a vector of complex numbers (which must be the same length as the window size we specify), and we apply it just by multiplying into the spectra element-by-element. One thing we’re not bothering with here is power equalisation–if we use a filtering function that radically alters the overall magnitudes of the audio samples, we’ll end up with something that sounds much louder or softer than the original. It’s better to stick with filtering functions $f$ for which $\int_{-\infty}^\infty |f(x)|^2 \, dx = 1$. We’ll gloss over this detail. (We’re also not going to talk about windowing functions or anything else filtering-related. This is an example where we’re going to take almost the dumbest approach possible just to have a play.

Then we have a simple driver to read our WAV file, apply the filter (using the runFilter function) and write the result back to a new WAV file:

-- Main processing driver.
doit :: Filter -> String -> String -> IO ()
doit filt@(Filter win o _) fin fout = do
w <- getWAVEFile fin

-- Powers of two only.
Just nsamp = waveFrames h
nwins = (nsamp + o) div (win - o)
nsampout = (win - o) * nwins

-- Convert all channels to Vector (Complex Double) and extract
-- individual channels as vectors.
let d = fromList $P.map (map sampleToDouble . fromList)$
P.take (nsampout + o) $waveSamples w chs = map (\i -> map (!i) d)$ enumFromN 0 (waveNumChannels h)

-- Run filter.
let chout = map (runFilter filt) chs

-- Convert data back to frames and write out.
let dout = map (\i -> map (!i) chout) $enumFromN 0 nsampout sampout = toList$ map (toList . map doubleToSample) dout
wave = WAVE ((waveHeader w) { waveFrames = Just nsampout }) sampout
putWAVEFile fout wave

The only slight annoyance here is flipping back and forth between the WAV files “frame”-based view, which bundles all the samples at one time point for all channels together, and a channel-based view, where we get all the samples for a channel as a single vector that we can manipulate. We also deal with making sure that the signal we pass to the filter fits the window and overlap sizes we’re using.

Finally, we have the audio filtering pipeline itself:

-- Handy pipeline combinator.
(=>=) :: (a -> b) -> (b -> c) -> a -> c
(=>=) = flip (.)

-- Apply a filter to a channel.
runFilter :: Filter -> Vector Double -> Vector Double
runFilter (Filter w o ffn) din = proc ss
where
-- Data to Complex Double for our complex-to-complex FFT.
cdin = map realToFrac din

-- Window start positions.
ss = enumFromStepN 0 (w - o) ((length din + o) div (w - o))

-- Processing pipeline.
proc =     map (\s -> slice s w cdin)      -- Extract windows.
=>= map fft
=>= map (zipWith (*) ffn)           -- Filter.
=>= map ifft
=>= map (slice (o div 2) (w - o)) -- Slice off overlaps.
=>= toList =>= concat               -- Concatenate windows.
=>= map realPart                    -- Convert back to real data.

We define a handy sequencing operator which is just normal function composition with the arguments reversed (oddly enough, this doesn’t seem to have a standard name in Haskell), so we can just string operations together in something that looks like a signal processing pipeline. We slice up the data into windows, Fourier transform, apply the filtering function, inverse Fourier transform, cut off the window overlaps, concatenate everything back together and convert back to real values and we’re done.

This is all wrapped up into a little standalone program that we can run from the command line giving input and output WAV file names, along with an index into the filters list to select a filter to apply. So, what can we do with this? I recorded a few seconds of speech using no care at all and the crappiest microphone I could find, producing a WAV file with lots of noise. Let’s apply a series of different filters to it and see what we get. In all cases, we take a window size of 1024 samples (about 0.02 s at a sample rate of 44,100 Hz). We use a window-to-window overlap of either zero or 256 samples (i.e. a quarter of the window length at each end is overlapped with the adjacent windows), and we either use a “hard” filter which cuts out the middle half of the spectral elements (corresponding to zeroing out spectral components for frequencies above about 11 kHz) or a “smooth” cosine-shaped filter (which is one at zero frequency and falls to zero at the Nyquist frequency).

The following links go to WAV files:

• Original signal–very noisy, sounds like it might have been recorded on one of Thomas Edison’s old wax cylinder rigs.

• No overlap, hard filter–slightly less noisy, but it sounds like I’m in a bucket and you can hear a “clicking” artefact from the lack of window overlap.

• Overlap, hard filter–less noise, no clicking, still a little bit “buckety”.

• No overlap, smooth filter–same clicking artefact as in the “hard” filter case with no overlap.

• Overlap, soft filter–less noise, no clicking, not very buckety: definitely the best result.

There’s obviously relatively little merit to this in terms of making the sound sound nicer, but it shows how easy it is to fiddle with this kind of audio processing–the “filtering” function we’ve been using is a complex vector, so we could do all sorts of phase shifting things with it as well as modifying the amplitudes of the spectral components.

Anyway, I thought a post with no equations in it at all might be a nice break. In the next article, there will be quite a lot of equations and a fair bit head-scratching as we extend the “toy algebra” system to help understand the mixed-radix FFT for arbitrary vector lengths.


text:
# American Institute of Mathematical Sciences

• Previous Article
Predicting non-life insurer's insolvency using non-kernel fuzzy quadratic surface support vector machines
• JIMO Home
• This Issue
• Next Article
Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records
April  2019, 15(2): 963-984. doi: 10.3934/jimo.2018080

## A new relaxed CQ algorithm for solving split feasibility problems in Hilbert spaces and its applications

 1 Department of Mathematics, ORT Braude College, 2161002 Karmiel, Israel 2 The Center for Mathematics and Scientific Computation, University of Haifa, Mt. Carmel, 3498838 Haifa, Israel 3 Department of Mathematics, University of Transport and Communications, 3 Cau Giay Street, Hanoi, Vietnam

* Corresponding author: avivg@braude.ac.il

Received  November 2017 Revised  January 2018 Published  June 2018

Fund Project: The first author work is supported by the EU FP7 IRSES program STREVCOMS, grant no. PIRSES-GA-2013-612669. The research of the third author was partially supported by University of Transport and Communications (UTC) [grant number T2018-CB-002] and Vietnam Institute for Advanced Study in Mathematics (VIASM).

Inspired by the works of López et al. [21] and the recent paper of Dang et al. [15], we devise a new inertial relaxation of the CQ algorithm for solving Split Feasibility Problems (SFP) in real Hilbert spaces. Under mild and standard conditions we establish weak convergence of the proposed algorithm. We also propose a Mann-type variant which converges strongly. The performances and comparisons with some existing methods are presented through numerical examples in Compressed Sensing and Sparse Binary Tomography by solving the LASSO problem.

Citation: Aviv Gibali, Dang Thi Mai, Nguyen The Vinh. A new relaxed CQ algorithm for solving split feasibility problems in Hilbert spaces and its applications. Journal of Industrial & Management Optimization, 2019, 15 (2) : 963-984. doi: 10.3934/jimo.2018080
##### References:

show all references

##### References:
Numerical results for m = 210; n = 212; k = 20
Numerical results for m = 210; n = 212; k = 40
Numerical results for m = 212; n = 213; k = 50
Parallelbeam geometry set-up: a set of parallel rays is shot through the object from different directions. These are typically coined as one projection. Two projections are illustrated above. (Left) Illustration of a single projection corresponding to a measurement along one ray. The image domain $\Omega$ is tiled into pixels or mathematically Haar-basis functions. Hence, a single projection corresponds to the line integral over a piecewise constant function
] (left). We illustrate how such a $32\times 32$ image is sampled (right) along $45$ parallel and equidistant lines that are all perpendicular to $\theta: = (\cos(30^\circ),\sin(30^\circ))^T$">Figure 5.  Vessel test image from [4] (left). We illustrate how such a $32\times 32$ image is sampled (right) along $45$ parallel and equidistant lines that are all perpendicular to $\theta: = (\cos(30^\circ),\sin(30^\circ))^T$
] representing a vascular system containing larger and smaller vessels. The results are for the recover $u$ from a $15$ (limited number of) tomographic projections">Figure 6.  Reconstructing a binary test image $u\in \mathbb{R}^{64\times 64}$ from [4] representing a vascular system containing larger and smaller vessels. The results are for the recover $u$ from a $15$ (limited number of) tomographic projections
Numerical results obtained by Algorithm 1 compared with Lopez et al. algorithm [21] ((8)-(10)) and Zhou and Wang [39,Algorithm 3.1]
 K and m, n Methods $\epsilon$=10-6 Iter fk (10) CPU time (sec.) $\frac{\|x^*-x^k\|}{\|x^0-x^{k+1}\|}$ K = 10 Algorithm 1 3310 2.23e - 5 3.3438 0.0033 m = 210 Lopez et al. [21] 3491 3.23e - 5 3.8125 0.0045 n = 212 Zhou and Wang [39] 3991 2.79e - 4 4.7438 0.0012 K = 20 Algorithm 1 7180 9.6601e - 13 5.08281 3.380e - 5 m = 210 Lopez et al. [21] 8901 7.6601e - 13 5.28281 3.271e - 5 n = 212 Zhou and Wang [39] 8180 8.4375e - 12 6.478 3.260e - 5 K = 50 Algorithm 1 8780 5.7301e - 10 12.3312 4.276e - 4 m = 212 Lopez et al. [21] 9901 6.6601e - 9 11.2761 4.238e - 4 n = 213 Zhou and Wang [39] 9180 7.251e - 10 11.453 3.457e - 4
 K and m, n Methods $\epsilon$=10-6 Iter fk (10) CPU time (sec.) $\frac{\|x^*-x^k\|}{\|x^0-x^{k+1}\|}$ K = 10 Algorithm 1 3310 2.23e - 5 3.3438 0.0033 m = 210 Lopez et al. [21] 3491 3.23e - 5 3.8125 0.0045 n = 212 Zhou and Wang [39] 3991 2.79e - 4 4.7438 0.0012 K = 20 Algorithm 1 7180 9.6601e - 13 5.08281 3.380e - 5 m = 210 Lopez et al. [21] 8901 7.6601e - 13 5.28281 3.271e - 5 n = 212 Zhou and Wang [39] 8180 8.4375e - 12 6.478 3.260e - 5 K = 50 Algorithm 1 8780 5.7301e - 10 12.3312 4.276e - 4 m = 212 Lopez et al. [21] 9901 6.6601e - 9 11.2761 4.238e - 4 n = 213 Zhou and Wang [39] 9180 7.251e - 10 11.453 3.457e - 4
Numerical results obtained by Algorithm 1 compared with Lopez et al. algorithm [21] ((8)-(9)) and Zhou and Wang [39,Algorithm 3.1]
 K and m, n Methods $\epsilon$ = 10-6 Iter fk (10) CPU time (sec.) $\frac{\|x^*-x^k\|}{\|x^0-x^{k+1}\|}$ K = 916 Algorithm 1 87 37.6590 0.6406 65.7008 m = 1365 Lopez et al. [21] 100 49.3198 0.3541 38.2665 n = 4096 Zhou and Wang [39] 100 48.5597 0.6565 68.3321
 K and m, n Methods $\epsilon$ = 10-6 Iter fk (10) CPU time (sec.) $\frac{\|x^*-x^k\|}{\|x^0-x^{k+1}\|}$ K = 916 Algorithm 1 87 37.6590 0.6406 65.7008 m = 1365 Lopez et al. [21] 100 49.3198 0.3541 38.2665 n = 4096 Zhou and Wang [39] 100 48.5597 0.6565 68.3321
 [1] Grace Nnennaya Ogwo, Chinedu Izuchukwu, Oluwatosin Temitope Mewomo. A modified extragradient algorithm for a certain class of split pseudo-monotone variational inequality problem. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021011 [2] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [3] Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066 [4] Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $k$-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056 [5] Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045 [6] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [7] Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044 [8] Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053 [9] Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29 [10] Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133 [11] Mayte Pérez-Llanos, Juan Pablo Pinasco, Nicolas Saintier. Opinion fitness and convergence to consensus in homogeneous and heterogeneous populations. Networks & Heterogeneous Media, 2021, 16 (2) : 257-281. doi: 10.3934/nhm.2021006 [12] Yaonan Ma, Li-Zhi Liao. The Glowinski–Le Tallec splitting method revisited: A general convergence and convergence rate analysis. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1681-1711. doi: 10.3934/jimo.2020040 [13] Tadeusz Kaczorek, Andrzej Ruszewski. Analysis of the fractional descriptor discrete-time linear systems by the use of the shuffle algorithm. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021007 [14] Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063 [15] Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185 [16] Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053 [17] Annalisa Cesaroni, Valerio Pagliari. Convergence of nonlocal geometric flows to anisotropic mean curvature motion. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021065 [18] Antonio De Rosa, Domenico Angelo La Manna. A non local approximation of the Gaussian perimeter: Gamma convergence and Isoperimetric properties. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021059 [19] Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080 [20] Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

2019 Impact Factor: 1.366


text:
# How to graph path of parametric equations

I am having a lot of trouble answering the following question as it is required to consider the value of t also. If t did not have to be considered, it would have been an easy ellipse.

Let an object move such that $$\left\{ \begin{array}{cr} x =& \cos{2t} \\ y =& -\sin{t} \end{array} \right.\qquad \text{where} \quad 0 \leq t \leq \frac{5\pi}{4}$$ Sketch a graph of the path followed by the object.

I greatly appreciate your contributions. Thank you in advance

## 1 Answer

Let $$u=\sin t$$, then since $$\cos2t=1-2\sin^2t$$, the curve can be reparametrised to $$(1-u^2,-u)$$ for $$-\frac{\sqrt2}2\le u\le1$$ (the range of $$\sin t$$ restricted to $$0\le t\le\frac{5\pi}4$$). This can then be implicitised as $$x=1-2y^2$$, so the curve is a parabola lying between the points obtained by substituting $$t=-\frac{\sqrt2}2$$ and $$t=1$$ into the parametric form (i.e. $$(0,\sqrt2/2)$$ and $$(-1,-1)$$. The rest of the sketch should be easy from here.

• Thanks, @ParclyTaxel ! – wendy Aug 12 at 9:24
• @wendy Would you please accept my answer by clicking the tick left of it? – Parcly Taxel Aug 12 at 9:39
• Hi, @ParclyTaxel , I didn't realise I hadn't accepted your answer! Sorry for not doing it sooner. – wendy Aug 13 at 11:38


text:
# Rewriting a function with y as the independent variable

1. Aug 18, 2010

### Sidthewall

Ok. Sooo. Let's say u have y=x+5. Then u know y-5=x. Now if u have y=x^2 - x. How would u rearrange it to find out what x equals. I found out that in general I cannot rearrange ewquatioms with mitiplr x variables with different exponents. So help me plz

2. Aug 18, 2010

### Mentallic

It's just a quadratic in x where you treat y as a constant.
$$y=x^2-x$$

$$x^2-x-y=0$$

3. Aug 18, 2010

### Sidthewall

I am not trying to find the x-intercept. I need the function to have x as the dependent variable and y as the independent variable for ex. If y=sqr(25-x) then y^2 - 25 = -x

4. Aug 18, 2010

### Mute

Mentallic is pointing out that you have a quadratic equation of the form ax^2 + bx + c = 0. Solve the quadratic equation and you will get x in terms of y. (But there will be more than one solution as y = x^2 -x is not a 1 to 1 function).

Also, although you can do it in this case, note that you can't always explicitly solve for x in terms of y. For example, y = x + sin(x).

5. Aug 18, 2010

### Mentallic

Yep Mute's got it :tongue:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook


text:
GMAT Question of the Day - Daily to your Mailbox; hard ones only

 It is currently 15 Oct 2019, 01:54

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# One hour before John started walking from P to Q, a distance

Author Message
TAGS:

### Hide Tags

Intern
Joined: 15 Jun 2010
Posts: 9
One hour before John started walking from P to Q, a distance  [#permalink]

### Show Tags

15 Apr 2014, 15:28
6
00:00

Difficulty:

35% (medium)

Question Stats:

66% (01:35) correct 34% (01:54) wrong based on 118 sessions

### HideShow timer Statistics

One hour before John started walking from P to Q, a distance of 18 miles, Ann had started walking along the same road from Q to P. Ann walked at a constant speed of 3 miles per hour and John at 2 miles per hour. How many miles had Ann walked when they met?

A. 6 miles
B. 8,4 miles
C. 9 miles
D. 9,6 miles
E. 12 miles
Retired Moderator
Joined: 20 Dec 2013
Posts: 166
Location: United States (NY)
GMAT 1: 640 Q44 V34
GMAT 2: 710 Q48 V40
GMAT 3: 720 Q49 V40
GPA: 3.16
WE: Consulting (Venture Capital)
Re: One hour before John started walking from P to Q  [#permalink]

### Show Tags

15 Apr 2014, 19:00
In an hour Ann walked 3 miles. So when John started to walk the distance between the two was 15 miles. Add their respective rates together (3mph + 2mph = 5mph) and calculate how long it took them to cover the 15 miles at that combined rate (15miles/5mph = 3hrs)

So in 3 hours Ann walks 3mph*3hrs = 9miles. Last step is to add in the initial 3 miles she walked before John started.

9+3=12miles
_________________
Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9701
Location: Pune, India
Re: One hour before John started walking from P to Q  [#permalink]

### Show Tags

15 Apr 2014, 20:53
tauchmeister wrote:
I'm having problems with the following question to,

It is from and old set I have with me,

I have no idea from the source.

One hour before John started walking from P to
Q, a distance of 18 miles, Ann had started walking
along the same road from Q to P. Ann walked at a
constant speed of 3 miles per hour and John at 2
miles per hour. How many miles had Ann walked
when they met?
a) 6 miles
b) 8,4 miles
c) 9 miles
d) 9,6 miles
e) 12 miles

Thanks

This is again a relative speed question and I would suggest you to check out the links given in my previous post.

Ann walks from Q to P at a speed of 3 miles/hr for one hour. She covers 3 miles in 1 hour and now distance between John and Ann is 18 - 3 = 15 miles.

Ann walks at 3 mph and John at 2 mph so their relative speed is 3+2 = 5 mph.

They have to cover 15 miles so it will take them 15/5 = 3 hours to meet.
In 3 hrs, Ann would have covered 3 hrs * 3 miles per hour = 9 miles.

Adding this to the 3 miles she covered before John, Ann covered a total of 3 + 9 = 12 miles.

Another Method:
You can also use ratios to say that Ann and John have 15 miles between them (after Ann covers 3 miles) and their speeds are in the ratio 3:2. So Ann will cover 3/5 of the distance i.e. (3/5)*15 = 9 miles.
This gives a total distance of 3 + 9 = 12 miles
_________________
Karishma
Veritas Prep GMAT Instructor

SVP
Status: The Best Or Nothing
Joined: 27 Dec 2012
Posts: 1751
Location: India
Concentration: General Management, Technology
WE: Information Technology (Computer Software)
Re: One hour before John started walking from P to Q  [#permalink]

### Show Tags

15 Apr 2014, 21:41
Ann has already walked 3 Miles, so 15 Miles are remaining

Setting up the equation

$$\frac{15-x}{2} = \frac{x}{3}$$

x = 9

Distance covered by Ann = 9+3

_________________
Kindly press "+1 Kudos" to appreciate
Manager
Joined: 20 Apr 2014
Posts: 86
Re: One hour before John started walking from P to Q, a distance  [#permalink]

### Show Tags

10 Sep 2015, 15:12
i am sorry for the silly question but how they meet and Ann moved before john and his speed is faster as well and eventually they meet. I think they never or I am missing something ?
Manager
Status: single
Joined: 19 Jan 2015
Posts: 84
Location: India
GPA: 3.2
WE: Sales (Pharmaceuticals and Biotech)
Re: One hour before John started walking from P to Q, a distance  [#permalink]

### Show Tags

10 Sep 2015, 18:56
IN question itself some discrepancy,
it mentions onehour before john started .
then anna covered 9.6miles.

If question mentions anna started 1hour before then
anna covered 12 miles.

so in this context option D is correct.
Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9701
Location: Pune, India
Re: One hour before John started walking from P to Q, a distance  [#permalink]

### Show Tags

10 Sep 2015, 20:44
hatemnag wrote:
i am sorry for the silly question but how they meet and Ann moved before john and his speed is faster as well and eventually they meet. I think they never or I am missing something ?

John walks from P to Q but Ann walks from Q to P. They are both walking toward each other so they meet.

Quote:
IN question itself some discrepancy,
it mentions onehour before john started .
then anna covered 9.6miles.

If question mentions anna started 1hour before then
anna covered 12 miles.

so in this context option D is correct.

The statement:

"One hour before John started walking from P to Q, a distance of 18 miles, Ann had started walking along the same road from Q to P"

One hour before John started ... Ann had started ...

So Ann had started one hour before John started. Not the other way around.
_________________
Karishma
Veritas Prep GMAT Instructor

Target Test Prep Representative
Affiliations: Target Test Prep
Joined: 04 Mar 2011
Posts: 2817
Re: One hour before John started walking from P to Q, a distance  [#permalink]

### Show Tags

25 Jul 2017, 11:50
tauchmeister wrote:
One hour before John started walking from P to Q, a distance of 18 miles, Ann had started walking along the same road from Q to P. Ann walked at a constant speed of 3 miles per hour and John at 2 miles per hour. How many miles had Ann walked when they met?

A. 6 miles
B. 8,4 miles
C. 9 miles
D. 9,6 miles
E. 12 miles

We have a converging problem in which we use the formula distance of John + distance of Ann = total distance.

We can let John’s time = t and Ann’s time = (t + 1). Furthermore, John’s distance is 2t and Ann’s distance is 3(t + 1) = 3t + 3. So, we have:

2t + 3t + 3 = 18

5t = 15

t = 3

Thus, Ann traveled 3t + 3 = (3 x 3) + 3 = 12 miles.

_________________

# Jeffrey Miller

Jeff@TargetTestPrep.com
122 Reviews

5-star rated online GMAT quant
self study course

See why Target Test Prep is the top rated GMAT quant course on GMAT Club. Read Our Reviews

If you find one of my posts helpful, please take a moment to click on the "Kudos" button.

Non-Human User
Joined: 09 Sep 2013
Posts: 13147
Re: One hour before John started walking from P to Q, a distance  [#permalink]

### Show Tags

08 Apr 2019, 08:32
Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________
Re: One hour before John started walking from P to Q, a distance   [#permalink] 08 Apr 2019, 08:32
Display posts from previous: Sort by


text:
Recognitions:

## Positions in Infinite Space

 Quote by netzweltler Makes perfect sense to me from a set theoretical point of view. Is it possible, that "travelling forever" simply means "travelling to each position finitely apart" and not necessarily, that a position infinitely apart is reached?
We seem to have reached a point where we are trying to define terms (like traveling forever). The math itself is clear.

 Quote by mathman We seem to have reached a point where we are trying to define terms (like traveling forever). The math itself is clear.
A math example:

The union of the segments [0, 0.5], [0.5, 0.75], [0.75, 0.875], ... is [0, 1) and not [0, 1]. If I am drawing these segments of the unit interval I am drawing infinitely many segments, but I am not drawing the last point 1.0 (which in some sense could be named the $\omega$th segment).
If the drawing of one segment takes a second, I am drawing these segments forever, and I am not reaching a point infinitely apart (in some sense point 1.0).

That's what I meant, when I was asking:
 Quote by netzweltler Is it possible, that "travelling forever" simply means "travelling to each position finitely apart" and not necessarily, that a position infinitely apart is reached?
 Recognitions: Science Advisor The fallacy in your analogy is that each step takes a fixed amount of time, no matter how small the interval. I don't see the connection to the original question where (as I have already said) you need to give a precise definition of what you mean.
 To see the analogy it might be helpful to biject the previous example to the trip of the set of mathematicians who haven't reached their destination. Let's say 1. travelling the first meter → drawing the segment [0, 0.5] 2. travelling the second meter → drawing the segment [0.5, 0.75] 3. travelling the third meter → drawing the segment [0.75, 0.875] ... Do we have two different definitions of infinite travelling? 1. Travelling between two points infinitely apart 2. Passing every finite meter/segment of infinitely many meters/segments In the first case we arrive at the point infinitely apart. In the second case we don't. According to the first definition the set of mathematicians who haven't reached their destination is empty at arrival at the point infinitely apart. According to the second definition the set of mathematicians who haven't reached their destination is non-empty for the whole infinite trip, and so it might be valid to state, that the mathematicians of this set are on an infinite trip, thus questioning that there are only finite distances in infinite space.

This whole conversation seems to have gone somewhere where I don't know where it is. First, the original question: The travel time of every mathematician is finite. We've settled that. It's done. As for this comment...

 To see the analogy it might be helpful to biject the previous example to the trip of the set of mathematicians who haven't reached their destination. Let's say 1. travelling the first meter → drawing the segment [0, 0.5] 2. travelling the second meter → drawing the segment [0.5, 0.75] 3. travelling the third meter → drawing the segment [0.75, 0.875] ...
I'm not sure what you're doing here, but it seems to be some sort of reference to Zeno's paradox, which is, of course, just a problem of infinite series. The travel times corresponding to each of those distances (even carrying on the pattern into infinity) sums to a finite value. More specifically...$$\sum_{i=1}^\infty \frac{1}{2^n} = 1$$
If that's not what you're talking about...then I have no idea.

 Do we have two different definitions of infinite travelling? 1. Travelling between two points infinitely apart 2. Passing every finite meter/segment of infinitely many meters/segments
We've been discussing "infinite travelling" in terms of travel times, and the issue has been settled. As for your two points...

1) There are no such points. The euclidean metric assigns to every two points in the plain a finite distance.
2) I really have no idea what this is supposed to mean.
 To get an idea of what I mean it might help to clarify this first: I am shifting the line [0, 1] in infinitely many steps to the left step 1: I am shifting the line [0, 1] to position [-0.5, 0.5] step 2: I am shifting the line at [-0.5, 0.5] to position [-0.75, 0.25] step 3: I am shifting the line at [-0.75, 0.25] to position [-0.875, 0.125] ... At which position is the line after infinitely many steps?

 Quote by netzweltler to get an idea of what i mean it might help to clarify this first: I am shifting the line [0, 1] in infinitely many steps to the left step 1: I am shifting the line [0, 1] to position [-0.5, 0.5] step 2: I am shifting the line at [-0.5, 0.5] to position [-0.75, 0.25] step 3: I am shifting the line at [-0.75, 0.25] to position [-0.875, 0.125] ... At which position is the line after infinitely many steps?
[-1, 0]

 Quote by Number Nine [-1, 0]
At which step does the leftmost point of the line move to position -1?
 Quote by netzweltler step 1: I am shifting the line [0, 1] to position [-0.5, 0.5] step 2: I am shifting the line at [-0.5, 0.5] to position [-0.75, 0.25] step 3: I am shifting the line at [-0.75, 0.25] to position [-0.875, 0.125] ...

 Quote by Number Nine [-1, 0]
I don't follow that. It's like taking the sequence 1/2, 1/4, 1/8, ... and asking what's the value of the sequence "after infinitely many steps." If you're using the phrase to mean "what is the limit of the sequence as n goes to infinity," then the answer is zero. But there is no point at which the value of the sequence is actually zero; and that's a huge conceptual subtlety in a discussion like this. Isn't it?

 Quote by SteveL27 I don't follow that. It's like taking the sequence 1/2, 1/4, 1/8, ... and asking what's the value of the sequence "after infinitely many steps." If you're using the phrase to mean "what is the limit of the sequence as n goes to infinity," then the answer is zero. But there is no point at which the value of the sequence is actually zero; and that's a huge conceptual difference in a discussion like this. Isn't it?
it's not a sequence, it's a series. First he's moving 0.5 to the left, then 0.25...

 At which step does the leftmost point of the line move to position -1?
That's not how infinite series work. The limit as the number of steps go to infinity is [-1, 0], which is what you asked. If you meant something different, then elaborate.

 Quote by netzweltler step 1: I am shifting the line [0, 1] to position [-0.5, 0.5] step 2: I am shifting the line at [-0.5, 0.5] to position [-0.75, 0.25] step 3: I am shifting the line at [-0.75, 0.25] to position [-0.875, 0.125] ...
The number of steps is not going to infinity, the number of steps is infinite. Think of it as an actually infinite list of steps. None of the steps on this list is shifting the line to postion [-1, 0]. I can understand, that there are different notions of infinite travelling. That's what I meant before. According to your notion the line is actually arriving at [-1, 0]. According to the list above the position of the line is not defined after infinitely many steps, but the line has done an infinite trip.

 According to the list above the position of the line is not defined after infinitely many steps, but the line has done an infinite trip.
No, the line is [-1, 0] "after infinitely many steps". This a very elementary infinite series.

Honestly, I have no idea what it is that we're supposed to be talking about anymore. All of the initial questions about "infinite travelling" have been answered, but you seem to have spontaneously created some sort of brand new definition that you're not sharing with anyone. Please clearly explaining what it is that you're asking.
 step 1: at t = 0 I am shifting the line [0, 1] to position [-0.5, 0.5] step 2: at t = 0.5 I am shifting the line at [-0.5, 0.5] to position [-0.75, 0.25] step 3: at t = 0.75 I am shifting the line at [-0.75, 0.25] to position [-0.875, 0.125] ... All shifting is done before t = 1. No action is done at t = 1. Countable infinity doesn't allow a last shift at t = 1, which clearly is needed for point -1 to be covered. If this is my private math solely, further clarification doesn't make sense.

 Quote by netzweltler step 1: at t = 0 I am shifting the line [0, 1] to position [-0.5, 0.5] step 2: at t = 0.5 I am shifting the line at [-0.5, 0.5] to position [-0.75, 0.25] step 3: at t = 0.75 I am shifting the line at [-0.75, 0.25] to position [-0.875, 0.125] ... All shifting is done before t = 1. No action is done at t = 1. Countable infinity doesn't allow a last shift at t = 1, which clearly is needed for point -1 to be covered.
...what? Where does "countable infinity" enter into all of this? And what does it have to do with "moving at t=1"? You aren't even bothering to explain what it is that you're doing or asking, and it's making it very difficult to answer any of your questions. What does this have to do with "positions in infinite space"?


text:
# Crockcroft-Walton Voltage Multiplier Large Voltage Loss

I have a CW voltage multiplier that uses 30kV, 1nF capacitors and doubled 20kV, 5mA, 100ns diodes (for a total of 40kV). My ac source is a sine wave (viewed on the primary side of the transformer because the secondary is beyond the capacity of my oscilloscope) around 20-24kHz and produces 15kV DC when half-wave rectified (measured after the 150Mohm resistor.)

simulate this circuit – Schematic created using CircuitLab

The output voltage of the CW multiplier is only 1.5kV. I have tested the diodes and capacitors. 100ns is compatible with most frequencies below 1MHz, I believe.

I am thinking that it might be perhaps that the 12 $$\\Omega\$$ resistor is not allowing enough current to charge the capacitors, but maybe it is some thing else such as some reactance I am not taking into account?

• Arcing (or almost invisible leaking) through the air comes to mind. I don't know the size or arrangement of your parts. Can you consider immersing this in pure mineral oil and also take a moment to make sure that the distances between nodes are appropriate? Have a look here for an example of what I'm thinking about. – jonk Apr 13 '19 at 20:56
• How are you measuring voltage? – user_1818839 Apr 13 '19 at 21:00
• Consider R2 and the input impedance of whatever you are using to measure voltage. – JRE Apr 13 '19 at 21:08
• @jonk the multiplier is immersed in mineral oil and the 15kv half wave rectification of the input will charge the capacitor to 15 kilovolts. – user198606 Apr 13 '19 at 21:53
• @Brian Drummond two ways. the first with a 100 volt voltmeter with the voltage split between the internal impotence of the voltmeter and an add-on resistor in the Mohms. The second, with a regular multimeter with a hundred times probe. The meters work just fine when measuring 15 kV when half wave rectified. – user198606 Apr 13 '19 at 21:58


text:
# Bypass Capacitors – Why and How to Use Them?

You may have heard about the phenomenon of bypassing in circuits, however, we may not have sufficient knowledge of how to apply this technique in real circuits. In this tutorial, we will discuss about the bypass capacitors, why we need to use and how to use these capacitors in circuits.

## What is a Bypass Capacitor?

A capacitor that filters out the AC signal removing the noise and provides a DC signal is known as a bypass capacitor. The capacitor connected in the figure below is a bypass capacitor bypassing AC noise and allowing pure DC signal to pass through the component.

Operation of a Bypass Capacitor

## Why Use Bypass Capacitors?

In electronics, most of the circuits are digital in nature using direct current (DC). It has been observed that variations in voltage can cause problems to the circuit operation. A circuit may operate incorrectly due to voltage swing. In practical circuits, the voltage fluctuation is usually caused by the AC component that may ride over DC signal causing noise. Therefore, a bypass capacitor is needed to dampen the AC or noise present at all frequencies. Also, it prevents the unwanted communication between devices sharing the same power source.

## When do you Need Bypass Capacitors?

Firstly, the low frequency circuits may not require bypass capacitors. However, many low frequency active devices comprise of high frequency units. For example, a microcontroller is a low frequency device using a clock making a low frequency system, but the rising and falling glitches can occur due to internal gate transitions without proper filtering of power supply that will traverse the circuit. Therefore, you may need a bypass capacitor with an appropriate value to achieve proper filtering of power supply.

Secondly, you may have this misconception that only digital devices need bypass capacitors. However, bypass capacitors also benefit the analog circuits and devices in a different way. In digital systems, bypass capacitors control the fast timing of rising and falling glitches. Conversely, bypass capacitors help in reducing noise of power supply in analog systems. Generally, analog devices have built in capability of filtering power supply that is effective for reducing low frequency power supply noise, but it is not useful at higher frequencies.

## Types of Bypass Capacitor

Bypass capacitors are usually used in high speed environments where the capacitor inductances play a very critical role. The output of a part generates high frequency noise, typically greater than 100 MHz, on the power line at high speed switching. A high lead inductance capacitor will behave as an open circuit due to these harmonics which prevents it from providing the needed current to the power line to maintain a stable level, which results in failure of circuit functionality. Therefore, capacitors with very small inductances are required to bypass the internal noise of the device.

The inductance of a typical surface mount ceramic capacitor is 0.5nH, while the inductance of an electrolytic capacitor is 15nH. By calculating the inductive impedance of these bypass capacitors, we can observe the effect on bypassing:

Electrolytic Capacitor Ceramic Capacitor
$Z_L = 2 pi fL$
$Z_L = 2 x 3.142x 1.5x10^{8}x 15x10^{-9}$
$Z_L = 14 Omega$
$Z_L = 2 pi fL$
$Z_L = 2x 3.142x1.5x10^{8}x 0.5x10^{-9}$
$Z_L = 0.4 Omega$
$V_{drop} = IxZ_L$
$V_{drop} = (0.04 A)x (14 Omega)$
$V_{drop} = 0.56V$
$V_{drop} = IxZ_L$
$V_{drop} = (0.04 A)x (0.4 Omega)$
$V_{drop} = 0.016V$

From this example, we have observed that supply voltage drops below the operating voltage of the device due to more than one channel switching at the same time. Therefore, it is important to use the correct type of bypass capacitor. This is the reason that ceramic capacitors are more favorable than electrolytic capacitors for bypassing. They allow easy flow of charge when needed due to negligible internal inductance.

## How to Select Value of Bypass Capacitor?

Now we know why and when we need to use bypass capacitors, but we still need to find out the appropriate value of the capacitor to use for a particular device. The typical values considered for bypass capacitors are 0.1 µF and 1 µF. The higher the frequency, the smaller the value; while the lower the frequency, the large the value.

$f = frac{1}{2t_R}$

where tR = rise time.

The most important parameter to select an appropriate bypass capacitor is its ability to supply instantaneous current when it is needed. In order to select the capacitor size for a particular device, we have the following methods:

1. Firstly, the bypass capacitor size can be calculated using the following equation:

$C = frac{I*N* Delta t}{Delta V}$

I = amount of current needed to switch one output from low to high

N = switching number of outputs

∆t = time required to charge the line by the capacitor

∆V = tolerated drop in VCC

The values given in the formula should be known, where ∆t and ∆V can be assumed.

2. Another way to find out the bypass capacitor size is by calculating its maximum current with the specified maximum pulse slew rate. Maximum pulse slew rate is specified by several capacitor manufacturers.

$I = Cfrac{dV}{dt}$

## How to Use Bypass Capacitors?

The bypass capacitor value depends on the noise frequency of the supply that requires filtering. Therefore, a typical bypass capacitor of 0.01 µF or 0.1 µF is connected for high frequency supply noise and low current applications as shown in figure below:

Bypass capacitor for low current and high frequency application

However, power supply lines may have multiple frequencies in some applications where a single bypass capacitor is not sufficient. Thus, a network of bypass capacitors is used to filter the noise of wider range of frequencies. An example is given in the circuit below where capacitor C2 filters mid range frequencies, C3 filters higher frequencies and C4 filters low frequencies.

Bypass capacitor network for filtering multiple frequencies

It is also important to know that the bypass capacitors should be connected closer to the power supply pins because longer traces on printed circuit boards will increase the inductance and lower the frequency of the bypass track.

## Example of a Bypass Capacitor Application

It is simple and easy to use a bypass capacitor in a circuit without changing the connections of other circuit components. A bypass capacitor is simply placed between power source (VCC) and ground of each active device, as shown in figure below:

Bypass Capacitor connected in a Circuit

In the given circuit, the bypass capacitor is responsible for holding the emitter voltage steady and maintaining voltage gain. For the transistor connected in the above given circuit, iC increases as iB rises, increasing the emitter voltage. This decreases VBE that decreases iC resisting the rise in emitter voltage. Here the bypass capacitor is connected to shunt the signal occurring at the emitter through to the ground.


text:
# Completeness relation

## Main Question or Discussion Point

hi, in quantum physics completeness relation is often use it equals to one - what is its significance in multiplying with state vector . thanks
wasi

Related Quantum Physics News on Phys.org
jtbell
Mentor
Do you mean this:

$$\sum {| n \rangle \langle n |} = 1\\ \sum {| n \rangle \langle n | \psi \rangle} = | \psi \rangle$$

This represents the expansion of ##|\psi\rangle## into a linear combination of orthonormal basis states ##|n\rangle##. The ##\langle n | \psi \rangle## are the coefficients of the expansion. In the position representation we usually write this as something like

$$\psi(x) = \sum {c_n \psi_n(x)}$$


text:
New Titles  |  FAQ  |  Keep Informed  |  Review Cart  |  Contact Us Quick Search (Advanced Search ) Browse by Subject General Interest Logic & Foundations Number Theory Algebra & Algebraic Geometry Discrete Math & Combinatorics Analysis Differential Equations Geometry & Topology Probability & Statistics Applications Mathematical Physics Math Education

Lehrbuch der Topologie
 SEARCH THIS BOOK:
AMS Chelsea Publishing
1934; 353 pp; hardcover
Volume: 31
Reprint/Revision History:
reprinted 1980, first AMS printing 2003
ISBN-10: 0-8218-3595-5
ISBN-13: 978-0-8218-3595-1
List Price: US$43 Member Price: US$38.70
Order Code: CHEL/31.H

The 1930s were important years in the development of modern topology, pushed forward by the appearance of a few pivotal books, of which this is one. The focus is on combinatorial and algebraic topology, with as much point-set topology as needed for the main topics. One sees from the modern point of view that the authors are working in a category of spaces that includes locally finite simplicial complexes. (Their definition of manifold is more properly known today as a "triangulizable homology manifold".) Amazingly, they manage to accomplish a lot without the convenient tools of homological algebra, such as exact sequences and commutative diagrams, that were developed later. The main topics covered are: simplicial homology (coefficients in $$\mathbb{Z}$$ or $$\mathbb{Z}_2$$), local homology, surface topology, the fundamental group and covering spaces, three-manifolds, Poincaré duality, and the Lefschetz fixed point theorem.

Few prerequisites are necessary. A final section reviews the lemmas and theorems from group theory that are needed in the text. As stated in the introduction to the important book by Alexandroff and Hopf (which appeared a year after Seifert and Threlfall): "Its lively and instructive presentation makes this book particularly suitable as an introduction or as a textbook."

Reviews

"The exposition proceeds by easy stages with examples and illustrations at every turn."

-- Bulletin of the AMS

"The great strength of this book is the geometric insight it has given to generations of readers."

-- Mathematical Reviews

• Anschauungsmaterial
• Simplizialer Komplex
• Homologiegruppen
• Simpliziale Approximation
• Eigenschaften im Punkte
• Flächentopologie
• Fundamentalgruppe
• Überlagerungskomplexe
• Dreidimensionale Mannigfaltigkeiten
• $$n$$-dimensionale Mannigfaltigkeiten
• Stetige Abbildungen
• Hilfssätze aus der Gruppentheorie