text:
Emil asked in Science & MathematicsMathematics · 8 years ago

How to find Radius of Convergence for Sum of ((x-3)^n)/(n3^n) from n =1 to inf?

Please explain and show math. Very Confused.

Relevance
• kb
Lv 7
8 years ago

Use the Ratio Test.

r = lim(n→∞) |[(x-3)^(n+1)/((n+1) 3^(n+1))] / [(x-3)^n/(n * 3^n)]|

..= (1/3) |x - 3| * lim(n→∞) n/(n+1)

..= (1/3) |x - 3|.

So, the series converges for r = (1/3)|x - 3| < 1 ==> |x - 3| < 3, and diverges for |x - 3| > 3.

Hence, the radius of convergence is 3.

I hope this helps!


text:
# Contents

## Idea

Heyting arithmetic is the constructive counterpart of Peano arithmetic. It adopts all the axioms of Peano arithmetic, while using constructive logic as its rules of inference.

## References

Named after Arend Heyting.

format: plain


text:
theorem relating mersenne numbers?

For

$(x2^9)^2=2^q-1+y^2q^2$,where $q$ is prime,

is it possible to show that there exists only an unique solution for the pair $\{x,y\}$?

• I think the question is: given a prime $q$, show that there is at most one pair $(x,y)$ of positive integers such that $$2^{18}x^2=2^q-1+q^2y^2.$$ – Charles May 27 '15 at 15:42
• That is correct – Kurtul May 27 '15 at 15:45

$\newcommand\Z{\mathbf{Z}}$

If $2^{q} - 1 \equiv 0 \mod p$, then $2$ has order $q$ in the group $\mathbf{F}^{\times}_p$. Since the latter group has order $p -1$, it follows that any prime divisor of $2^{q} - 1$ is $1 \mod q$. Moreover, $2$ will be a quadratic residue modulo $p$, so any factor will also be congruent to $\pm 1$ modulo $8$.

With this in mind, consider the following lemma.

Lemma: Consider $128$ ordered elements (not necessarily distinct) of the abelian group $\Z/128 \Z$. Then some non-trivial subset of these elements sums to zero.

Proof: Order the list as $s_1, \ldots, s_{128}$. Consider the elements: $$s_1, \ s_1 + s_2, \ s_1 + s_2 + s_3, \ \ldots$$ There are $128$ such sums. If they are all distinct, one must be the identity. If two are the same, their difference is also a non-trivial sum which is equal to zero.

You can't do better (a priori) than 128, because one might have $s_i = 1$ modulo $128$ for all $i$.

We deduce:

Corollary: For any $129$ primes $\equiv \pm 1 \mod 8$, a non-trivial proper subset of them has a product which is $\pm 1 \mod 2^{10}$.

Proof:: Apply the lemma above to any subset of size $128$ and to the group of elements $\pm p_i \equiv 1 \mod 8$. Note that the group $(1 + 8\Z)/(1 + 2^{10} \Z)$ is cyclic of order $128$.

Corollary: If $2^{q} - 1$ has at least $129$ prime divisors, then there are at least two solutions to

$$2^{q} - 1 = (2^9 x)^2 - y^2 q^2 = (2^9 x + y q)(2^9 x - y q).$$

Proof: We want to write $2^q - 1 = AB$, where $A$ and $B$ have the required form, that is, we can solve for integral $x$ and $y$ in the equations:

$$A = 2^9 x + y q,$$ $$B = 2^9 x - y q.$$

This amounts to asking that $A \equiv B \equiv 1 \mod q$, and that $A$ is $\equiv \pm 1 \mod 2^{10}$. The trivial solution is $A = 1$ and $B = 2^{q} - 1$; we want to construct another such solution. Since all the prime factors of $2^q - 1$ are $1 \mod q$, the first condition is automatic. For the second, if we are assuming that $2^q - 1$ has at least $129$ prime factors, then, by the Lemma, there is a proper divisor which is $\pm 1 \mod 2^{10}$. This gives the desired solution.

One certainly expects that the numbers $2^{q} - 1$ can have an arbitrarily large number of prime factors, so one expects --- by the obvious generalization of the lemma above --- that there can exist arbitrarily many solutions as $q$ varies. In addition, one can hope to find a small $q$ with many factors such that some product is $\pm 1 \mod 2^{10}$ --- the bound in the Lemma is sharp in the worst case scenario, but in practice one expects many fewer than $129$ primes should suffice. The problem is that $2^q - 1$ is hard to factor as $q$ gets large. Instead, one can search for $q$ for which $2^q - 1$ has a small factor, say less than 500,000. For such small factors, they have (roughly) a one in $256$ chance of being $\pm 1 \mod 1024$, given they are $\pm 1$ modulo $8$. Since computing the GCD of $2^q - 1$ and (say) 500,000! is relatively cheap, it is realistic to search over a range of various $q$. One finds that:

$$2^{3527} - 1 \equiv 0 \mod p = 63487,$$

and, with $q = 3527$, we have

$$p \equiv 1 \mod q, \quad p \equiv -1 \mod 1024.$$

Hence, if

$$A = p, \quad B = \frac{2^{q} - 1}{p}, \qquad x = \frac{B+A}{2^{10}}, \quad y = \frac{B-A}{2q},$$

then

$$(2^9 x)^2 = 2^{q} - 1 + q^2 y^2$$

is a second solution (beyond the trivial case when $A = 1$ and $B = 2^{q} - 1$). Explicitly, $x$ equals

\begin{aligned} & \ 83139985554814564201142265398423940983734084680519373351274507224446764599607 \\ & \ 49451696564934671744653119863727621498244035702529608058476405955664605629948\\ & \ 62838307137784283737806179254649900079974691279735262514980072403875850975080\\ & \ 61957046474191593038928867902487454538277902526798081847840485073702295261112\\ & \ 33113621488853227725892116562645102916296506631441882237602645539576240063083\\ & \ 16542844209980653631941354248232439226396413730532924481168362238086941828118\\ & \ 38308509653785749056465841156627127934624282576692681779074414679440900436490\\ & \ 51748113171730486696573215817843552171786257357981110777970815770070081216602\\ & \ 65313780022194173593463676305763851504432476029971231801801391928524170852121\\ & \ 01902453812880831869001524277687896922188634322634430157407549044529132580919\\ & \ 11569976254856032521966500715204341110750005850922868567006271584961070720322\\ & \ 41598144814720814044682551670392948705627868423019659857466668911286790507132\\ & \ 78061681936258561522605907127622832906278247368600982784494146323005476392476\\ & \ 84876567107301371945802093257368889076102458785927292, \end{aligned}

and $y$ equals \begin{aligned} & \ 12069087781135542067191618906717623414707074385150529956295023447382121767791\\ & \ 05108950564572314129079216719656518913269335491833047724961701119733563391702\\ & \ 21086819748949689048414166084031967349290343616451503943200963161549315480363\\ & \ 27678482504901076165560414053323951438502491095469412505271995564994492535778\\ & \ 14390182648792983440787287689275387778039073262063579162362504824571316958406\\ & \ 17541802164873857289354684824240149952910395188554822039795350571562379987523\\ & \ 84806905852775249083331587942215222427708430019638971667390445227069390706969\\ & \ 98722720142876668326806205415008760621478470021912766860879233817486782416473\\ & \ 08148754003788890524483527720031497581590424646256101696207063415765346038073\\ & \ 70619239113182587444550263802148058753660499226875199387749550640997707933493\\ & \ 22008457000988457230293974586386340416417352706456622825717950397363217524469\\ & \ 82619294058728964216296418047984459806430810499740874921185975186441405369904\\ & \ 16321968004356218741019059951614088587472203757506011677250071708925093255726\\ & \ 72145393353824298961227862701381590929108153926394871.\end{aligned}

There's also a second solution when $q = 6947$. In this case, $p= 180623$ and $p' = 333457$ are divisors of $2^q - 1$, and

$$A = p p' = 60230003711 \equiv -1 \mod 1024.$$

• I have learned a lot from your answer, Forgive my ignorance for asking since you have proved that If $2^q−1$ has at least 129 prime divisors then there are at least two solutions. What if 2q−1 has at less than 129 prime divisors? – Kurtul May 29 '15 at 8:38
• The number of solutions is the number of divisors of $2^q - 1$ which are $1$ modulo $2^{10}$. There's probably not much more that one can say in general. For example, $2^{3527} - 1$ presumably has fewer than $129$ prime factors, but it just so happens to have a small prime factor $p = 63487$ such that $(2^q - 1)/p$ is $1$ modulo $2^{10}$. – Epargyreus May 29 '15 at 13:03


text:
## Chemistry 10th Edition

Percent ionization $\approx$ 4.9%.
1. Drawing the equilibrium (ICE) table we get these concentrations at equilibrium:** The image is in the end of this answer. -$[H_3O^+] = [HCOO^-] = x$ -$[HCOOH] = [HCOOH]_{initial} - x = 0.0751 - x$ For approximation, we consider: $[HCOOH] = 0.0751M$ 2. Now, use the Ka value and equation to find the 'x' value. $Ka = \frac{[H_3O^+][HCOO^-]}{ [HCOOH]}$ $Ka = 1.8 \times 10^{- 4}= \frac{x * x}{ 7.51 \times 10^{- 2}}$ $Ka = 1.8 \times 10^{- 4}= \frac{x^2}{ 7.51 \times 10^{- 2}}$ $1.352 \times 10^{- 5} = x^2$ $x = 3.677 \times 10^{- 3}$ Percent ionization: $\frac{ 3.677 \times 10^{- 3}}{ 7.51 \times 10^{- 2}} \times 100\% = 4.896\%$ %ionization < 5% : Right approximation.


text:
# Reference figures across .tex documents when using includeonly and endfloat

I am looking to have a document Main.tex that references content in two sub-documents, Doc1.tex and Doc2.tex via \include{} and that can be configured to only compile to PDF the content in a particular one of those documents. Following the discussion in this answer to: Splitting(!) one latex document into two pdf outputs including references , I can get the basics working just fine. But, when I use the endfloat package the functionality falls apart. Below is a minimal working example. It works fine if I:

1. First compile Main.tex with the \includeonly{} command commented out.

2. Then re-compile Main.tex removing the comment from \includeonly{}.

But, as soon as I remove the comment to load the endfloat package, I lose the ability to reference figures in Doc2.tex - instead, the references just appear as ?? in the compiled PDF.

Main.tex

\documentclass{article}
% \usepackage[notablist,nofiglist,nomarkers]{endfloat}  %% places all figures and tables at the end.

% \includeonly{Doc1}

\begin{document}

\include{Doc1}

\include{Doc2}

\end{document}

Doc1.tex

As I show in Figure \ref{fig1} in Doc2 ...

Doc2.tex

\begin{figure}
\centering\rule{1cm}{1cm}
\caption{This is a figure}
\label{fig1}
\end{figure}
• Would subfiles be an alternative? see tex.stackexchange.com/a/378163/36296 – user36296 Aug 8 '17 at 20:41
• It can't really work. endfloat writes the figures to an external file. If this file is not process the labels are not there. And I also don't really understand what should happen at the end with the figures. Are some printed and if yes which one and where? – Ulrike Fischer Aug 8 '17 at 21:28
• @UlrikeFischer Regarding the desired behavior - the goal is to only print figures from Doc1, and to do so at the end of Doc1, but to be able to reference figures from Doc2 from within Doc1. Thanks! – aireties Aug 8 '17 at 22:03
• @samcarter I think that has some potential. But, I've also run into difficulties with the subfiles package. See the new question that I posted here describing those challenges: tex.stackexchange.com/questions/385485/… – aireties Aug 9 '17 at 0:48

This question can be broken down into two parts:

• Compiling the two parts separately. I recommend the subfiles for this - it allows you to easily share the preamble of the main file with the subfiles

• cross referencing between the subfiles. With the xr-hyper package you can import labels from another file. The trick is to use this only for the compilation of the subfiles, not when the main file is compiled, that's why the inclusion in the below references answer tests for the jobname of the compilation.

An example how to use both can be found at Cross Reference problem

If as you mention in the comment the figures can be at the end of every subfile then this will probably work:

Put \processdelayedfloats at the end of every subdocument.

Compile without the \includeonly until everything is stable and then use \includeonly.

• Great, thank you very much for these suggestions. They are both helpful on their own and in aiding me in discovering yet another solution to the problem, which is to switch my compiler for the .tex files. – aireties Aug 10 '17 at 15:49

Interestingly, I discovered that my original scripts actually work just as given if I compile them using TeXShop, but not if I compile them, as I was previously doing, with Sublime LaTeXing. I still am not fully certain of the reason for this. But, in TeXShop, a successful workflow is:

1. Compile Main.tex
2. Compile Main.tex again, making no changes
3. Uncomment the includeonly{ } and then compile Main.tex one more time.

Props to the answer from @Ulrike Fischer that got me to try out variations along these lines, first precisely as suggested in Ulrike's answer and then to realize that the basic procedure from Ulrike would work even on the original scripts I had posted if I switched my compiler.


text:
a high-level multithreaded programming model - Maple Help

Description

 • The Task package provides a high-level multithreaded programming interface.  It provides a programming model that simplifies multithreaded programming.  For more details of the Task programming model, see the Task Programming Model help page.


text:
# Using prim for bump hunting

#### 05 February 2021

The Patient Rule Induction Method (PRIM) was introduced by Friedman and Fisher (1999). It is a technique from data mining for finding interesting’ regions in high-dimensional data. We start with regression-type data (X1, Y1), …, (Xn, Yn) where Xi is d-dimensional and Yi is a scalar response variable. We are interested in the conditional expectation function

m(x) = E (Y | X = x).

In the case where we have a single sample then PRIM finds the bumps of m(x).

We use a subset of the Boston data set in the MASS library. It contains housing data measurements for 506 towns in the Boston, USA area. For the explanatory variables, we take the nitrogen oxides concentration in parts per 10 million nox and the average number of rooms per dwelling rm. The response is the per capita crime rate crim. We are interested in characterising those areas with higher crime rates in order to provide better support infrastructure.

library(prim)
library(MASS)
data(Boston)
x <- Boston[,5:6]
y <- Boston[,1]
boston.prim <- prim.box(x=x, y=y, threshold.type=1)

The default settings for prim.box are

• peeling quantile: peel.alpha=0.05
• pasting is carried out: pasting=TRUE
• pasting quantile: paste.alpha=0.01
• minimum box mass (proportion of points inside a box): mass.min=0.05
• threshold is the overall mean of the response variable y
• threshold.type=0

We use the default settings except that we wish to only find high crime areas {m(x) $$\ge$$ threshold} so we set threshold.type=1.

We view the output using a summary method. This displays three columns: the box mean, the box mass, and the threshold type. Each line is a summary for each box, as well as an overall summary. The box which is asterisked indicates that it is the box which contains the rest of the data not processed by PRIM. There is one box which contains 42.89% of the towns and where the average crime rate is 7.62. This is our HDR estimate. This regions comprises the bulk of the high crime areas, and is described in terms of nitrogen oxides levels in [0.53, 0.74] and average number of rooms in [3.04, 7.07]. The other 57.11% of the towns have an average crime rate of 0.6035.

summary(boston.prim, print.box=TRUE)
#>           box-fun  box-mass threshold.type
#> box1    7.6222290 0.4288538              1
#> box2*   0.6035267 0.5711462             NA
#> overall 3.6135236 1.0000000             NA
#>
#> Box limits for box1
#>        nox     rm
#> min 0.5332 3.0391
#> max 0.7400 7.0718
#>
#> Box limits for box2
#>        nox     rm
#> min 0.3364 3.0391
#> max 0.9196 9.3019

We plot the PRIM boxes, including all those towns whose crime rate exceeds 3.5. Thus verifying that the majority of high crime towns fall inside thebump.

plot(boston.prim, col="transparent")
points(x[y>3.5,])

There are many options for the graphical display. See the help guide for more details ?plot.prim.

The default function applied to the response variable y is mean. We can input another function, e.g. median, using

boston.prim.med <- prim.box(x=x, y=y, threshold.type=1, y.fun=median)

We compare the results: the box for the mean is in black, for the median in red:

plot(boston.prim, col="transparent")
legend("topleft", legend=c("mean", "median"), col=1:2, lty=1, bty="n")

The covariate x can also include categorical variables: we replace the average number of rooms per dwelling rm with the index of accessibility to radial highways rad which takes integral values from 1 to 24 inclusive.

x2 <- Boston[,c(5,9)]
y <- Boston[,1]
boston.cat.prim <- prim.box(x=x2, y=y, threshold.type=1)
summary(boston.cat.prim, print.box=TRUE)
#>           box-fun  box-mass threshold.type
#> box1    7.2629703 0.4822134              1
#> box2*   0.2148022 0.5177866             NA
#> overall 3.6135236 1.0000000             NA
#>
#> Box limits for box1
points(x2[y>3.5,])`


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

 It is currently 15 Nov 2019, 00:07

### 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

# Each year for 4 years, a farmer increased the number of trees in a

Author Message
TAGS:

### Hide Tags

e-GMAT Representative
Joined: 04 Jan 2015
Posts: 3138
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

04 Nov 2018, 03:28
yashna36 wrote:
Hi,

I tried using geometric progression formula for this ->
x is the no of trees at the end of 1st year, end of 2nd year no of trees is 5x/4. Therefore, common ratio (r) is 5/4

6250=x(r^n-1)
6250= x(5/4)^4-1
6250=x(5/4)^3
x=(6250*64)/125
x=3200

can you please explain to me where has my reasoning gone wrong?

Hey yashna36,
There is nothing wrong in your reasoning - you need to do one more step to get the final answer.

You have assumed x as the number of trees at the end of 1st year, whereas the question is asking us to find the number of trees at the beginning of the 1st year.

Therefore, you need to divide 3200 by 5/4 to get the final answer.

Hope this helps.
_________________
Manager
Joined: 14 Jun 2018
Posts: 212
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

04 Nov 2018, 12:09
It's a compound interest with rate = 25% , time = 4 year.

6250 = x (1+ 25/100)^4

x = 2560
Manager
Joined: 19 Jan 2018
Posts: 78
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

28 Jan 2019, 13:30
imhimanshu wrote:
Each year for 4 years, a farmer increased the number of trees in a certain orchard by 1/4 of the number of trees in the orchard of the preceding year. If all of the trees thrived and there were 6250 trees in the orchard at the end of 4 year period, how many trees were in the orchard at the beginning of the 4 year period.

A. 1250
B. 1563
C. 2250
D. 2560
E. 2752

[/spoiler]

Useful to know your Powers of 4 $$5^4 = 625$$ and $$4^4 = 256$$

"Each year for 4 years, a farmer increased the number of trees in a certain orchard by 1/4 of the number of trees in the orchard of the preceding year"
This translate into:

$$Year 1 = X *$$ $$\frac{5}{4}$$

$$Year 2 = X *$$ $$\frac{5}{4}$$ * $$\frac{5}{4}$$

$$Year 3 = X *$$ $$\frac{5}{4}$$ * $$\frac{5}{4}$$ * $$\frac{5}{4}$$

$$Year 4$$ or 6250 trees $$= X *$$ $$\frac{5}{4}$$ * $$\frac{5}{4}$$ * $$\frac{5}{4}$$ * $$\frac{5}{4}$$
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

$$6250 = X *$$ $$\frac{5^4}{4^4}$$

$$625 * 10 = X *$$ $$\frac{5^4}{4^4}$$

$$25^2 * 10 = X *$$ $$\frac{5^4}{4^4}$$

$$5^4 * 10 = X *$$ $$\frac{5^4}{4^4}$$ (The $$5^4$$ cancel out, leaving $$4^4$$)

$$4^4 * 10 = X$$

$$256 * 10 = X$$

$$2560 = X$$

Intern
Joined: 22 Jan 2019
Posts: 7
Location: Spain
Schools: HKUST '22
GMAT 1: 690 Q50 V34
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

30 Jan 2019, 14:36
Hi,

I may not be 100% sure, but tell me if you agree: I've solved the problem using the compound rate formula for exercises about loans.

Final value = Initial value * (1+ i)^n, where "i" is the interest rate or growth in this case, and "n" number of years. Therefore:

6250= x*(1+1/4)^4 = x*(5/4)^4 --> x= 5^4*10/(5^4/4^4) =(5^4*10*4^4)/5^4=10*4^4=10*64*4=640*4=2560 --> Answer D
VP
Joined: 23 Feb 2015
Posts: 1298
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

02 Jul 2019, 04:20
Bunuel wrote:
imhimanshu wrote:
Each year for 4 years, a farmer increased the number of trees in a certain orchard by 1/4 of the number of trees in the orchard of the preceding year. If all of the trees thrived and there were 6250 trees in the orchard at the end of 4 year period, how many trees were in the orchard at the beginning of the 4 year period.

A. 1250
B. 1563
C. 2250
D. 2560
E. 2752

Can someone walk me through the logic behind this question. I am able to solve this by using options as well as by assuming the number of trees = x. However, had the question been, "If all of the trees thrived and there were 6250 trees in the orchard at the end of 15 year period, how many trees were in the orchard at the beginning of the 4 year period". then it would have been difficult to solve.

Thanks

Say the number of trees at the beginning of the 4 year period was x, then:
At the end of the 1st year the number of trees would be $$x+\frac{1}{4}x=\frac{5}{4}*x$$;
At the end of the 2nd year the number of trees would be $$(\frac{5}{4})^2*x$$;
At the end of the 3rd year the number of trees would be $$(\frac{5}{4})^3*x$$;
At the end of the 4th year the number of trees would be $$(\frac{5}{4})^4*x$$;
At the end of the $$n_{th}$$ year the number of trees would be $$(\frac{5}{4})^n*x$$;

So, we have that $$(\frac{5}{4})^4*x=6,250$$ --> $$\frac{5^4}{4^4}*x=5^4*10$$ --> $$x=4^4*10=2,560$$.

If the question were "if all of the trees thrived and there were 6250 trees in the orchard at the end of 15 year period, how many trees were in the orchard at the beginning of the 4 year period", then we would have that: $$(\frac{5}{4})^{15}*x=6,250$$ --> $$x\neq{integer}$$, so it would be a flawed question.

Hope it's clear.

Bunuel
In that time, the maker of the question will replace the figure 6250 with another one so that x has to be integer, right?
Thanks__
_________________
“The heights by great men reached and kept were not attained in sudden flight but, they while their companions slept, they were toiling upwards in the night.”

SEARCH FOR ALL TAGS
Math Expert
Joined: 02 Sep 2009
Posts: 59039
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

02 Jul 2019, 04:24
Bunuel wrote:
imhimanshu wrote:
Each year for 4 years, a farmer increased the number of trees in a certain orchard by 1/4 of the number of trees in the orchard of the preceding year. If all of the trees thrived and there were 6250 trees in the orchard at the end of 4 year period, how many trees were in the orchard at the beginning of the 4 year period.

A. 1250
B. 1563
C. 2250
D. 2560
E. 2752

Can someone walk me through the logic behind this question. I am able to solve this by using options as well as by assuming the number of trees = x. However, had the question been, "If all of the trees thrived and there were 6250 trees in the orchard at the end of 15 year period, how many trees were in the orchard at the beginning of the 4 year period". then it would have been difficult to solve.

Thanks

Say the number of trees at the beginning of the 4 year period was x, then:
At the end of the 1st year the number of trees would be $$x+\frac{1}{4}x=\frac{5}{4}*x$$;
At the end of the 2nd year the number of trees would be $$(\frac{5}{4})^2*x$$;
At the end of the 3rd year the number of trees would be $$(\frac{5}{4})^3*x$$;
At the end of the 4th year the number of trees would be $$(\frac{5}{4})^4*x$$;
At the end of the $$n_{th}$$ year the number of trees would be $$(\frac{5}{4})^n*x$$;

So, we have that $$(\frac{5}{4})^4*x=6,250$$ --> $$\frac{5^4}{4^4}*x=5^4*10$$ --> $$x=4^4*10=2,560$$.

If the question were "if all of the trees thrived and there were 6250 trees in the orchard at the end of 15 year period, how many trees were in the orchard at the beginning of the 4 year period", then we would have that: $$(\frac{5}{4})^{15}*x=6,250$$ --> $$x\neq{integer}$$, so it would be a flawed question.

Hope it's clear.

Bunuel
In that time, the maker of the question will replace the figure 6250 with another one so that x has to be integer, right?
Thanks__

Since x represent the number of trees, then it must be an integers, so if you were to replace 6,250 with some other number, you should replace it so that x at the end turns out to be an integer.
_________________
Intern
Joined: 17 May 2019
Posts: 19
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

28 Jul 2019, 15:21
Bunuel wrote:
imhimanshu wrote:
Each year for 4 years, a farmer increased the number of trees in a certain orchard by 1/4 of the number of trees in the orchard of the preceding year. If all of the trees thrived and there were 6250 trees in the orchard at the end of 4 year period, how many trees were in the orchard at the beginning of the 4 year period.

A. 1250
B. 1563
C. 2250
D. 2560
E. 2752

Can someone walk me through the logic behind this question. I am able to solve this by using options as well as by assuming the number of trees = x. However, had the question been, "If all of the trees thrived and there were 6250 trees in the orchard at the end of 15 year period, how many trees were in the orchard at the beginning of the 4 year period". then it would have been difficult to solve.

Thanks

Say the number of trees at the beginning of the 4 year period was x, then:
At the end of the 1st year the number of trees would be $$x+\frac{1}{4}x=\frac{5}{4}*x$$;
At the end of the 2nd year the number of trees would be $$(\frac{5}{4})^2*x$$;
At the end of the 3rd year the number of trees would be $$(\frac{5}{4})^3*x$$;
At the end of the 4th year the number of trees would be $$(\frac{5}{4})^4*x$$;
At the end of the $$n_{th}$$ year the number of trees would be $$(\frac{5}{4})^n*x$$;

So, we have that $$(\frac{5}{4})^4*x=6,250$$ --> $$\frac{5^4}{4^4}*x=5^4*10$$ --> $$x=4^4*10=2,560$$.

If the question were "if all of the trees thrived and there were 6250 trees in the orchard at the end of 15 year period, how many trees were in the orchard at the beginning of the 4 year period", then we would have that: $$(\frac{5}{4})^{15}*x=6,250$$ --> $$x\neq{integer}$$, so it would be a flawed question.

Hope it's clear.

Hi.

I made the eqn of x+0.4 x+1.6x+6.4x=6250 but it did not work .Do you mind clarifying where the mistake is ? I am not also very clear on where we derived the (5/4)^n formula.

Thanks a lot in advance !!
Intern
Joined: 08 Dec 2014
Posts: 8
Location: India
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

23 Aug 2019, 08:30
Hi,
If we manually try to solve the question, it comes at the end 125x/64. This is equal to the given value i.e. 6250.
Steps:
1st year> x trees
2nd year> x+(1/4)x = (5/4)x
3rd year> (5/4)x + 1/4{(5/4)}x = (25/16)x
4th year> (25/16)x + 1/4{(25/16)}x = (125/64)x

Solving this, we get x/64 = 50. Thus, x = 3200. But the correct answer is 2560. Please let me know what went wrong.
Intern
Joined: 18 Jan 2018
Posts: 28
Location: India
GPA: 3.27
WE: Operations (Other)
Re: Each year for 4 years, a farmer increased the number of trees in a  [#permalink]

### Show Tags

01 Sep 2019, 22:46
I solved it in less 45 seconds. The question says the growth happened by a factor of 1/4. The correct answer should be divisible by 4, otherwise the number of trees for the next year would not be an integer. Out of all the options only D is divisible by 4.
Re: Each year for 4 years, a farmer increased the number of trees in a   [#permalink] 01 Sep 2019, 22:46

Go to page   Previous    1   2   3   [ 49 posts ]

Display posts from previous: Sort by


text:
Deriving the Lorentz Transformation from the Homogeneity of Spacetime

Homework Statement

Show that the isotropy and homogeneity of space-time and equivalence of different inertial frames (first postulate of relativity) require that the most general transformation between the space-time coordinates (x, y, z, t) and (x', y', z', t') is the linear transformation,
x'=f(v2)x-vf(v2)t; t'=g(v2)t-vh(v2)x; y'=y; z'=z
and its inverse,
x=f(v2)x'+vf(v2)t'; t=g(v2)t'+vh(v2)x'; y=y'; z'=z'

The Attempt at a Solution

Now, I know that homogeneity implies that the transformation must be linear in x and t and that the isotropy of space implies that the coefficients can only be functions of the magnitude of the velocity (not the direction) at most. Therefore, I am stuck at the following:
x'=f(v2)x-vf0(v2)t; t'=g(v2)t-vh(v2)x; y'=y; z'=z
However, I am having trouble proving that f = f0. The solution I am looking at says that this follows from the homogeneity of space-time but I am having trouble using that fact to prove it.

strangerep


text:
22055 articles – 15889 references  [version française]

hal-00309695, version 3

## NORMAL FORMS FOR SEMILINEAR QUANTUM HARMONIC OSCILLATORS

Benoit Grebert () 1, Rafik Imekraz 1, Eric Paturel 1

Communications in Mathematical Physics 291 (2009) 763-798

Abstract: We consider the semilinear harmonic oscillator $$i\psi_t=(-\Delta +\va{x}^{2} +M)\psi +\partial_2 g(\psi,\bar \psi), \quad x\in \R^d,\ t\in \R$$ where $M$ is a Hermite multiplier and $g$ a smooth function globally of order 3 at least.\\ We prove that such a Hamiltonian equation admits, in a neighborhood of the origin, a Birkhoff normal form at any order and that, under generic conditions on $M$ related to the non resonance of the linear part, this normal form is integrable when $d=1$ and gives rise to simple (in particular bounded) dynamics when $d\geq 2$.\\ As a consequence we prove the almost global existence for solutions of the above equation with small Cauchy data. Furthermore we control the high Sobolev norms of these solutions.

• 1:  Laboratoire de Mathématiques Jean Leray (LMJL)
• CNRS : UMR6629 – Université de Nantes – École Centrale de Nantes

• hal-00309695, version 3
• oai:hal.archives-ouvertes.fr:hal-00309695
• From:
• Submitted on: Monday, 14 December 2009 11:48:07
• Updated on: Monday, 14 December 2009 13:40:51


text:
# Simplifying and improving (namely DRY) for flight info fetcher

I've put together this simple fetcher for text data (which I just copy and pasted from a flight info website) - it takes in text data, and spits out an array of objects containing values for each property of each flight it finds. I thought it would be a good accompaniment exercise to "Eloquent Javascript: Chapter 3, Data Structures: Objects and Arrays."

• I'm looking for ways in which I should condense the functions, or possibly merge their tasks. I don't think there's a whole lot that can be shared amongst each fetch function, however.
• I think there may be a more simple way of noting the index of each item (found from the specific fetcher function), and then passing that on to the next fetcher function, but I'm not sure if that applies for each property of the flight, and I'm not sure what pattern I would use for that.
• General code critique or advice?

*Note: I held off on adding fetchers for timeSched, status, and onSched until I get some feedback here, thanks! *

var flightObject = {

/*
We assume our text value comes in this form: airlineCode airlineName destAbbrev dest timeSched status onSched
*/

text: "9E 3801 Pinnacle Airlines (MSP) Minneapolis 3:38 PM Landed On-time\nDL 3801 Delta Air Lines (MSP) Minneapolis 3:38 PM Landed On-time\n1I 131 Netjets Aviation (MEM) Memphis 3:06 PM Scheduled On-time\n1I 880 Netjets Aviation (HPN) Westchester County 3:06 PM En Route On-time\nRAX 308 Royal Air Freight, Inc. (FDY) Findlay 3:06 PM Landed On-time\nWN 627 Southwest Airlines (FLL) Fort Lauderdale 3:16 PM En Route On-time\nWN 2541 Southwest Airlines (SAT) San Antonio 3:35 PM En Route Delayed\nWN 1939 Southwest Airlines (LAS) Las Vegas 3:35 PM En Route On-time\nFIV 540 Citationshares (PWK) Chicago 3:10 PM Scheduled On-time",

/*
Here is our function that grabs the Flight Number (airlineCode), Airline (airlineName),
Destination Abbreviation (destAbbrev), and Destination Long Title (dest),
Scheduled Time (timeSched), Status of Flight (stat), and whether flight is on time (onSched)
*/

extractFlight: function() {

/*
Split paragraphs into lines
*/

var paragraphs = this.text.split("\n");

/*
Get index for parenthesis which will help in finding destAbbrev
note: start at i = 3 because we know it can't occur earlier
due to data's nature.
*/

function getParenthIndex(){

for( var i = 3 ; i < words.length ; i++ ) {
var word = words[i];
if (word.charAt(0) === "(") {
return i;
}
}

}

function getAirlineName(){
var parenthIndex = getParenthIndex();
var airlineName = "";

/*
note: we start for loop at i = 2 because we know it can't
occur earlier due to data's nature.
*/

for( var i = 2; i < parenthIndex; i++ ) {
var word = words[i];
if (i === parenthIndex - 1) {
return airlineName += word;
}
else {
airlineName += word + " ";
}
}
}

/*
Grab destination abbreviation using index of
word that starts with parenthesis as guide
*/

function getDestAbbrev(){
var parenthIndex = getParenthIndex();
return words[parenthIndex];
}

/*
Grab destination using index of
word that starts with parenthesis as guide,
while searching for number to know when to stop.
*/

function getDest(){
var parenthIndex = getParenthIndex();
var dest = "";

for( var i = parenthIndex + 1 ; i < words.length ; i++ ) {
var word = words[i];
var re = /\d/;

if (!re.test(word)){
if (i === parenthIndex + 1) {
dest+= word;
}
else {
dest += " " + word;
}
}
else {
return dest;
}
}
}

/*
Take array and add flight objects by looping through
each paragraph and grabbing each property value we're interested in.
*/

var flights = [];

for( var i = 0 ; i < paragraphs.length ; i++ ) {

var paragraph = paragraphs[i];

var words = paragraph.split(" ");

/* Now we find the flight number which is the 1st and 2nd word */

var flightCode = words[0] + " " + words[1];
var flightCodeConden = words[0] + words[1];

var airlineName = getAirlineName();

var destAbbrev = getDestAbbrev();

var dest = getDest();

flights[flightCodeConden] = {
"flightCode" : flightCode,
"airlineName" : airlineName,
"destAbbrev" : destAbbrev,
"dest" : dest
};

}

console.log(flights);
}
};

-
maybe you're doing it like this for a particular reason? You could simplify a lot using slice and join methods on words. –  Stuart Dec 22 '12 at 2:19

The individual flights here are good candidates for being individual objects, along the following lines. I take a slightly different approach of first identifying the index of the flight code and the index of the date, and then using that to parse all the other information using words.slice. That simplifies things so much you don't have to worry about passing indices around between different functions (though if you did need to do that as your parser gets more complicated, you could do so by making the relevant indices properties of the Flight object).

function Flight(text) {
var ch, i, words = text.split(' '), parenthIndex, dateIndex;
for (i = 3; i < words.length; i++) {
ch = words[i].charAt(0);
if (ch === "(") {
parenthIndex = i;
}
else if (ch >= '0' && ch <= '9') {
dateIndex = i;
break;
}
}
this.airlineName = words.slice(2, parenthIndex).join(' ');
this.destAbbrev = words[parenthIndex];
this.dest = words.slice(parenthIndex + 1, dateIndex).join(' ');
this.code = words[0] + ' ' + words[1];
this.id = words[0] + words[1];
}

Then in your extractFlights function you only need the following, to break the text down into individual lines and send them to new Flight objects to be parsed.

extractFlights: function() {
var paragraphs = this.text.split("\n"), flights = {}, f, p;
while (p = paragraphs.pop()) {
f = new Flight(p);
flights[f.id] = f;
}
console.log(flights);
}

(fiddle)

-
Can you explain your while loop in extractFlights? Did you mean to check for equality instead of assigning p to paragraphs.pop()? –  mcabrams Dec 27 '12 at 0:03
I just ended up using a for loop: for (var i = 0; i < paragraphs.length; i++) { p = paragraphs.pop(); f = new Flight(p); flights.push(f); } –  mcabrams Dec 27 '12 at 0:05
Your for loop is a more transparent way of doing the same thing. The while statement assigns the last value in paragraphs to p and removes it from paragraphs; when paragraphs is empty it returns undefined and so the loop stops. It's just a nice way of looping though all the values of an array when you don't care if the array gets destroyed in the process. –  Stuart Dec 27 '12 at 0:14


text:
# A belief propagation algorithm based on domain decomposition

This note provides a detailed description and derivation of the domain decomposition algorithm that appears in previous works by the author. Given a large re-estimation problem, domain decomposition provides an iterative method for assembling Boltzmann distributions associated to small subproblems into an approximation of the Bayesian posterior of the whole problem. The algorithm is amenable to using Boltzmann sampling to approximate these Boltzmann distributions. In previous work, we have shown the capability of heuristic versions of this algorithm to solve LDPC decoding and circuit fault diagnosis problems too large to fit on quantum annealing hardware used for sampling. Here, we rigorously prove soundness of the method.

## Authors

• 4 publications
• ### Assessment of image generation by quantum annealer

Quantum annealing was originally proposed as an approach for solving com...
03/15/2021 ∙ by Takehito Sato, et al. ∙ 0

• ### Benchmarking Quantum Hardware for Training of Fully Visible Boltzmann Machines

Quantum annealing (QA) is a hardware-based heuristic optimization and sa...
11/14/2016 ∙ by Dmytro Korenkevych, et al. ∙ 0

• ### Bayesian machine learning for Boltzmann machine in quantum-enhanced feature spaces

Bayesian learning is ubiquitous for implementing classification and regr...
12/20/2019 ∙ by Yusen Wu, et al. ∙ 0

• ### Optimal Decomposition of Belief Networks

In this paper, optimum decomposition of belief networks is discussed. So...
03/27/2013 ∙ by Wilson X. Wen, et al. ∙ 0

• ### Restricted Boltzmann Machine Assignment Algorithm: Application to solve many-to-one matching problems on weighted bipartite graph

In this work an iterative algorithm based on unsupervised learning is pr...
04/30/2019 ∙ by Francesco Curia, et al. ∙ 0

• ### Leveraging Adiabatic Quantum Computation for Election Forecasting

Accurate, reliable sampling from fully-connected graphs with arbitrary c...
01/30/2018 ∙ by Maxwell Henderson, et al. ∙ 0

• ### Annealing Gaussian into ReLU: a New Sampling Strategy for Leaky-ReLU RBM

Restricted Boltzmann Machine (RBM) is a bipartite graphical model that i...
11/11/2016 ∙ by Chun-Liang Li, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## I Introduction

In our previous work bian2014discrete ; bian2016mapping , we explored methods to decompose constrained optimization problems into subproblems that could be solved on quantum annealing hardware, where the individual solutions can then be reassembled into a solution of the whole problem. We have used the term domain decomposition to represent any of a number of heuristic belief propagation-like algorithms to do this. In bian2014discrete

, we created a variant of the min-sum algorithm to solve LDPC decoding problems with more variables than qubits available on the available hardware. In

bian2016mapping , we created a sum-product style algorithm that solved fault diagnosis problems too large to fit on the hardware directly.

While ultimately successful in solving these problems, the versions of the domain decomposition method used in those works was heuristic: there was no guarantee that the object formed by reassembling the solutions on each subproblem was in any way related to the original problem. The goal of this note is provide a mathematical proof of the soundness of a specific domain decomposition algorithm (Algorithm 1) formed by balancing “free energy flow” between subproblems. In §2 we review the well known relationship between the Boltzmann distribution, Helmholtz free energy, and belief propagation algorithm. In §3 we develop the notion of a regional approximate free energy analogous to the Bethe free energy. In §4 we examine the free energy of a single region and show that when the free energy between regions is balanced, a critical point for the regional approximate free energy is obtained (Theorem 3). We then given an explicit statement for the domain decomposition algorithm (Algorithm 1) and prove that a stationary point for this algorithm is such a critical point (Theorem 5).

Like belief propagation there is no guarantee that the domain decomposition algorithm converges. In the case of belief propagation failure to converge is often attributed to a lack of convexity of the Bethe approximate free energy stemming from loops in the factor graph. Several sufficient conditions for convergence have been based on this observation tatikonda2002loopy ; heskes2003stable ; heskes2004uniqueness ; mooij2007sufficient ; watanabe2009graph ; watanabe2011uniqueness , and other forms of generalized belief propagation algorithms have been developed from convex bounds or treating convex and concave regions separately heskes2002approximate ; teh2002unified ; yuille2002cccp ; heskes2003approximate ; globerson2007approximate . While the algorithm we propose here is a significant departure from these methods, it is possible that one or more of these techniques could apply. We leave such explorations for future work.

Algorithm 1 relies on obtaining marginals of Boltzmann distributions along certain “boundary” variables. While the intent was to empirically estimate these using a dedicated device that produces Boltzmann samples, these marginals could also be computed by any number of other means such as simulated annealing or even belief propagation. It would be interesting to see if domain decomposition using—say—simulated annealing to compute these marginals could outperform belief propagation by carefully designing regions that internalize many of the loops in the factor graph, and so reduce the nonconvexity of the free energy approximation.

## Ii Free energy and belief propagation

Belief propagation pearl2014probabilistic

is an iterative method to approximate posterior marginal distributions of a constrained optimization problem given observations. The most common version of belief propagation, the sum-product algorithm, can derived in a straightforward manner by carefully tracking conditional probabilities and making suitable independence assumptions; for a concise presentation see

kschischang2001factor . Such algorithms, including various variants of belief propagation, can be viewed as a type of generalized distributive law on semirings aji2000generalized .

Our starting point is the variational approach to Bayesian re-estimation, yedidia2000generalized ; aji2001generalized ; yedidia2001bethe ; pakzad2002belief ; yedidia2003understanding ; yedidia2005constructing : the Bayesian posterior distribution is a critical point of a Helmholtz free energy constructed from the given problem. Specifically, given a space of configurations, let us write our target probability as a Gibbs state based on the product of problem dependent factors

 p0(x)=1Zm∏α=1fα(x)=1Z(T)e−∑mα=1Eα(x)/kT, (1)

where each factor term contributes an energy to the total energy

. The Helmholtz free energy of an ensemble with probability distribution

is

 A(p)=U(p)−TH(p)=∑x∈Ωp(x)E(x)+kT∑x∈Ωp(x)logp(x).

From (1) above one can write

 E(x)=m∑α=1Eα(x)=−kT(logp0(x)+logZ(T)).

Inserting this into the above equation,

 A(p) = = −kTlogZ(T)+kT∑xp(x)log(p(x)p0(x)) = −kTlogZ(T)+kTDKL(p∥p0).

, with equality if and only , and therefore the posterior is the global minimum of this Helmholtz free energy.

Decomposing the Helmholtz free energy as

 A(p)=U(p)−TH(p)=∑x∈Ωm∑α=1p(x)Eα(x)+kT∑x∈Ωp(x)logp(x),

one sees each factor contributes an energy term to the internal energy. Let us assume that the energies are “local.” We do not want to be too formal about this; simply, we assume the configurations in our space all have the form and that each does not depend on all the variables , but rather only a few of them. Let us introduce the notation

• to mean (through ) depends nontrivially on ,

• for the support of , and

• for the domain of the vector

.

The marginal distribution with respect to one of these supports is (the notation refers to the “belief” and hence “belief propagation”). The internal energy then has the form

 ∑x∈Ωp(x)Eα(x)=∑xα∈Ωαbα(xα)Eα(xα).

That is, the internal energy is linear in the sense that

 U(p)=∑x∈Ωm∑α=1p(x)Eα(x)=m∑α=1∑xα∈Ωαbα(xα)Eα(xα)=m∑α=1Uα(bα).

At this point it is natural to disassociate the beliefs with the marginals of and pose a local free energy associated to each factor (for which we will reuse the name for its argument)

 Aα(bα)=Uα(bα)−TH(bα)=∑xαbα(xα)Eα(xα)+kT∑xαbα(xα)logbα(xα).

The main problem lies in “localizing” the entropy term. The sum of the factors’ local free energies does not recover the Helmholtz free energy partially because of the nonlinearity inherent in the entropy, but mostly because one has grossly over-counted entropy contributions from factors sharing common variables. To illustrate this by a simple example, suppose and is uniform; form the marginals

 b1(x2,x3)=∑x1∈Ω1p(x1,x2,x3) and b2(x1,x3)=∑x2∈Ω2p(x1,x2,x3),

which are also uniform. Then

 H(p)=klog|Ω|=k(log|Ω1|+log|Ω2|+log|Ω3|).

and

 H(b1)=k(log|Ω2|+log|Ω3|) and H(b2)=k(log|Ω1|+log|Ω3|).

Therefore over-counts the entropy by simply because in the support of each belief.

The Bethe approximation overcomes this failure by correcting the entropy count at each variable. For each variable let us write , the number of factors involving this variable. Removing extra entropy through over counting gives

 ABethe = m∑α=1[∑xα∈Ωαbα(xα)Eα(xα)+kT∑xα∈Ωαbα(xα)logbα(xα)] (2) + kTn∑j=1⎛⎝(1−Cj)⋅∑xj∈Ωjbj(xj)logbj(xj)⎞⎠.

There is some freedom to use different weights to correct the entropy contributions, which leads to variants of the sum-product algorithm wiegerinck2003fractional ; weller2015bethe . We will only consider the Bethe approximation as given above.

Here, the “ensemble” of the Bethe approximate free energy is a collection of beliefs , one for each factor and variable. The target posterior distribution minimizes the Helmholtz free energy, so it is not unreasonable to attempt to approximate this posterior with the minimum of the Bethe approximation. However, the minimum of the Helmholtz free energy is taken over global probability distributions, while the Bethe approximation is a function of disjoint beliefs. To rectify this, one adds consistency constraints on the beliefs so to make them marginals of a single distribution:

• and , and

• whenever we require .

Enforcing these conditions with Lagrange multipliers produces a constrained Bethe approximate free energy:

 ~ABethe = m∑α=1[∑xα∈Ωαbα(xα)Eα(xα)+kT∑xα∈Ωαbα(xα)logbα(xα)] + kTn∑j=1⎛⎝(1−Cj)⋅∑xj∈Ωjbj(xj)logbj(xj)⎞⎠ + m∑α=1λα(∑xα∈Ωαbα(xα)−1)+n∑j=1λj⎛⎝∑xj∈Ωjbj(xj)−1⎞⎠ + m∑α=1∑j≺α∑xj∈Ωjλjα(xj)⎛⎜⎝∑xα∖xjbα(xα)−bj(xj)⎞⎟⎠.

We find relations at interior critical points of by setting various derivatives to zero. The derivatives with respect to the multipliers simply recover the constraints when set to zero. The two nontrivial types of derivatives are

 ∂~ABethe∂bα(xα) = Eα(xα)+kT(logbα(xα)+1)+λα+∑j≺αλjα(xj), and ∂~ABethe∂bj(xj) = kT(1−Cj)(logbj(xj)+1)+λj−∑α≻jλjα(xj).

Setting the first of these to zero produces the equation

 bα(xα)=e−(1+λα/kT)e−Eα(xα)/kT∏j≺αe−λjα(xj)/kT.

In particular, at a critical point the multiplier can be selected, and is completely determined by, the normalization constraint . So, we are free to work with unnormalized, for which we have

 bα(xα)∝fα(xα)⋅∏j≺αe−λjα(xj)/kT (3)

at any interior critical point. Similarly, the second type of derivative above produces the relation

 bj(xj)∝∏α≻je−λjα(xj)/kT(Cj−1) (4)

at an interior critical point, where now is selected, and determined by, the normalization of .

The remaining constraints are the consistency of the marginals. Computing the marginal using (3) one finds the additional relations on each :

 bj(xj)∝e−λjα(xj)/kT⋅∑xα∖xjfα(xα)∏r≺α∖je−λrα(xj)/kT.

We define the function

 Mα→j(xj)∝∑xα∖xjfα(xα)∏r≺α∖je−λrα(xj)/kT,

with the condition . One can simplify the above relation to

 bj(xj)∝e−λjα(xj)/kT⋅Mα→j(xj). (5)

Note the trivial equation

 ∏β≻j:β≠αbj(xj)=bj(xj)Cj−1,

which is just a restatement of the definition of . Now, we evaluate the left side of this equation using (5) and the right side using (4). This results in the relation

 ∏β≻j:β≠αe−λjβ(xj)/kT⋅Mβ→j(xj)∝∏β≻je−λjβ(xj)/kT.

Canceling common terms from both side leaves

 e−λjα(xj)/kT∝∏β≻j:β≠αMβ→j(xj). (6)

Now we define the function

 Mj→α(xj)∝e−λjα(xj)/kT,

where as before we require to be a probability distribution.

###### Proposition 1.

Suppose that for each variable and factor with one has two probability distributions, and , which jointly satisfy

 Mα→j(xj) ∝ ∑xα∖xjfα(xα)∏k≺α∖jMk→α(xk), and Mj→α(xj) ∝ ∏β≻j:β≠αMβ→j(xj).

Then the probability distributions and satisfying

 bα(xα) ∝ fα(xα)⋅∏j≺αMj→α(xj), and bj(xj) ∝ ∏α≻jMα→j(xj),

are critical points of the Bethe approximate free energy with

 ∑xα∖xjbα(xα)=bj(xj), % whenever j≺α.

This result hands us the sum-product algorithm. We initialize distributions and in a reasonable way (which will be problem dependent) and iteratively redefine these as in the proposition:

 M(t+1)α→j(xj) ∝ ∑xα∖xjfα(xα)∏k≺α∖jM(t)k→α(xk), and M(t+1)j→α(xj) ∝ ∏β≻j:β≠αM(t+1)β→j(xj).

The proposition shows that if this converges to a stationary point, that point is a critical point of the Bethe approximate free energy and so may be taken as an approximation of the Bayesian posterior.

In practice, one has a class of factors that depend only a single variable

; these typically arise as prior probabilities in a re-estimation problem. Let us write

in this case. Since is vacuous, we have

 M(t){j}→j(xj)∝f{j}(xj)

for all and hence there is no need to compute these. One can then simplify

 M(t+1)j→α∝f{j}(xj)⋅∏β≻j:β≠α,{j}M(t+1)β→j(xj).

Since for , one can also eliminate all factors arising from priors and use this last rule as the update rule at such nodes.

In most problems, one is primarily interested in the marginals

, as these are the posterior probabilities one wishes to compute by re-estimation. From (

4) these satisfy

 bj(xj)∝∏α≻je−λjα(xj)/kT(Cj−1)∝e−(∑α≻j(λjα(xj)/(Cj−1)))/kT.

That is, is the Gibbs state associated to the energy spectrum given by normalized Lagrange multipliers . In particular, the posterior marginal is itself the minimum of the Helmholtz free energy

 Aj(bj)=∑α≻j∑xj∈Ωjbj(xj)λjα(xj)/(Cj−1)+kT∑xj∈Ωjbj(xj)logbj(xj).

## Iii Regional approximate free energies

The presentation of the Bethe approximate free energy of the previous section was a purposefully unusual. Let us return to this construction, but rather than focus on the energies of single factors let us construct “regions” containing multiple factors. We introduce the notation for a region of factors . Without loss of generality, we will assume that to every variable there is a factor . As noted at the end of the previous section, we can treat priors differently and so not include them in any of the regions. To be precise, all the factors that are not priors are partitioned into regions and the prior factors are treated individually. We hasten to indicate that unlike the usual approach to regional belief propagation algorithms yedidia2000generalized ; aji2001generalized ; pakzad2002belief , we do not use a hierarchy of regions and the Kukuchi free energy approximation. Here we simply organize our factors in a different way and use the Bethe approximation above.

We extend the notation to , meaning the collection of variables for which depends nontrivially; we also write or when is one of these variables. Each region has internal energy

 UR(bR)=∑xRbR(xR)ER(xR),

where we have defined . Similarly, if is the energy associated to the prior , the internal energy at the variable is

 Uj(bj)=∑xjbj(xj)Ej(xj).

When and are obtained by marginalizing a global probability , the internal energy of the whole system is

 U(p)=∑RUR(bR)+∑jUj(bj).

Exactly at in the Bethe method, define the weight

 Cj=#{R:R≻j},

and the constrained regional approximate free energy:

 ~Aregional = ∑R(∑xRbR(xR)ER(xR)+kT∑xRbR(xR)logbR(xR)) + ∑j(∑xjbj(xj)Ej(xj)−kT(Cj−1)∑xjbj(xj)logbj(xj)) + ∑R∑j≺R∑xjλjR(xj)⎛⎜⎝∑xR∖xjbR(xR)−bj(xj)⎞⎟⎠.

By a similar argument, setting the derivative with respect to to zero yields

 bR(xR)∝fR(xR)⋅∏j≺Re−λjR(xj)/kT. (7)

One finds the analysis of the derivative with respect to splits into two cases. First if (when the variable is internal to one region) one obtains

 ∂~Aregional∂bj(xj)=Ej(xj)+λj−λjR(xj),

where is the region that contains . By setting this to zero and exponentiating, we find

 e−λjR(xj)/kT∝fj(xj).

However for variables contained in multiple regions (which we call boundary variables) one finds

 ∂~Aregional∂bj(xj)=Ej(xj)−(Cj−1)kT(logbj(xj)+1)+λj−λjR(xj).

Setting this derivative to zero produces the relation

 bj(xj)∝(fj(xj))−1/(Cj−1)⋅∏R≻je−λjR(xj)/kT(Cj−1). (8)

The variables forming the support of a region divide into boundary variables (denoted ) and the remainder which we call interior (denoted ). Computing the marginal of the belief in (7) at a boundary variable yields the relation

 bj(xj)∝e−λjR(xj)/kT∑xR∖xjfR(xR)∏r≺R∖je−λrR(xr)/kT.

Note that in this product, runs over all variables. For variables in we know . Based on this we define the augmented regional factor as the usual factor for that region times the priors for all its internal variables:

 ~fR(xR)=fR(xR)⋅∏r≺R∘fr(xR).

As ,

 bj(xj)∝e−λjR(xj)/kT∑xR∖xj~fR(xR)∏r≺∂R∖je−λrR(xr)/kT.

 MR→j(xj)=∑xR∖xj~fR(xR)∏r≺∂R∖je−λrR(xr)/kT

so that

 bj(xj)∝e−λjR(xj)/kTMR→j(xj). (9)

Except for the fact that one deals only with messages to and from boundary variables, the arguments of the previous section apply. For a fixed region one has

 ∏S≻j:S≠Rbj(xj)=bj(xj)Cj−1.

Evaluating the left and right sides with equations (9) and (8) respectively gives the relation

 ∏S≻j:S≠Re−λjS(xj)/kTMS→j(xj)∝fj(xj)−1⋅∏S≻je−λjS(xj)/kT.

Canceling common terms produces the analogous result:

 Mj→R(xj)∝e−λjR(xj)/kT∝fj(xj)⋅∏S≻j:S≠RMR→j(xj).
###### Proposition 2.

Suppose that for each region and variable with one has two probability distributions, and , which jointly satisfy

 MR→j(xj) ∝ ∑xR∖xj~fR(xR)∏r≺∂R∖jMr→R(xr), and Mj→R(xj) ∝ fj(xj)⋅∏S≻j:S≠RMS→j(xj).

Then the probability distributions and satisfying

 bR(xR) ∝ ~fR(xR)⋅∏j≺∂RMj→R(xj), and bj(xj) ∝ fj(xj)⋅∏R≻jMR→j(xj),

are critical points of the regional approximate free energy with

 ∑xR∖xjbR(xR)=bj(xj), whenever j≺∂R.

Note that this proposition yields a generalized belief propagation algorithm. However this algorithm becomes impractical as the size of the regions increases. With large regions, there is potentially far fewer variables for which we need to compute messages. However the marginalization over becomes intractable.

## Iv Modified free energy of a single region

In the previous section we developed a regional belief propagation algorithm that rapidly becomes inefficient as the size of regions get large. However, if we assume we have access to a device that samples from the Boltzmann distribution, can this capability aid us in computing—or at least in approximating—these marginals?

Given a regional decomposition as in the last section, the Helmholtz free energy of the factors of a single region is given by

 AR(bR)=∑xRbR(xR)(ER(xR)+∑j≺REj(xj))+kT∑xRbR(xR)logbR(xR).

Unless is isolated from the rest of the system one would not expect that minimizing would produce a result related to our desired posterior distribution. Nonetheless, we argue as follows. At the minimum of the free energy, the outgoing message represents the flow out of variable into region . The (change in) free energy associated to this is

 ASj(bj)=∑xjbj(xj)λjS(xj)+kTbj(xj)logbj(xj).

At each variable in we compensate for this expected flow. This produces the modified free energy of the region , defined as

 AR(bR)−∑j∈∂R⎛⎝∑S≻j:S≠RASj(bj)⎞⎠.

As with the Bethe approximation, we add appropriate marginalization constraints, to obtain the constrained modified free energy

 ~AR = ∑xRbR(xR)~ER(xR)+kT∑xRbR(xR)logbR(xR) + ∑j≺∂R∑xjbj(xj)VRj(xj)−kT(Cj−1)∑xjbj(xj)logbj(xj) + λR(∑xRbR(xR)−1)+∑j≺∂RλRj(∑xjbj(xj)−1) + ∑j≺∂R∑xjλjR(xj)⎛⎜⎝∑xR∖xjbR(xR)−bj(xj)⎞⎟⎠,

where

 ~ER(xR)=ER(xR)+∑j≺R∖∂REj(xj)

and for ,

 VRj(xj)=Ej(xj)−∑S≻j:S≠RλjS(xj).

Note the the definition of involves the Lagrange multipliers of the constrained modified free energy of adjacent regions.

Adding these local “corrective” potentials could be viewed as a form of hybrid mean field approach riegler2013merging , however the values of the potential are unknown. Nonetheless, like the cavity method mooij2007loop , if the corrective potentials are set as indicated above then the minima of each regional free energy do minimize the global approximate free energy.

###### Theorem 3.

A joint interior critical point of each modified regional free energy defines a critical point of the regional approximate free energy.

###### Proof.

Just as above we compute an interior critical point of each region’s constrained modified free energy, yielding

 ~ER(xR)+kT(logbR(xR)+1)+λR+∑j≺∂RλjR(xj) = 0, VRj(xj)−(Cj−1)kT(logbj(xj)+1)+λRj−λjR(xj) = 0.

Now using these become

 bR(xR) ∝ ~fR(xR)⋅∏j≺∂Re−λjR(xj)/kT bj(xj) ∝ f(xj)1/(1−Cj)⋅∏S≻je−λjS(xr)/kT(Cj−1).

These are precisely the relations of a critical point of the regional approximate free energy. ∎

Finally we can tackle the question of how to utilize a modest sized device or method that can produce Boltzmann samples. Suppose that: given an arbitrary selection of corrective potentials , we have a black box that produces an interior minimum of each region’s modified regional free energy. Then: we instantiate Algorithm 1 below. Note that in this algorithm it is only the marginals of the Boltzmann distribution that are required. With the ability to do Boltzmann sampling from physical hardware (or by other means), we approximate these marginals in each region by drawing a sufficiently large number of samples and estimating the marginal probabilities empirically. Specifically, we decompose our large re-estimation problem into regions small enough for our Boltzmann sampler to handle, and use the sampler on each region to approximate the marginals of Algorithm 1. By Theorem 5 below, if the algorithm converges then it recovers the approximate posterior.

The numerical results presented in bian2014discrete ; bian2016mapping indicate that these approximations can be sufficient to solve problems too large to be sampled directly. In bian2014discrete we used a variant of Algorithm 1 based on the min-sum method to solve 1000 variable LDPC decoding problems on a 504 qubit D-Wave quantum annealer for which belief propagation failed to converge. In bian2016mapping we implemented a slight variant of Algorithm 1 to solve hardware fault diagnosis problems requiring up to seven regions to completely embed on a D-Wave 2X architecture.

###### Lemma 4.

If Algorithm 1 converges then the marginal at any boundary variable is independent of the region used to compute it.

###### Proof.

For any boundary variable and region , if the algorithm has converged then steps 5 and 6 of the algorithm show

 ∑xR∖xjbR(xR)∝Fj→R(xj)⋅FR→j(xj)∝fj(xj)⋅∏S≻jFS→j(xj),

which is independent of . ∎

###### Theorem 5.

If Algorithm 1 converges then the collection of minima of each region’s modified regional free energy from step 4, and their marginals , produces a critical point of the approximate regional free energy of the whole system.

###### Proof.

For an arbitrary selection of corrective potentials , the critical point of the constrained modified free energy satisfies

 bR(xR) ∝ ~fR(xR)⋅∏j≺∂Re−λjR(xj)/kT b(R)j(xj) ∝ eVRj(xj)/kT(Cj−1)⋅e−λjR(xj)/kT(Cj−1).

Therefore at a critical point,

 bR(x