text:
# Highly stable, nanotube-enhanced CMOS-MEMS thermal emitter for mid-infrared gas sensing | Scientific Reports

2021-11-25 10:30:27 By : Ms. Kathy Huang

Thank you for visiting Nature. The browser version you are using has limited support for CSS. For the best experience, we recommend that you use a newer version of the browser (or turn off the compatibility mode in Internet Explorer). At the same time, to ensure continued support, we will display sites without styles and JavaScript.

Driven by many socio-economic and industrial factors, the gas sensor market is growing rapidly. Mid-infrared (MIR) gas sensors provide outstanding performance for a growing number of sensing applications in the healthcare, smart home, and automotive industries. Obtaining a low-cost, miniaturized, and energy-saving light source is essential for the monolithic integration of MIR sensors. Here, we show an on-chip broadband thermal mid-infrared source manufactured by combining a complementary metal oxide semiconductor (CMOS) microthermal plate with a dielectric encapsulated carbon nanotube (CNT) black body layer. The micro-hot plate is used as a micro-reactor in the manufacturing process to promote the high temperature (>700 $$^{\circ}$$C) growth of the CNT layer, and is also used for thermal annealing after growth. We have demonstrated for the first time the stable extended operation of a device with a dielectric encapsulated CNT layer in the air at a heater temperature higher than 600 $$^{\circ }$$ C. The displayed device exhibits almost uniform emissivity in the entire MIR spectrum, providing an ideal solution for the low-cost, highly integrated MIR spectrum of the Internet of Things.

Driven by many scientific, industrial and commercial applications, gas sensors are at the center of ever-increasing research and development efforts. This includes monitoring environmental pollutants from deforestation2, vehicles and industry3, and air quality in buildings4. People are becoming more aware of the impact of air pollution on human health3, leading to increased demand for low-cost, accessible, compact, and easy-to-deploy air quality monitoring5. In order to maintain emerging global demand, gas sensors must find a suitable and challenging balance between performance and cost1. In addition to being economically feasible, more and more sensors have strict power and size constraints1, such as those deployed in the Internet of Things (IoT)6 and mobile platforms7. These requirements have prompted researchers to explore new materials, designs, and technologies to achieve component miniaturization, monolithic integration, low cost, low power consumption, and manufacturability1.

Among various sensing technologies, optical gas sensors have many advantages in terms of selectivity and long-term operational stability1. It is worth noting that non-dispersive infrared (NDIR) sensors currently dominate the carbon dioxide (CO$$_2$$) gas sensor market and also serve many other applications8. However, although NDIR gas sensors have inherent advantages (for example, for spectral sensing), they are currently mainly used to detect a single analyte or several substances at the same time. One limitation of wider adoption is the availability of low-cost and optically efficient small broadband mid-infrared light sources (arguably the core of optical gas sensors)1. Traditionally, light bulb-based heat sources have been used, but they are fragile, bulky, and limited in optical efficiency at wavelengths above 5 $$\upmu$$ m. Light-emitting diodes (LEDs) provide higher integration and reliability, but due to the use of professional III-V semiconductor technology, the manufacturing cost is higher9.

Using standard complementary metal oxide semiconductor (CMOS) processes is an attractive way to manufacture low-cost integrated thermal mid-infrared sources and detectors, and has led to many innovative devices based on microelectromechanical systems (MEMS) 1,10. Various techniques have been proposed to improve the emissivity/absorption rate of CMOS-MEMS thermal devices1, including the use of a carbon nanotube (CNT) adsorption layer to provide near-unit broadband emissivity 11, 12, or plasma for specific mid-infrared bands Body metamaterials 13,14. Multi-species spectroscopy detection requires the MIR source to operate under the set of target MIR bands, so that the overall CNT broadband emission enhancement 11,12 is attractive for spectroscopy. However, despite their blackbody-like advantages15,16, so far, most studies have observed such CNTs, and generally all graphite nanocarbon adsorption layers burn out in the air when operating at temperatures above 400 ℃ $$^{\circ }$$ C17,18. This imposes limitations (light emission and operational stability) for its integration into CMOS MEMS micro hot plate MIR sources (usually operating at these temperatures). Although inert gas can be used to prevent CNTs from burning out, this requires the use of special sealed ceramic or metal packaging, which will significantly affect the cost20,21.

Here, we propose a solid-state method based on a dielectric encapsulation method that can achieve long-term operational stability of CNT-coated thermal emitters. We show that aluminum oxide (Al$$_2$$ O$$_3$$) encapsulated carbon nanotubes grown on MEMS micro hot plates can withstand more than 800 when operating in air. $$^{\circ }$$ The temperature of C. The packaged CNT adlayer has a nearly uniform emissivity (reference standard MEMS device, $$\sim$$ increased by 8 times), and stable operation for 10 days under 600 $$^{\circ }$$ C. This work It paves the way for packaging technology to be more widely used in temperature and air-sensitive nanomaterials, enabling them to operate stably in the air, well above their normal temperature threshold.

Equipment manufacturing. (a) Cross section of micro hot plate using tungsten (W) heating element embedded in $$\sim$$ 5 $$\upmu$$ m thick silicon dioxide (SiO$$_2$$) (not to scale) Film formed by deep reactive ion etching. (b) The optical image of the micro hot plate, showing the heating element of the multi-ring design surrounded by the film. Chip size = 1.76 mm $$\times$$ 1.76 mm. (c) Micro heater temperature as a function of power consumption. (d) Active heating elements have three purposes: (i) Local in-situ heating during CNT growth (microreactor); (ii) Used as a thermal analyzer for self-annealing (adlayer flashing); (iii) Used in IR emission is generated during equipment operation (usually at a temperature of 300–600 $$^{\circ }$$ C). (e) Typical SEM image of spaghetti-like CNT structure grown by in-situ CVD process using acetylene (C$$_2$$ H$$_2$$) mixed with ammonia (NH$$_3$$) on iron (Fe) catalyst, and (f) SEM image of $$\sim$$ 50 nm alumina (Al$$_2$$ O$$_3$$) after packaging. (e) SEM images of denser and more aligned CNTs synthesized by mixing C$$_2$$ H$$_2$$ and hydrogen (H$$_2$$ ), and (h) SEM images after packaging .

For our experiment, we use an in-house designed micro electric furnace manufactured in a commercial foundry. The cross section of the micro hot plate is shown in Figure 1a. It consists of a silicon dioxide (SiO$$_2$$) film (1200 $$\upmu$$ embedded in $$\sim$$ 5 $$\upmu$$ m thick m diameter) to ensure low direct current (DC) power consumption19. Compared with doped polysilicon or aluminum, W was chosen as the heating element and interconnect metal because of its excellent electromigration resistance and higher glass transition temperature10,19. The micro heating plate adopts CMOS-SOI (Silicon-on-Insulator) technology, with a monolithic integrated monocrystalline silicon thermal diode, which can operate linearly with high precision at a recording temperature of up to 600 $$^{\circ }$$ C22. When the micro heating plate is used as an IR transmitter, the thermal diode can be used as an accurate temperature sensor, and the resolution is allowed to be less than 0.5 $$^{\circ }$$ C during calibration. For CNT growth and operation above 600 $$^{\circ }$$ However, it is better to use W heater as resistance temperature detector (RTD). W has a large and stable temperature coefficient of resistance (TCR) ($$\sim$$ 4.5 $$\times$$ 10$$^(-3)$$ K$$^(-1)$$) and has been Prove that it can be run with relatively high accuracy under 1000 $$^{\circ }$$ C $$\sim$$ 2 $$^{\circ }$$ C19. The micro hot plate can reach a temperature of more than 700 $$^(\circ )$$ C and has a fast thermal transient time> 4 $$\times$$ 10$$^4$$ $$^{\circ }\ ) C/s, to achieve voltage-controlled thermal ramp and stable MIR emission at a very low cost, with excellent reproducibility10,19. The optical image of the micro heating plate we made shows the heating element surrounded by the film, as shown in Figure 1b. We use in-situ chemical vapor deposition (CVD) process to integrate CNT adlayer11,12. The CVD process usually requires a substrate temperature of more than 400 \(^{\circ }$$ C23,24, which is incompatible with CMOS because temperature effects can damage integrated circuits (for example, due to accelerated alloying and atom migration)10. Due to the thermal isolation provided by the thin dielectric film, our micro hot plate can easily reach a temperature of more than 750 $$^{\circ }$$ C (Figure 1c) in the local "hot zone" without affecting the functional chip substrate The peripheral CMOS circuit on the board is only a few microns away from the hot zone. Therefore, our micro hot plate can be effectively used as an ideal CMOS compatible microreactor, allowing viable CNT-CMOS integration at the wafer level12. In addition, our design allows relatively low DC power consumption to achieve such a high temperature (for example, $$\sim$$ 100 mW at 500 $$^{\circ }$$ C, as shown in Figure 1c), which It can be further minimized by using a modulated drive signal (for example, 50% duty cycle in our case). In order to test the packaging efficiency, we used two commonly used process gases, ammonia (NH$$_3$$ )12 and hydrogen (H$$_2$$ )11, which are the same as the carbon-containing gas [acetylene (C$$_2$$ H$$_2$$ )], in the iron (Fe) catalyst process. As reported elsewhere in the CNT synthesis literature, the use of NH$$_3$$ tends to produce more spaghetti-like nanotube bundles 12, while the use of H$$_2$$ produces more spatially dense, vertical arrangements. The nanotube 11 thus provides us with a comprehensive test platform for our experiments (the influence of CNT crystallography and morphology). NH$$_3$$ :C$$_2$$ H$$_2$$ The optical image of the synthesized CNT sample is shown in Figure 1d. Scanning electron microscope (SEM) examination confirmed the successful growth of spaghetti-like (Figure 1e) and vertically aligned (Figure 1g) nanotube forests.

Characterization and stability testing in the air. (a) The infrared absorption spectrum of the uncoated micro heating plate (black line) compared to the CNT coated plate (red line) that absorbs almost all light. (b) Measure the emission spectra of the uncoated (black line), CNT-coated (blue line) and encapsulated (red line) micro hot plates at 600 $$^{\circ }$$ C. Compared with uncoated devices at the same temperature, CNT-coated devices show a $$\sim$$ 8-fold increase in emission. However, unencapsulated CNTs will burn within a few minutes, causing their The emission spectrum (blue line) drops from the initial value close to the packaged device (red line) to the uncoated device (black line). Optical inspection (inset) showed that the carbon nanotubes were almost completely burned. (c) The emission spectrum measured at 600 $$^{\circ }$$ C in 10 days, for the device packaged with NH$$_3$$: C$$_2$$ H$$_2$$ -synthetic CNT (as shown in Figure 1f). The optical images recorded at various times show that the packaged CNTs are not affected by high-temperature operation. After running at 850 $$^{\circ }$$ C for 4 hours at a higher temperature, the optical image of the test sample is displayed in the lower right corner, showing that the CNT is intact. (D) (bottom two lines) Raman spectra measured at 532 nm before and after the operational stability test shown in (c). For comparison, the two lines at the top show the same test (not shown) measurement performed on the CNT synthesized using H$$_2$$ :C$$_2$$ H$$_2$$ (shown in Figure 2) Raman spectroscopy. 1h) In contrast, it shows that both samples remain stable.

As we all know, carbon nanotubes burn in air at a temperature higher than 400 $$^{\circ }$$ C (usually within a few minutes), depending on their diameter, number of walls or number of defects17,18, Therefore, their application as thermal emitters is hindered. In order to isolate the CNTs exposed to the air from oxidation 17, 18 and create a thermally stable emitter interface, we encapsulated the grown CNTs in $$\sim$$ 50 nm Thick deposited atomic layer (ALD) Al$$_2$$ O$$_3$$ coating. The package based on Al$$_2$$ O$$_3$$ guarantees high thermomechanical stability, and has been proven to have the ability to operate at temperatures higher than 500 $$^{\circ }$$ C, and at the same time proved Good oxygen (O$$_2$$) and water (H$$_2$$ O) 25,26 barriers. Figure 1f,h shows the SEM images of CNT (spaghetti-like NH$$_3$$ :C$$_2$$ H$$_2$$ synthesis) and g (aligned) shown in Figure 1e after packaging. (_2\) :C$$_2$$ H$$_2$$-combine separately). In order to improve the thermal stability after packaging, we used the equipment self-annealing 26,27 process, in our case, it is activated by the micro heater itself. The thermal distribution is applied to the electric heating modulation in step C of $$\sim$$ 100 $$^{\circ }$$, and the temperature is as high as $$\sim$$ 800 $$^{\circ }$$ C; this makes the film The induced thermo-mechanical stress on the surface is consistent with the operating frequency, thereby avoiding membrane rupture.

The typical light absorption spectrum of our micro hot plate (see "Methods"), in the 2-14 $$\upmu$$ m band, as shown in Figure 2a (black line), the absorption peak is $$\ sim$$ 85% The characteristics of Si-O stretching vibration in the 8.5 $$\upmu$$ m; SiO$$_2$$ film28,29. In the same picture (red line), the micro heating plate with the in-situ grown NH$$_3$$ :C$$_2$$ H$$_2$$ CNT (Figure 1f) layer shows almost 100% absorption, This behavior is attributed to the black body-like nature of the CNT layer15,16. In order to study the emission characteristics of our uncoated, CNT coated and packaged devices, we implemented a temperature controller based on proportional integral derivative (PID), which can control the temperature of the self-heating micro hot plate at $$\sim$$ 0.5 \ Within (^{\circ }\) C resolution. The emission spectrum of the self-heating device was then measured by an MIR spectrometer (Bentham) (Figure 2b). For the packaged (NH$$_3$$ :C$$_2$$ H$$_2$$) sample, the representative spectrum recorded at 600 $$^{\circ }$$ C is shown in Figure 2b ( The red line), compared with the uncoated device (black line) operating at the same temperature, shows a $$\sim$$ 8 times emission enhancement. We also measured the emission spectra of the unencapsulated CNT-coated device. As expected, it exhibited a rapid ($$\sim$$ minute) emission reduction at elevated temperatures, which is the same as that of the CNT when exposed to air. In the middle, it will burn out unanimously 17. The sample spectrum is shown in Figure 2b (blue line), recorded at 600 $$^{\circ }$$ C after running for 10 minutes $$\sim$$. A visual comparison between the black and blue lines indicated that most of the CNTs had been burned, which was confirmed by visual inspection under a microscope (Figure 2b, inset).

In order to study the long-term operational stability of our packaged devices, we used normal indoor conditions [standard pressure (1010–1020 mbar), temperature (18–21 $$^{\circ }$$ C) and relative humidity (30–50%) )] At a temperature as high as 900 $$^{\circ }$$ C, it is significantly higher than the actual equipment operating temperature ($$\sim$$ 500–600 $$^{\circulation}$$ C). For the typical emission spectrum of the equipment running continuously for 10 days (regularly recorded every 24 hours) under 600 $$^{\circ }$$ C as shown in Figure 2c, where $$\sim$$ 3 \ (\times\ ) 10$$^{-5}$$ Variation in standard deviation, indicating excellent stability. An optical image recorded at a representative time during the test is also provided, which shows that the encapsulated CNT is physically unaffected by the high operating temperature. When up to 900 $$^{\ circ }$$ C. The optical image of the sample is displayed in the lower right corner of Figure 2c, and it is recorded after running in the air of 850 $$^{\circ }$$ C for 4 hours, and further shows The stability of physical carbon nanotubes at high temperatures is improved. It is worth noting that at such high temperatures, some films (not carbon nanotubes) will fail due to extreme thermally induced mechanical stress. The faulty device was analyzed through optical and SEM imaging, and the identified fault was attributed to film rupture, rather than burnt-out of the packaged CNT layer, and remained intact even under extreme temperatures. Similar film rupture at extreme temperatures was also observed using uncoated devices (no CNT layer). In order to check the quality of the encapsulated CNTs before and after the 10-day operation test, we used Raman spectroscopy to characterize them. Figure 2d (bottom two lines) plots the Raman spectrum of the above device. We did not observe any changes in the position, width and intensity of the D peak, indicating that long-term high temperature operation will not cause additional defects in the starting material30. As a comparison (see the first two lines), we also show the Raman spectrum of the same test run with CNT packaged with H$$_2$$ :C$$_2$$ H$$_2$$, showing good operation Stability of two samples, thus highlighting the wider application potential of our packaging technology.

Non-dispersive infrared (NDIR) experiment. (a) Schematic diagram of NDIR gas sensor setup. (b) The relative optical response recorded by the thermopile at 4.26 $$\upmu$$ m is used for uncoated (black line), CNT coated (blue dashed line) and encapsulated (red line) micro hot plates. At temperatures higher than 600 $$^{\circ }$$ C, the detected IR emission of the unpackaged device (blue dotted line) drops rapidly (minutes), consistent with the data provided in Figure 2b. (c) CO$$_2$$ The sensor response voltage has uncoated (black wire) and encapsulated (red wire) micro-heating plates respectively. For packaged CNT devices, it can be observed that $$\sim$$ relative voltage$$\Delta V=V_{0 ppm}-V_{lock-in}$$ has increased by 8 times.

In order to test the performance of our MIR transmitter in the application type setting, a custom NDIR gas sensor designed for CO$$_2$$ detection was used to benchmark samples against uncoated equipment. The schematic diagram of our experimental setup is shown in Figure 3a. We use our thermal emitter as the MIR light source, coupled to a single-channel thermopile detector (Heimann HMS-J21), integrated 4.26 $$\upmu$$ m filter tuned to the CO$$_2$$ absorption band. Both the emitter and the detector are installed in a custom-made gas chamber, and the length of the optical path between the emitter and the detector is 4 cm. The gas chamber is connected to the gas mixing system so that the CO$$_2$$ concentration ($$c_{CO_2}$$) can pass through the cylinder of dry air at 5$$\%$$. Our customized experimental device allows the CO$$_2$$ concentration to be controlled below 100 ppm, and the minimum controlled change in concentration is a few ppm. The relative optical signal recorded by the thermopile at room temperature (see "Methods") is shown in Figure 3b. CNT (NH$$_3$$ :C$$_2$$ H$$_2$$ synthesis) The response of the coated device (blue dotted line) and the packaged device (red line) to temperature rise is similar to $$\sim\ ) 600 \(^{\circ }$$ C, but the emission level began to decrease rapidly (within a few minutes) towards a typical uncoated device, confirming the results shown in Figure 2b. After several weeks of operation, we found that the response of the CNT-encapsulated device did not change significantly (Figure 3b, red line). Figure 3c shows the voltage response of a sensor with a encapsulated CNT device (red wire). Compared with an uncoated device (black wire), $$c_{CO_2}$$ ranges from 0 to $$\sim$$ 21,500 ppm . The response of the packaged CNT device at the maximum CO$$_2$$ concentration is $$\Delta V=V_{0 ppm}-V_{lock-in}$$ = 111 mV, while the response of the uncoated device is only 22 mV. The standard deviation of CO$$_2$$ measurement is $$\sim$$ 0.6 mV, which is much smaller than 200-300 mV after the amplitude recovery signal is amplified, mainly because the signal-to-noise ratio (SNR) is limited by thermal noise. Considering the relative sensitivity defined as $$S=\frac{d\Delta V}{dc_{CO_2}}|_{c_{CO_2}=0}$$ and $$\sim$$ 3 dB to measure SNR, we estimate The detection limit of $$\sim$$ 0.12 ppm for the packaged device is compared with the detection limit of $$\sim$$ 1 ppm for the uncoated device, which is consistent with the results in Figure 2b.

In summary, we show a highly efficient CMOS compatible CNT packaged micro hot plate-based MIR emitter, which is manufactured on a single SiO$$_2$$ dielectric film, with a near uniform emissivity and long-term stable operation sex. By adopting a standard CMOS tungsten heater as a microreactor for precise in-situ CNT growth, the processing of the chip is simplified, allowing scalable integration at the wave level. The same heating element can also be used as a contributing factor for the multi-functional self-annealing thermal curve, which can be easily optimized for various processes. We demonstrated the stable operation of alumina encapsulated CNTs at a record temperature of up to 900 $$^{\circ }$$ C. Using the transmitter in the proof-of-concept optical sensing demonstration, we measured that the relative sensitivity has increased by 8 times compared to using the traditional MEMS transmitter, CO$$_2$$. Our transmitter exhibits almost uniform emissivity across the entire MIR band, making it particularly attractive for various low-cost, low-power and large-capacity spectral applications in the MIR spectral region.

The micro hot plate is designed in Cadence$$\copyright$$ and is manufactured on a 6-inch silicon (Si) wafer using a commercial 1$$\upmu$$ m SOI-CMOS process. The film is formed by deep reactive ion etching (DRIE) on a 400 $$\upmu$$ m thick Si substrate, where the buried SiO$$_2$$ layer serves as an etch stop layer. The silicon nitride (Si$$_3$$ N$$_4$$) passivation layer protects the film from environmental factors, such as humidity 31.

Carbon nanotubes are grown on Fe catalyst by in-situ thermal CVD of C$$_2$$ H$$_2$$. Coat (ALD) the micro hot plate with $$\sim$$ 10 nm Al$$_2$$ O$$_3$$, and then sputter with 2-4 nm Fe catalyst. Then these devices [installed on a TO-type package connected to a power supply (Keithley 2400)], and then transferred to a custom CVD chamber to grow CNTs, and then evacuated to a base pressure of $$\sim$$ 0.5 millibar. The CNT growth process is optimized by $$\sim$$ 0.5 $$^{\circ }$$ C resolution based on PID temperature controller, realized in LabVIEW© software, set to 20 $$^{\circ }$$ C/s heating rate. When the micro heater reaches $$\sim$$ 500 $$^{\circ }$$ C, introduce high purity NH$$_3$$ or H$$_2$$ into the chamber, and then at 725 $$^ {\circ }$$ C continues for 60 seconds to form small catalyst Fe islands. Then introduce C$$_2$$ H$$_2$$ into 5% H$$_2$$ through a separate pipeline: C$$_2$$ H$$_2$$ or 25% NH$$_3$$) :C$$_2$$ H$$_2$$ The atmosphere was maintained at $$\sim$$ 4 mbar during the growth of $$\sim$$ for 10 minutes. Then the device was introduced into the ALD reactor (Cambridge NanoTech) to deposit $$\sim$$ 50 nm Al$$_2$$ O$$_3$$ [using trimethyl aluminum (TMA) and water (H$$_2$$ ) O) as a precursor is encapsulated in 200 $$^{\circ }$$ C], and then packaged in $$\sim$$ 400, 500, 600 and 700 $$^{\circ }$$ C, respectively 30 minutes.

In order to obtain the optical absorption (A) spectrum distribution diagram, in the wavelength range of 2-14 $$\upmu$$ m, the transmission (T) and reflection (R) FTIR measurements (normal incidence) are coupled to obtain A = 1- Rebroadcast. The optical aperture of the micro FTIR system (Agilent Cary 620 FTIR microscope) is set to image only the heater area of the micro hot plate. The emission spectrum curve was measured by installing the equipment to a custom MIR spectrometer (Bentham) consisting of a monochromator (TMc300) connected to a cryogenically cooled mercury cadmium telluride detector (DH-MTC). Raman spectra were obtained by Renishaw's inVia Raman microscope under 532 nm excitation.

The NDIR sensor is connected to a National Instruments DAQ card (NI USB-6353) to allow automatic control and data acquisition through LabVIEW© software. The micro heater uses a custom amplifier for voltage modulation with a 2 Hz periodic square wave. A custom preamplifier (60 dB voltage gain) and a software-based lock-in amplifier (1 s integration time; $$\sim$$ 50 dB SNR) are used to recover the signal detected by the thermopile from the background noise. A complete 16-bit A/D conversion is used for measurement. The total flow rate used for CO$$_2$$ sensing is 200 sccm, which is realized by a combination of a computer-controlled mass flow controller (MKS).

Popa, D. and Udrea, F. are committed to integrating mid-infrared gas sensors. Sensor 19, 2076. https://doi.org/10.3390/s19092076 (2019).

Seymour, F. & Harris, NL Reduce tropical deforestation. Science 365, 756–757. https://doi.org/10.1126/science.aax8546 (2019).

Landrigan, PJ et al. The Lancet Pollution and Health Committee. The Lancet 391, 462–512. https://doi.org/10.1016/S0140-6736(17)32345-0 (2018).

Barnes, JH, Chatterton, TJ & Longhurst, JW Emissions and Exposure: Increasing injustices caused by air pollution related to road traffic in the UK. Part D of the transshipment reservoir: Transp. environment. 73, 56-66. https://doi.org/10.1016/j.trd.2019.05.012 (2019).

Morawska, L. et al. Application of low-cost sensing technologies in air quality monitoring and exposure assessment: how far have they gone? environment. internationality. 116, 286–299. https://doi.org/10.1016/j.envint.2018.04.018 (2018).

CAS Article PubMed PubMed Central Google Scholar

Cerchecci, M. etc. Low-power IoT sensor node architecture for waste management in smart city environments. Sensor 18, 1282. https://doi.org/10.3390/s18041282 (2018).

Sun, J. etc. Suspended AlGaN/GaN HEMT NO$$_2$$ gas sensor integrated with micro heater. J. Microelectromechanical. system. 28, 997–1004. https://doi.org/10.1109/JMEMS.2019.2943403 (2019).

Non-dispersive infrared (NDIR) market. technology. Representative, MarketsandMarkets (2020).

Fujita, H. et al. High luminous efficiency AlInSb mid-infrared LED for gas sensors. Physical statistics. Solidi (A) 215, 1700449. https://doi.org/10.1002/pssa.201700449 (2018).

Udrea, F. & Luca, AD CMOS technology platform for ubiquitous micro-sensors. 2017 International Conference on Semiconductors (CAS), 43-52. https://doi.org/10.1109/SMICND.2017.8101149 (2017).

DeLuca, A. et al. An enhanced spectral gas sensor using carbon nanotubes grown in situ. App Physics Wright. 106, 194101. https://doi.org/10.1063/1.4921170 (2015).

Santra, S. etc. Post-CMOS wafer-level growth of carbon nanotubes for low-cost microsensors-proof of concept. Nanotechnology 21, 485301. https://doi.org/10.1088/0957-4484/21/48/485301 (2010).

Pusch, A. etc. A high-efficiency CMOS nano-plasmonic crystal enhanced slow-wave thermal emitter improves infrared gas sensing equipment. science. Rep. 5, 17451. https://doi.org/10.1038/srep17451 (2015).

Lochbaum, A. etc. On-chip narrow-band heat emitter for mid-infrared optical gas sensing. ACS Photon. 4, 1371–1380. https://doi.org/10.1021/acsphotonics.6b01025 (2017).

Kaul, AB, Coles, JB, Eastwood, M., Green, RO & Bandaru, PR uses multi-walled carbon nanotubes to collect ultra-high light absorption efficiency from ultraviolet to infrared. Small 9, 1058-1065. https://doi.org/10.1002/smll.201202232 (2013).

Mizuno, K. et al. A black body absorber made of vertically aligned single-walled carbon nanotubes. The process of the national team Akkad. science. 106, 6044–6047. https://doi.org/10.1073/pnas.0900155106 (2009).

Bom, D. etc. Thermogravimetric analysis of oxidation of multi-walled carbon nanotubes: Evidence for the role of defect sites in carbon nanotube chemistry. Nanolet. 2, 615–619. https://doi.org/10.1021/nl020297u (2002).

Singh, DK, Iyer, PK & Giri, PK Diameter dependence of oxidation stability in multi-walled carbon nanotubes: the effect of defects and the effect of vacuum annealing. J. Application Physics 108, 084313. https://doi.org/10.1063/1.3491022 (2010).

Ali, SZ etc. Low-power, low-cost infrared transmitter using CMOS technology. IEEE Sens. J. 15, 6775–6782. https://doi.org/10.1109/JSEN.2015.2464693 (2015).

Reichl, H. & Grosser, V. Overview and development trends in the field of MEMS packaging. In the technical digest. MEMS 2001. The 14th IEEE International Conference on Micro-Electro-Mechanical Systems (catalog number: 01CH37090), 1-5. https://doi.org/10.1109/MEMSYS.2001.906464 (2001).

Esashi, M. Wafer-level packaging of MEMS. J. Micromachines. Micro engineering. 18, 073001. https://doi.org/10.1088/0960-1317/18/7/073001 (2008).

Santra, S., Guha, PK, Ali, SZ, Haneef, I. & Udrea, F. Silicon-on-insulator diode temperature sensor-detailed analysis of ultra-high temperature operation. IEEE Sens. J. 10, 997–1003. https://doi.org/10.1109/JSEN.2009.2037822 (2010).

Terranova, M., Sessa, V. and Rossi, M. The world of carbon nanotubes: an overview of CVD growth methods. Chemical vapor. Deposit 12, 315–325. https://doi.org/10.1002/cvde.200600030 (2006).

Wirth, CT, Zhang, C., Zhong, G., Hofmann, S. & Robertson, J. The diffusion and reaction of carbon nanotube forests restrict growth. ACS Nano 3, 3560–3566. https://doi.org/10.1021/nn900613e (2009).

Nasiri, A. & Ang, S. The application of alumina-based ceramic slurry in high-temperature electronic packaging. J. Electronics. Package. 143, 20902. https://doi.org/10.1115/1.4049292 (2021).

Golim, OP, etc. Synthesis of alumina ceramic package for thermal barrier coating self-repairing material. J. Phys: Conf. Sir. 985, 012036. https://doi.org/10.1088/1742-6596/985/1/012036 (2018).

Musil, J. et al. Thermal stability of alumina film containing $$\gamma$$-Al$$_2$$O$$_3$$ phase prepared by reactive magnetron sputtering. Application surfing. science. 257, 1058–1062. https://doi.org/10.1016/j.apsusc.2010.07.107 (2010).

Arun Kumar, D., Merline Shyla, J. & Xavier, FP Synthesis and characterization of TiO$$_2$$ /SiO$$_2$$ nanocomposites for solar cell applications. Applications Nanoscience. 2, 429–436. https://doi.org/10.1007/s13204-012-0060-5 (2012).

Popa, D., Ali, SZ, Hopper, R., Dai, Y. & Udrea, F. Smart CMOS mid-infrared sensor array. choose. Wright. 44, 4111. https://doi.org/10.1364/OL.44.004111 (2019).

Dresselhaus, M., Dresselhaus, G., Saito, R. & Jorio, A. Raman spectra of carbon nanotubes. Physics Rep. 409, 47-99. https://doi.org/10.1016/j.physrep.2004.10.006 (2005).

Brand, O. & Fedder, GK (eds) CMOS-MEMS (aaWILEY-VCH, 2005).

We thank EPSRC (EP/S031847/1, EP/S030247/1, EP/P005152/1) for funding. V.-PV-R. Recognizing the EPSRC Doctoral Training Award (EP/M508007/1) and the support of the NPL, JAW recognizes the support of his Dorothy Hodgkin Research Fellowship from the Royal Society.

Department of Engineering, University of Cambridge, Cambridge, CB3 0FA, UK

Daniel Popa, Richard Hopper, Ye Fan, Vlad-Petru Veigang-Radulescu, Jack Alexander-Webber, Stephan Hofmann and Florin Udrea

Flusso Limited, Cambridge, CB4 0DL, UK

Syed Zeeshan Ali & Andrea De Luca

Department of Electronic and Electrical Engineering, University of Bath, Bath, BA2 7AY, UK

Department of Physics, University of Cambridge, Cambridge, CB3 0HE, UK

School of Biomedical Physics, Physics and Astronomy, University of Exeter, Exeter, EX4 4QL, UK

Faculty of Engineering, University of Warwick, Coventry, CV4 7AL, UK

Xing Yuxin & Julian William Gardner

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

DP and FU conceived this idea. DP and RH designed the project. DP, RH, SZA and MTC manufactured these devices. DP, RH, YF, V.-PV-R., RC, and JN characterize these devices. DP and RH tested these devices. DP, RH, YX, JWG and FU analyzed the results. DP supervised the work and wrote the manuscript. All authors reviewed the manuscript.

The author declares no competing interests.

Springer Nature remains neutral on the jurisdiction claims in the published maps and agency affiliates.

Popa, D., Hopper, R., Ali, SZ, etc. A highly stable nanotube-enhanced CMOS-MEMS thermal transmitter for mid-infrared gas sensing. Scientific Report 11, 22915 (2021). https://doi.org/10.1038/s41598-021-02121-5

DOI: https://doi.org/10.1038/s41598-021-02121-5


text:
you are viewing a single comment's thread.

[–]Noncommutative Geometry 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

You're welcome. There are also function spaces with nice topologies that are not normable (so the topology is not induced by a norm). For instance the space of complex-valued continuous functions on a nonempty open set in some euclidean space can be equipped with a topology such that a sequence of functions converges in the topology if and only if it converges uniformly on compact subsets. For this kind of stuff, see Rudin's Functional Analysis (my example is 1.44 on p. 33).

format: plain


text:
You are reading an old version of the documentation (v3.1.0). For the latest version see https://matplotlib.org/stable/

# Working with Matplotlib on OSX¶

On OSX, two different types of Python builds exist: a regular build and a framework build. In order to interact correctly with OSX through the native GUI frameworks, you need a framework build of Python. At the time of writing the macosx and WXAgg backends require a framework build to function correctly. This can result in issues for a Python installation not build as a framework and may also happen in virtual envs and when using (Ana)conda. From Matplotlib 1.5 onwards, both backends check that a framework build is available and fail if a non framework build is found. (Without this check a partially functional figure is created. In particular, it is produced in the background and cannot be put in front of any other window.)

## virtualenv¶

In a virtualenv, a non-framework build is used even when the environment is created from a framework build (virtualenv bug #54, virtualenv bug #609).

The solution is to not use virtualenv, but instead the stdlib's venv, which provides similar functionality but without exhibiting this issue.

If you absolutely need to use virtualenv rather than venv, then from within the environment you can set the PYTHONHOME environment variable to \$VIRTUAL_ENV, then invoke Python using the full path to the framework build (typically /usr/local/bin/python).

## conda¶

The default python provided in (Ana)conda is not a framework build. However, a framework build can easily be installed, both in the main environment and in conda envs: install python.app (conda install python.app) and use pythonw rather than python.


text:
Home » Posts tagged 'Integral' (Page 2)

# Tag Archives: Integral

## Multiple logarithmic integral

Let denote the Riemann zeta function. Evaluate the integral

Solution

Based on symmetries,

Let . It follows that

Using the recursion we get that

Thus,

## Fourier transformation

Let and . Show that

Solution

We note that

Thus,

## Arctan integral

Prove that

where denotes the Euler – Mascheroni constant.

Solution

Beginning by parts we have,

However,

The result now follows taking and .

## Bessel function integral

Let denote the Bessel function of the first kind. Prove that

Solution

We recall that

Hence,

Then,

Using the fact that the looks like an ‘almost periodic’ function with decreasing amplitude. If we denote by the zeros of then as and furthermore

as for each . So the integral converges uniformly in this case justifying the interchange of limit and integral.

The result follows.

## Trigonometric integral

Evaluate the integral

Solution

We have successively:


text:
# Macros in texniccenter

1. Feb 28, 2013

### marcio

Hi all,

Is there a way of getting TeXnicCenter to process these commands so I don't have to type them into the windows command line everytime something new is written?

latex thesis
makeindex thesis.nlo -s nomencl.ist -o thesis.nls
bibtex thesis
latex thesis
latex thesis
pdflatex thesis
start thesis.pdf

Or maybe a script I could load from the command prompt on Windows 8?

Any help will be very much appreciated

2. Feb 28, 2013

### AlephZero

This isn't specific to TeXnicCenter, but see if your TeX distribution has a utility program like "texify" or "latexmk".

They can automatically run makeindex, bibtex, etc if required, and rerun latex to get the cross references correct.

3. Feb 28, 2013

### marcio

I'm using MikTeX.

'texify -p thesis.tex' worked well but not like a charm! It didn't update the nomenclature!

Thanks!

Last edited: Feb 28, 2013


text:
# [D3D11 Effect] How to use SetMatrixArray?How access it on shader?

This topic is 2813 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Im currently use it like that:
XMMATRIX **ppMatrices = new XMMATRIX*[3];fxBoneMatrices->SetMatrixArray( (FLOAT*)ppMatrices[0], 0, 3 );

Im not sure if thats correct, since Im getting weird results, and using pix I dont understand the values Im getting(I want be sure the error is not sintax)..So I looked at DX10 sdk sample and they do it like that:
for( UINT i = 0; i < g_SkinnedMesh.GetNumInfluences( iMesh ); i++ )            {                const D3DXMATRIX* pMat = g_SkinnedMesh.GetMeshInfluenceMatrix( iMesh, i );                g_pmConstBoneWorld->SetMatrixArray( ( float* )pMat, i, 1 );            }

So I guess Im doing it right..
On the shader Im doing that:
matrix skinningTransform = 0;				if( input_p.BoneIDs.x != 5 )skinningTransform += mul( input_p.SkinWeights.x, BoneTransformsInterpolated[ input_p.BoneIDs.x ] );		if( input_p.BoneIDs.y != 5 )skinningTransform += mul( input_p.SkinWeights.y, BoneTransformsInterpolated[ input_p.BoneIDs.y ] );		if( input_p.BoneIDs.z != 5 )skinningTransform += mul( input_p.SkinWeights.z, BoneTransformsInterpolated[ input_p.BoneIDs.z ] );		if( input_p.BoneIDs.w != 5 )skinningTransform += mul( input_p.SkinWeights.w, BoneTransformsInterpolated[ input_p.BoneIDs.w ] );

Do you notice any mistake?

##### Share on other sites
Quote:
 since Im getting weird results

What exactly are the weird results?

Quote:
 XMMATRIX **ppMatrices = new XMMATRIX*[3];fxBoneMatrices->SetMatrixArray( (FLOAT*)ppMatrices[0], 0, 3 );

Did you ever initialize the matrices between those two lines?

How are the matrices in your shader declared? It should be something like :
cbuffer cbPerObject{    row_major float4x4 BoneTransformsInterpolated[ 3 ];};

##### Share on other sites
Original post by Icebone1000
Im currently use it like that:
XMMATRIX **ppMatrices = new XMMATRIX*[3];fxBoneMatrices->SetMatrixArray( (FLOAT*)ppMatrices[0], 0, 3 );

[/quote]
This looks suspicious. How are you filling the matrices before you send them off?
Why do you need a pointer to a pointer to a matrix?

##### Share on other sites
Is declared like that:

cbuffer cbChangers{

matrix BoneTransformsInterpolated[20];

};

I have a loop to initialize the matrices, so that they point to my bone matrices:
VOID SetBonesOnArray(){	//NOTE: remember that tha vertices IDs are according to the order of bones appareance in the pMesh->mBones!	//allocate mem:	ppMBoneArray = new XMMATRIX*[animSkeleton.iNBones];	//traverse mBones  of aiMesh:	Bone_Node *pBone = NULL;	for( UINT i = 0; i < pMesh->mNumBones; i++ ){		//get the bone_node by name:		animSkeleton.GetBoneByName( pMesh->mBones->mName.data, pBone, animSkeleton.pBoneRoot );		//reference its matrix onto array:		ppMBoneArray = &pBone->mFinal;	}}

Any mistake?
I dont know how to explain the weird values..My first array of matrices(for time 0.0) should be 3 identity matrices, and debuging I indeed get those..on pix I get other, but those other arent junk value ones, just not the expected one..and I dont have idea why(yet)..

On pix, the matrices are show like being just an array of rows, it shows my first matrix(for example) like that:(debuging on pix)
BoneTransformsInterpolated[0] float4
BoneTransformsInterpolated[1] float4
BoneTransformsInterpolated[2] float4
BoneTransformsInterpolated[3] float4

Can you see that Im not using it like that, when I use BoneTransformsInterpolated[ v.IDs.x ] Im expecting a full matrix here..At least is how Im imagining..

##### Share on other sites
Quote:
 the matrices are show like being just an array of rows

do the array of rows look like they contain the column values of the matrix? You need to make the following change :

cbuffer cbChangers{row_major matrix BoneTransformsInterpolated[20];};

HLSL receives the matrix data as column major by default (for optimization purposes), so if your matrix is row major and you don't make the suggested change, you'll get unexpected results.

##### Share on other sites
Using row_major or column_major keyword didnt changed anything..

I just seted a matrix like that just to see what I get on pix:
pCurrentBone_p->mFinal = XMMatrixSet( 11, 12, 13, 14,										21, 22, 23, 24,										31, 32, 33, 34,										41, 42, 43, 44 );

Pix display itlike this:
BoneTransformsInterpolated[0] (11.000, 12.000, 13.000, 14.000, )
BoneTransformsInterpolated[1] (21.000, 22.000, 23.000, 24.000, )
BoneTransformsInterpolated[2] (31.000, 32.000, 33.000, 34.000, )
BoneTransformsInterpolated[3] (41.000, 42.000, 43.000, 44.000 )

Its the same for column or row major..
The problem is with the next matrices( BoneTransformsInterpolated[4]..) I always get the same result:
BoneTransformsInterpolated[0] (0.000, 1.000, 0.000, 0.000, )
BoneTransformsInterpolated[1] (-1.000, 0.000, 0.000, 0.000, )
BoneTransformsInterpolated[2] (0.000, 0.000, 1.000, 0.000, )
BoneTransformsInterpolated[3] (2.495, 0.000, -0.009, 1.000 )

That matrix...I NEVER set this matrix to my bones->mFinal matrix..All my bones have the one I showed above( 11, 12..)
Quote:
 But that thing being displaied on pix, is the damn bone offsetmatrix, how is that there?..I never do this calculation ._.Debugging the call to the setmatrixarray, I have a watch on each of the 3 matrices, all of them have the same matrix(11, 12..)..

Damn..I just get it...My matrices arent contiguous on memory, the call to setmatrix array expect everything to lay like an array, since mine is an array of pointers..Im screwing everything(it gets the matrix next to the mFinal).. =D

I hope Im right...Hmm, how I solve that? I bet dont hold the final matrices on the bones, but in the structure that holds the bones, so I avoid a copy of all matrices per frame.. Im trying all that later, I cant right now.
Thanks a lot for the help!

-EDIT-
Indeed it was the problem, I got my skeletal animation/skinning working >w<

[Edited by - Icebone1000 on November 9, 2010 11:47:20 AM]

1. 1
2. 2
3. 3
Rutin
22
4. 4
JoeJ
16
5. 5

• 14
• 29
• 13
• 11
• 11
• ### Forum Statistics

• Total Topics
631774
• Total Posts
3002290
×


text:
# Uniform Distribution

Each element or member of the group ( Continuous uniform distribution, rectangular distribution belonging to a symmetric probability distribution) is equally probable for all intervals which have the same length on the distribution’s support in Statistics.

It is defined by two parameters, x and y, where x = minimum value and y = maximum value.

The uniform distribution is generally denoted by u(x,y).

Uniform distribution can be explained well by knowing the following:

1. Definition
2. Practicing solved examples.
3. It’s important formulas

## Uniform Distribution Definition:

• A continuous probability distribution is a Uniform distribution and is related to the events which are equally likely to occur.

OR

• If the probability density function of a uniform distribution with a continuous random variable X is f(b)=$\frac{1}{y-x}$, then It is denoted by U(x,y), where x and y are constants such that x<a<y.
 It is written as: X $\sim$ U(a,b)

## Uniform Distribution Example:

(Note: Check whether the data is inclusive or exclusive before working out problems with uniform distribution.)

Example: The data in the table below are 55 times a baby yawns, in seconds, of a 9-week-old baby girl.

 10.4 19.6 18.8 13.9 17.8 16.8 21.6 17.9 12.5 11.1 4.9 12.8 14 22.8 20.8 15.9 16.3 13.4 17.1 14.5 19 22.8 1.3 0.7 8.9 11.9 10.9 7.3 5.9 3.7 17.9 19.2 9.8 5.8 6.9 2.6 5.8 21.7 11.8 3.4 2.1 4.5 6.3 10.7 8.9 9.7 9.1 7.7 10.1 3.5 6.9 7.8 11.6 13.8 18.6
• The sample mean = 11.49
• The sample standard deviation = 6.23.

As assumed, the yawn times, in secs, it follows a uniform distribution between 0 to 23 seconds(Inclusive).

So, it is equally likely that any yawning time is from 0 to 23.

• Histograph Type: Empirical Distribution (It matches with theoretical uniform distribution).
• If the length is A, in seconds, of a 9-month-old baby’s yawn.

• The uniform distribution notation for the same is A $\sim$ U(x,y) where x = the lowest value of a and y = the highest value of b.
• f(a) = $\frac{1}{y-x}$, f(a) = the probability density function. For x $\leq$a$\leq$y.

In this example:

• X $\sim$ U(0,23)
• f(a) = $\frac{1}{23-0}$ for For 0 $\leq$X$\leq$23.

### Theoretical Mean Formula

 $\mu$ = $\frac{x+y}{2}$

## Standard Deviation Formula

 $\sigma$ = $\sqrt{\frac{(y-x)^{2}}{12}}$

In this example,

The theoretical mean = $\mu$ = $\frac{x+y}{2}$ $\mu$ = $\frac{0+23}{2}$ = 11.50

standard deviation = $\sqrt{ \frac{(y-x)^{2}}{12}}$

standard deviation = $\sqrt{ \frac{(23-0)^{2}}{12}}$ =6.64 seconds.


text:
# 22) Select the correct statement from the following assuming Camacho Company had a favorable direct.

22) Select the correct statement from the following assuming Camacho Company had a favorable direct materials price variance of $2,500 and an unfavorable direct materials usage variance of$1,000. A. The total direct materials variance is $1,500 favorable. B. The total direct materials variance is$1,500 unfavorable. C. The total direct materials variance is $3,500 favorable. D. The total direct materials variance is$3,500 unfavorable.

Attachments:

Direct Material Variance = Direct Material Usage Variance + Direct Material Price Variance Direct Material Variance = -\$1,000 +...

## Recent Questions in Financial Accounting

Copy and paste your question here...

Attach Files

22) Select the correct statement from the following assuming Camacho Company had a favorable direct.
3 9


text:
Drug Discovery

Creating better drugs to treat diseases is a challenging task. An ideal drug should attack the source of the illness and have no secondary effects. To this end, scientists first identify targets (e.g., a proteins) related to a disease, and the goal is to develop a drug that will interact with these targets (to cure the illness) but not with others (to minimize secondary effects).

This process traditionally involves screening millions of drug compounds (e.g. molecules) in search of a few ones that have the desired interactions with the targets. This produces a drug-target matrix of interactions. The screening process is expensive, so this matrix is highly incomplete.

However, some targets behave similarly, so it is reasonable to assume that the interactions have some structure. For example a union of subspaces or a mixture matrix. Such structures may be exploited to predict the interactions of a new target. This way, given a new target, we may find its interaction with just a few cleverly selected drugs, see which targets have similar interactions, and predict the remaining interactions based on information about these similar targets.


text:
# ApplyAnd operation

Namespace: Microsoft.Quantum.Canon

Package: Microsoft.Quantum.Standard

Inverts a given target qubit if and only if both control qubits are in the 1 state, using measurement to perform the adjoint operation.

operation ApplyAnd (control1 : Qubit, control2 : Qubit, target : Qubit) : Unit is Adj + Ctl

## Description

Inverts target if and only if both controls are 1, but assumes that target is in state 0. The operation has T-count 4, T-depth 2 and requires no helper qubit, and may therefore be preferable to a CCNOT operation, if target is known to be 0. The adjoint of this operation is measurement based and requires no T gates.

The controlled application of this operation requires no helper qubit, 2^c Rz gates and is not optimized for depth, where c is the number of overall control qubits including the two controls from the ApplyAnd operation. The adjoint controlled application requires 2^c - 1 Rz gates (with an angle twice the size of the non-adjoint operation), no helper qubit and is not optimized for depth.

## Input

### control1 : Qubit

First control qubit

### control2 : Qubit

Second control qubit

### target : Qubit

Target auxiliary qubit; must be in state 0

## References

• Cody Jones: "Novel constructions for the fault-tolerant Toffoli gate", Phys. Rev. A 87, 022328, 2013 arXiv:1212.5069 doi:10.1103/PhysRevA.87.022328
• Craig Gidney: "Halving the cost of quantum addition", Quantum 2, page 74, 2018 arXiv:1709.06648 doi:10.1103/PhysRevA.85.044302
• Mathias Soeken: "Quantum Oracle Circuits and the Christmas Tree Pattern", Blog article from December 19, 2019 (note: explains the multiple controlled construction)


text:
Back to Course

0% Complete
0/0 Steps

• ## Do you like this content?

Lesson 8, Topic 2
In Progress

# Poles of a Magnet

Lesson Progress
0% Complete

A magnetic pole is a point at either end of a magnetic field where the magnetic force is concentrated and strongest.

The earliest way to visualize the poles of a magnet is by using a bar magnet, the kind you probably came across in a science class in school.

That type of magnet is called a permanent magnet because its magnetic properties are constant. The two ends of a permanent magnet are its poles called the North pole and South pole respectively.

error:


text:
# All Questions

186 views

### Encrypt array of int for individual retrieval

I have limited exposure to cryptographic terminology, so please bear with me. My end goal is to encrypt integer IDs, before transmitting them to a web client in a list of search results, in a way ...
636 views

### Signature and Timestamp for Long Term Document Archival Question

I have a PDF document intended for long-term (many years, maybe decades) archival which I would like to digitally sign with my personal certificate to ensure its integrity. As far as I understand, I ...
457 views

### What kind of multiparty computation is this?

The classic multiparty computation protocols are defined around " Untrusted parties trying to compute something together". But is there a cryptographic abstraction for, "Trusted parties trying to ...
2k views

### How do digital certificates work, and why is it not possible to reverse engineer one from a signed file?

Digital certificates are used quite commonly these days, for signing files. They are used by various operating systems to ensure reliability and security. For example, Android requires that each of ...
239 views

### Algorithm to securely exchange identities

Say four people each have a public/private key pair that they can use to encrypt or sign messages. They have an anonymous way to post messages such that the others can see them. Malicious entities can ...
155 views

### What “Tag Length” should be used for the EAX MAC?

Since EAX is very flexible with regard to the length of the calculated MAC (what they call "tag" is the MAC value right?), and the EAX paper as well as other documentations carefully avoid suggesting ...
1k views

### Obtaining the key length from the ciphertext of an auto-encipher

I'm revising for a cryptography exam at the moment and I'm having some problems with a question. The question looks for the key length of a cipher given that the word "earthquake" appears in the ...
187 views

### Does hash_df use binary or an ASCII hexadecimal representation for numbers to be passed to the hash function?

I'm implementing the HASH_DRBG algorithm. As per NIST-SP800 90 document for HASH DRBG Generation, section 10.4.1 "Derivation Function Using a Hash Function (Hash_df)", the Hash_df algorithm contains ...
398 views

### ElGamal message signatures retrieving the secret value x

If the GCD(r, p-1) is small and the value k is used to sign a message using ElGamal is also small. Then the secret value of x can be determined. Why is this true? How would one retrieve x?
203 views

### Background for modular arithmetic function

I'm investigating this function: $a := ((b\cdot c) \bmod k) - (b \cdot c)/k$ where $/$ indicates integer division. Two things I've noticed: It's equivalent to multiplying a·b, and then ...
809 views

### Digital Signature Algorithm signature creation

I was studying DSS from "Cryptography and Network Security" by William Stallings. What puzzled me was the DSS approach figure described in the text. It says it uses Public and Private Keys for ...
65 views

### Is it possible to combine true streaming with AEAD?

It seems there is a difference between "streaming" in cryptographic sense (as in CTR) and "streaming" in general programming sense (as in "accept a file larger than RAM from socket and save it on ...
133 views

### Is there a format preserving cryptographically secure hash?

I want a way to 'scramble' strings (like words, names) in a predictable way but I don't ever want to (myself or anyone else) be able to 'unscramble' the strings. I found that perhaps what I am ...
110 views

### Achieving 32-bit verification code with 16-bit CRC? [closed]

I am programming an embedded chip that has a hardware 16-bit CRC module. I have to protect some data bytes $d_0,d_1,...,d_{n-1}$ against corruption caused by sudden loss of power; a 32-bit CRC would ...
79 views

### Security concern about reducing hash value using modulo operation

As stated in the title, what I am looking for is information about a "technique" that I would like to use in some of my algorithms. Sometimes I need to map a hash function's result into a range of ...
80 views

### How many times can a key be used for HMAC-SHA256 before it needs to be rotated?

If I wanted to use hmac for proving that a value hadn't been tampered with, how many times can I use a key before it needs to be rotated?
81 views

### Secure multiparty computation of conjunction

Suppose Alice and Bob each have bits a and b, respectively. How can Alice and Bob compute the function ...
158 views

### Collision in Merkle–Damgård without a collision in compression function

Is it possible to find a collision in Merkle–Damgård just by omitting the extra one bit that is appended to each input without having a collision in compression function?
180 views

### Real life systems that use concepts of crypto computing [closed]

Are there any working cloud/internet solutions/products that operates on encrypted data such as systems using homomorphic encryption, secure multiparty computation, electronic voting, private ...
73 views

### NIST implementation of the Lucas primality test

The NIST standard FIPS 186-4 describes an implementation of the Lucas primality test in section C.3.3. I can follow the algorithm but I am puzzled by step 6.2: ...
113 views

### What is the technical name for a public key container in DER format?

I have a public key in the following (format-neutral; the type is specified by the DER bytes) format: ...
134 views

### Last Round in DES

I am studying DES for my Cryptoexam .As far as I understood , the initial plaintext is permuted and then the left half is called L0 and Right half is called R0. After that for each round the process ...
323 views

### Why does FIPS 186-4 require specific sizes for keys?

In FIPS 186-4, page 32, about FFC crypto it is required that the length of $p$ will be exactly 1024 bit and the length of $q$ will be exactly 160 bit. Why is the requirement not stated in terms of ...
58 views

### Is using SHA256 to extract entropy from a p-rand nonce a good way to create keying material?

Using $SHA256(N)$, where $N$ is 64 bytes of output from the Microsoft Windows CryptGenRandom function. Are there any known vulnerabilities with using this method to ...
116 views

### Which public key encryption scheme is re-randomizable? How can I re-randomize an encryption scheme?

Which public key encryption scheme is re-randomizable? Is there any library for re-randomizable encryption scheme? If not, how can I re-randomize a given public key encryption scheme? I cannot find ...
129 views

### PBKDF2 Salt and Password Ordering

I am currently reading about PBKDF2, and understand that the salt is used only once, while the password is used multiple times in the computation of the final key (see this question). How would the ...
142 views

### Proving Non-Existence of ECC Backdoors

In light of the NIST Dual EC DRBG scandal, I was intrigued by a NIST slide (slide 9) that said the two points P and Q can be chosen so that the chooser can prove they don't have a backdoor. This ...
112 views

### Is this an acceptable All-or-Nothing Transform?

I was thinking about AONTs, and designed the one below, I call it CHANT for Chained-Hash All-or-Nothing Transform; it's my very first shot at something of the sort, and was hoping I could get your ...
335 views

### True Random Number Generator by milliseconds per keystroke (TRNG-Kms)

The simplest way to generate truly random numbers for OTP keys is to measure the time in milliseconds between each keystroke on a keyboard. The randomness depends on the user typing in various speeds. ...
101 views

### Indistinguishable encryptions in the presence of an eavesdropper equivalence

I'm trying to prove that definition 5 and definition 6 in this document are equivalent. This is what I've done at the moment: Asume that the scheme has Indistinguishable encryptions in the presence of ...
121 views

### What is the quantum-resistant signature scheme with the smallest signature + pubkey?

After playing cat and mouse with an number of quantum-resistant signature schemes and coming up with nothing with small enough signatures, I'm turning to Crypto.SE. I need a quantum-resistant ...
209 views

### Using PBKDF2 twice with different argument order

I'm pretty sure this is a really bad approach (in theory), but one of my clients is doing this and I was wondering… How bad it is to perform pbkdf-2 in this way (with 2000 iterations)? ...
145 views

### Twisted curves in protocol

I've come to understand that twisted curves, as for instance defined in the Brainpool specifications, are $F(p)$-isomorphic to their regular $F(p)$ equivalents. So brainpoolP256r1 is isomorphic to ...
136 views

### How to handle the GCD(V,P) != 1 case when doing point addition or point doubling in elliptic curve cryptography

The equation for a finite field Elliptic Curve is of this form: $$y^2 \equiv x^3 + a * x + b \pmod{P}$$ When we do common EC operations like point doubling or point addition we need to calculate the ...
468 views

### Cryptographic hash function for 32-bit length input keys

Since I'm unfamiliar with cryptography area I haven't been able to find cryptographic hash functions for 32 bit integer keys. It seems all such functions (as I saw here) are designed to digest a ...
237 views

### Number of keys when using symmetric and asymmetric encryption?

Quoting part of my homework/assignment: How many keys are required for secure communication among 1000 person if: Symmetric key encryption algorithm is used? Asymmetric key encryption ...
176 views

### Is ISAAC Cipher Cryptographically Secure?

http://en.wikipedia.org/wiki/ISAAC_(cipher) This question was asked before but the answers seem vague, and I want to know about ISAAC specifically, not ISAAC+. It seems some cryptanalysis was ...
200 views

### Can XEX or XTS modes be used with only one tweak?

XEX Mode (with two tweaks) is the following scheme: $X = E_{k}(I) \otimes \alpha^j \\ C = E_{K}(P \oplus X) \oplus X$ where $I$ and $j$ are both tweaks (sector number and block number respectively). ...
248 views

### Nonlinearity of the J-K Flip Flop

In Encryption Schemes for Computer Confidentiality, Pless describes how to use the J-K flip flop as a nonlinear combiner for linear feedback shift registers. This generator was broken because the J-K ...
138 views

### Zero-knowledge proof for committing a choice?

Let's say there are 100 choices (which are publicly known), each represented as a different string, and today you have to choose one of them. You need not reveal what that choice is right now, though. ...
69 views

### Does displaying HMAC hashes of user inputs compromise the HMAC validation?

Here is the scenario: "SECRET" is a secret key that is kept private and only used in this one application. The application allows users to enter in any "VALUE" (within various open-ended limits such ...
235 views

### Convert m-Sequence into a de Bruijn Sequence

In his paper Alternating Step Generator Controlled by de Bruijn Sequence, C.G. Günther states on page three that a de Bruijn sequence (..) can easily be obtained from an m-sequence (maximal length ...
111 views

### Key-dependent encryption in TAHOE-LAFS

TAHOE-LAFS uses a form of "key-dependent encryption", in that a private key SK is encrypted with the truncated hash of the private key: ...
187 views

### secure integer comparison

I have been going through a huge amount of papers to find a simple and a practical method to compare integer numbers without revealing their original values. I know that this falls within the area of ...
282 views

### Entropy test for AES Key Schedule

According to the article "Lest We Remember: Cold Boot Attacks on Encryption Keys" there is a quick and dirty entropy test that can help to find possible AES Key Schedules in memory dumps. Although ...
525 views

### Questions about OAEP for RSA

I have two questions about OAEP for RSA. How are the number of bits to pad with 0 chosen? For example, if I'm sending a 255 byte message with RSA-2048 I have 8 unused bits (1 byte). Should I split ...
120 views

### Sextic twist optimization of BN pairing - cubic root extraction required?

I found the following paper really interesting: http://www.researchgate.net/publication/220378229_A_family_of_implementation-friendly_BN_elliptic_curves/file/79e4150b3a773beecd.pdf It allows ...
2k views

### Diffie-Hellman Key Exchange with Authentication: Man-in-the-Middle query

I have been reading up on MiTM attacks, and the prevention of them using public key certificates. Recently I learnt about Diffie-Hellman Key Exchange with Authentication, and how it uses signed ...


text:
# Budi's factorial sum

What is the remainder when

$\sum_{i=1}^{101} i! i$

is divided by $101$?

This problem is posed by Budi U.

Details and assumptions

You may use the fact that 101 is prime.

×

Problem Loading...

Note Loading...

Set Loading...


text:
Theorem 2.1
MATHEMATICS OF OPERATIONS RESEARCH Vol. 00, No. 0, Xxxxx 0000, pp. 000–000 issn 0364-765Xeissn 1526-54710000000001 INFORMS doi 10.1287/xxxx.0000.0000 © 0000 INFORMS

Empirical Dynamic Programming

EE & CS Departments, University of Southern California

Rahul Jainthanks: Corresponding author. This research was supported via NSF CAREER award CNS-0954116 and ONR Young Investigator Award N00014-12-1-0766.

EE & ISE Departments, University of Southern California

rahul.jain@usc.edu

Dileep Kalathil

EE Department, University of Southern California

manisser@usc.edu

We propose empirical dynamic programming algorithms for Markov decision processes (MDPs). In these algorithms, the exact expectation in the Bellman operator in classical value iteration is replaced by an empirical estimate to get ‘empirical value iteration’ (EVI). Policy evaluation and policy improvement in classical policy iteration are also replaced by simulation to get ‘empirical policy iteration’ (EPI). Thus, these empirical dynamic programming algorithms involve iteration of a random operator, the empirical Bellman operator. We introduce notions of probabilistic fixed points for such random monotone operators. We develop a stochastic dominance framework for convergence analysis of such operators. We then use this to give sample complexity bounds for both EVI and EPI. We then provide various variations and extensions to asynchronous empirical dynamic programming, the minimax empirical dynamic program, and show how this can also be used to solve the dynamic newsvendor problem. Preliminary experimental results suggest a faster rate of convergence than stochastic approximation algorithms.

Key words: dynamic programming; empirical methods; simulation; random operators; probabilistic fixed points.

MSC2000 subject classification: 49L20, 90C39, 37M05, 62C12, 47B80, 37H99.

OR/MS subject classification: TBD.

History: Submitted: July 3, 2019

Markov decision processes (MDPs) are natural models for decision making in a stochastic dynamic setting for a wide variety of applications. The ‘principle of optimality’ introduced by Richard Bellman in the 1950s has proved to be one of the most important ideas in stochastic control and optimization theory. It leads to dynamic programming algorithms for solving sequential stochastic optimization problems. And yet, it is well-known that it suffers from a “curse of dimensionality” [5, 32, 19], and does not scale computationally with state and action space size. In fact, the dynamic programming algorithm is known to be PSPACE-hard [33].

This realization led to the development of a wide variety of ‘approximate dynamic programming’ methods beginning with the early work of Bellman himself [6]. These ideas evolved independently in different fields, including the work of Werbos [44], Kushner and Clark [26] in control theory, Minsky [29], Barto, et al [4] and others in computer science, and Whitt in operations research [45, 46]. The key idea was an approximation of value functions using basis function approximation [6], state aggregation [7], and subsequently function approximation via neural networks [3]. The difficulty was universality of the methods. Different classes of problems require different approximations.

Thus, alternative model-free methods were introduced by Watkins and Dayan [43] where a Q-learning algorithm was proposed as an approximation of the value iteration procedure. It was soon noticed that this is essentially a stochastic approximations scheme introduced in the 1950s by Robbins and Munro [36] and further developed by Kiefer and Wolfowitz [23] and Kushner and Clarke [26]. This led to many subsequent generalizations including the temporal differences methods [9] and actor-critic methods [24, 25]. These are summarized in [9, 40, 34]. One shortcoming in this theory is that most of these algorithms require a recurrence property to hold, and in practice, often work only for finite state and action spaces. Furthermore, while many techniques for establishing convergence have been developed [11], including the o.d.e. method [28, 12], establishing rate of convergence has been quite difficult [22]. Thus, despite considerable progress, these methods are not universal, sample complexity bounds are not known, and so other directions need to be explored.

A natural thing to consider is simulation-based methods. In fact, engineers and computer scientists often do dynamic programming via Monte-Carlo simulations. This technique affords considerable reduction in computation but at the expense of uncertainty about convergence. In this paper, we analyze such ‘empirical dynamic programming’ algorithms. The idea behind the algorithms is quite simple and natural. In the DP algorithms, replace the expectation in the Bellman operator with a sample-average approximation. The idea is widely used in the stochastic programming literature, but mostly for single-stage problems. In our case, replacing the expectation with an empirical expectation operator, makes the classical Bellman operator a random operator. In the DP algorithm, we must find the fixed point of the Bellman operator. In the empirical DP algorithms, we must find a probabilistic fixed point of the random operator.

In this paper, we first introduce two notions of probabilistic fixed points that we call ‘strong’ and ‘weak’. We then show that asymptotically these concepts converge to the deterministic fixed point of the classical Bellman operator. The key technical idea of this paper is a novel stochastic dominance argument that is used to establish probabilistic convergence of a random operator, and in particular, of our empirical algorithms. Stochastic dominance, the notion of an order on the space of random variables, is a well developed tool (see [30, 38] for a comprehensive study).

In this paper, we develop a theory of empirical dynamic programming (EDP) for Markov decision processes (MDPs). Specifically, we make the following contributions in this paper. First, we propose both empirical value iteration and policy iteration algorithms and show that these converge. Each is an empirical variant of the classical algorithms. In empirical value iteration (EVI), the expectation in the Bellman operator is replaced with a sample-average or empirical approximation. In empirical policy iteration (EPI), both policy evaluation and the policy iteration are done via simulation, i.e., replacing the exact expectation with the simulation-derived empirical expectation. We note that the EDP class of algorithms is not a stochastic approximation scheme. Thus, we don’t need a recurrence property as is commonly needed by stochastic approximation-based methods. Thus, the EDP algorithms are relevant for a larger class of problems (in fact, for any problem for which exact dynamic programming can be done.) We provide convergence and sample complexity bounds for both EVI and EPI. But we note that EDP algorithms are essentially “off-line” algorithms just as classical DP is. Moreover, we also inherit some of the problems of classical DP such as scalability issues with large state spaces. These can be overcome in the same way as one does for classical DP, i.e., via state aggregation and function approximation.

Second, since the empirical Bellman operator is a random monotone operator, it doesn’t have a deterministic fixed point. Thus, we introduce new mathematical notions of probabilistic fixed points. These concepts are pertinent when we are approximating a deterministic operator with an improving sequence of random operators. Under fairly mild assumptions, we show that our two probabilistic fixed point concepts converge to the deterministic fixed point of the classical monotone operator.

Third, since scant mathematical methods exist for convergence analysis of random operators, we develop a new technique based on stochastic dominance for convergence analysis of iteration of random operators. This technique allows for finite sample complexity bounds. We use this idea to prove convergence of the empirical Bellman operator by constructing a dominating Markov chain. We note that there is an extant theory of monotone random operators developed in the context of random dynamical systems [15] but the techniques for convergence analysis of random operators is not relevant to our context. Our stochastic dominance argument can be applied for more general random monotone operators than just the empirical Bellman operator.

We also give a number of extensions of the EDP algorithms. We show that EVI can be performed asynchronously, making a parallel implementation possible. Second, we show that a saddle point equilibrium of a zero-sum stochastic game can be computed approximately by using the minimax Bellman operator. Third, we also show how the EDP algorithm and our convergence techniques can be used even with continuous state and action spaces by solving the dynamic newsvendor problem.

A key question is how is the empirical dynamic programming method different from other methods for simulation-based optimization of MDPs, on which there is substantial literature. We note that most of these are stochastic approximation algorithms, also called reinforcement learning in computer science. Within this class. there are Q learning algorithms, actor-critic algorithms, and appproximate policy iteration algorithms. Q-learning was introduced by Watkins and Dayan but its convergence as a stochastic approximation scheme was done by Bertsekas and Tsitsiklis [9]. Q-learning for the average cost case was developed in [1], and in a risk-sensitive context was developed in [10]. The convergence rate of Q-learning was established in [18] and similar sample complexity bounds were given in [22]. Actor-critic algorithms as a two time-scale stochastic approximation was developed in [24]. But the most closely related work is optimistic policy iteration [42] wherein simulated trajectories are used for policy evaluation while policy improvement is done exactly. The algorithm is a stochastic approximation scheme and its almost sure convergence follows. This is true of all stochastic approximation schemes but they do require some kind of recurrence property to hold. In contrast, EDP is not a stochastic approximation scheme, hence it does not need such assumptions. However, we can only guarantee its convergence in probability.

A class of simulation-based optimization algorithms for MDPs that is not based on stochastic approximations is the adaptive sampling methods developed by Fu, Marcus and co-authors [13, 14]. These are based on the pursuit automata learning algorithms [41, 35, 31] and combine multi-armed bandit learning ideas with Monte-Carlo simulation to adaptively sample state-action pairs to approximate the value function of a finite-horizon MDP.

Some other closely related works are [16] which introduces simulation-based policy iteration (for average cost MDPs). It basically shows that almost sure convergence of such an algorithm can fail. Another related work is [17]. wherein a simulation-based value iteration is proposed for a finite horizon problem. Convergence in probability is established if the simulation functions corresponding to the MDP is Lipschitz continuous. Another closely related paper is [2], which considers value iteration with error. We note that our focus is on infinite horizon discounted MDPs. Moreover, we do not require any Lipschitz continuity condition. We show that EDP algorithms will converge (probabilistically) whenever the classical DP algorithms will converge (which is almost always).

A survey on approximate policy iteration is provided in [8]. Approximate dynamic programming (ADP) methods are surveyed in [34]. In fact, many Monte-Carlo-based dynamic programming algorithms are introduced herein (but without convergence proof.) Simulation-based uniform estimation of value functions was studied in [20, 21]. This gave PAC learning type sample complexity bounds for MDPs and this can be combined with policy improvement along the lines of optimistic policy iteration.

This paper is organized as follows. In Section id1, we discuss preliminaries and briefly talk about classical value and policy iteration. Section 2.1 presents empirical value and policy iteration. Section 3.2 introduces the notion of random operators and relevant notions of probabilistic fixed points. In this section, we also develop a stochastic dominance argument for convergence analysis of iteration of random operators when they satisfy certain assumptions. In Section id1, we show that the empirical Bellman operator satisfies the above assumptions, and present sample complexity and convergence rate estimates for the EDP algorithms. Section id1 provides various extensions including asychronous EDP, minmax EDP and EDP for the dynamic newsvendor problem. Basic numerical experiments are reported in Section id1.

We first introduce a typical representation for a discrete time MDP as the 5-tuple

 (S,A,{A(s) : s∈S},Q,c).

Both the state space and the action space are finite. Let denote the space of probability measures over and we define similarly. For each state , the set is the set of feasible actions. The entire set of feasible state-action pairs is

 K≜{(s,a)∈S×A% : a∈A(s)}.

The transition law governs the system evolution, for all , i.e., for is the probability of visiting the state next given the current state-action pair . Finally, is a cost function that depends on state-action pairs.

Let denote the class of stationary deterministic Markov policies, i.e., mappings which only depend on history through the current state. We only consider such policies since it is well known that there is an optimal policy in this class. For a given state , is the action chosen in state under the policy . We assume that only contains feasible policies that respect the constraints . The state and action at time are denoted and , respectively. Any policy and initial state determine a probability measure and a stochastic process defined on the canonical measurable space of trajectories of state-action pairs. The expectation operator with respect to is denoted .

We will focus on infinite horizon discounted cost MDPs with discount factor . For a given initial state , the expected discounted cost for policy is denoted by

 vπ(s)=Eπs[∞∑t=0αtc(st,at)].

The optimal cost starting from state is denoted by

 v∗(s)≜infπ∈ΠEπs[∑t≥0αtc(st,at)],

and denotes the corresponding optimal value function in its entirety.

The Bellman operator is defined as

 [Tv](s)≜mina∈A(s){c(s,a)+αE[v(~s)|s,a]},∀s∈S,

for any , where is the random next state visited, and

is the explicit computation of the expected cost-to-go conditioned on state-action pair . Value iteration amounts to iteration of the Bellman operator. We have a sequence where for all and an initial seed . This is the well-known value iteration algorithm for dynamic programming.

We next state the Banach fixed point theorem which is used to prove that value iteration converges. Let be a Banach space with norm . We call an operator a contraction mapping when there exists a constant such that

 ∥Gv1−Gv2∥U≤κ∥v1−v2∥U, ∀v1,v2∈U.
###### Theorem 2.1

(Banach fixed point theorem) Let be a Banach space with norm , and let be a contraction mapping with constant . Then,

(i) there exists a unique such that ;

(ii) for arbitrary , the sequence converges in norm to as ;

(iii) for all .

For the rest of the paper, let denote the space of contraction mappings from . It is well known that the Bellman operator with constant is a contraction operator, and hence has a unique fixed point . It is known that value iteration converges to as . In fact, is the optimal value function.

Policy iteration is another well known dynamic programming algorithm for solving MDPs. For a fixed policy , define as

 [Tπv](s)=c(s,π(s))+αE[v(~s)|s,π(s)].

The first step is a policy evalution step. Compute by solving for . Let be the vector of one period costs corresponding to a policy , and , the transition kernel corresponding to the policy . Then, writing we have the linear system

 cπ+Qπvπ=vπ.  (Policy Evaluation)

The second step is a policy improvement step. Given a value function , find an ‘improved’ policy with respect to such that

 Tπv=Tv.  (Policy Update)

Thus, policy iteration produces a sequence of policies and as follows. At iteration , we solve the linear system for , and then we choose a new policy satisfying

 Tπkvπk=Tvπk,

which is greedy with respect to . We have a linear convergence rate for policy iteration as well. Let be any value function, solve for , and then compute . Then, we know [9, Lemma 6.2] that

 ∥vπ−v∗∥≤α∥v−v∗∥,

from which convergence of policy iteration follows. Unless otherwise specified, the norm we will use in this paper is the sup norm.

We use the following helpful fact in the paper. Proof is given in Appendix id1.

###### Remark 2.1

Let be a given set, and and be two real-valued functions on . Then,

(i) , and

(ii) .

We now present empirical variants of dynamic programming algorithms. Our focus will be on value and policy iteration. As the reader will see, the idea is simple and natural. In subsequent sections we will introduce the new notions and techniques to prove their convergence.

We introduce empirical value iteration (EVI) first.

The Bellman operator requires exact evaluation of the expectation

We will simulate and replace this exact expectation with an empirical estimate in each iteration. Thus, we need a simulation model for the MDP. Let

 ψ : S×A×[0,1]→S

be a simulation model for the state evolution for the MDP, i.e. yields the next state given the current state, the action taken and an i.i.d. random variable. Without loss of generality, we can assume that is a uniform random variable on and . With this convention, the Bellman operator can be written as

Now, we replace the expectation with its sample average approximation by simulating . Given i.i.d. samples of a uniform random variable, denoted , the empirical estimate of is . We note that the samples are regenerated at each iteration. Thus, the EVI algorithm can be summarized as follows.

In each iteration, we regenerate samples and use this empirical estimate to approximate . Now we give the sample complexity of the EVI algorithm. Proof is given in Section id1.

###### Theorem 3.1

Given and , fix and select such that where . Select an such that

 n≥n(ϵ,δ)=2(κ∗)2ϵ2glog2|K|δ1

where and select a such that

 k≥k(ϵ,δ)=log(1δ2μn,min),

where and is given by Lemma 4.3. Then

 P{∥^vkn−v∗∥≥ϵ}≤δ.
###### Remark 3.1

This result says that, if we take samples in each iteration of the EVI algorithm and perform iterations then the EVI iterate is close to the optimal value function with probability greater that . We note that the sample complexity is .

The basic idea in the analysis is to frame EVI as iteration of a random operator which we call the empirical Bellman operator. We define as

 [ˆTn(ω)v](s)≜mina∈A(s){c(s,a)+αnn∑i=1v(ψ(s,a,ξi))},∀s∈S. (3.1)

This is a random operator because it depends on the random noise samples . The definition and the analysis of this operator is done rigorously in Section id1.

We now define EPI along the same lines by replacing exact policy improvement and evaluation with empirical estimates. For a fixed policy , we can estimate via simulation. Given a sequence of noise , we have for all . For , choose a finite horizon such that

 max(s,a)∈K|c(s,a)|∞∑t=T+1αt<γ.

We use the time horizon to truncate simulation, since we must stop simulation after finite time. Let

 [^vπ(s)](ω)=T∑t=0αtc(st(ω),π(st(ω)))

be the realization of on the sample path .

The next algorithm requires two input parameters, and , which determine sample sizes. Parameter is the sample size for policy improvement and parameter is the sample size for policy evaluation. We discuss the choices of these parameters in detail later. In the following algorithm, the notation is understood as the state at time in the simulated trajectory .

Step 2 replaces computation of (policy improvement). Step 3 replaces solution of the system (policy evaluation).

We now give the sample complexity result for EPI. Proof is given in Section id1.

###### Theorem 3.2

Given , select such that . Also select such that . Then, select such that where . Then, select a and such that

 q≥q(ϵ,δ)=2(κ∗(T+1))2(ϵ1−γ)2log2|S|δ11.
 n≥n(ϵ,δ)=2(κ∗)2(ϵ2/α)2log2|K|δ12.

where , and select a such that

 k≥k(ϵ,δ)=log(1δ2μn,q,min),

where and is given by equation (5.6). Then,

 P{∥vπk−v∗∥≥ϵ}≤δ.
###### Remark 3.2

This result says that, if we do simulation runs for empirical policy evaluation, samples for empirical policy update and perform iterations then the true value of the policy will be close to the optimal value function with probability greater that . We note that is and is .

The empirical Bellman operator we defined in equation (3.1) is a random operator. When it operates on a vector, it yields a random vector. When is iterated, it produces a stochastic process and we are interested in the possible convergence of this stochastic process. The underlying assumption is that the random operator is an ‘approximation’ of a deterministic operator such that converges to (in a sense we will shortly make precise) as increases. For example the empirical Bellman operator approximates the classical Bellman operator. We make this intuition mathematically rigorous in this section. The discussion in this section is not specific to the Bellman operator, but applies whenever a deterministic operator is being approximated by an improving sequence of random operators .

In this subsection we formalize the definition of a random operator, denoted by .

Since is a random operator, we need an appropriate probability space upon which to define . So, we define the sample space , the algebra where is the inherited Borel algebra on , and the probability distribution on formed by an infinite sequence of uniform random variables. The primitive uncertainties on are infinite sequences of uniform noise where each is an independent uniform random variable on . We view as the appropriate probability space on which to define iteration of the random operators .

Next we define a composition of random operators, , on the probability space , for all and all where,

 ˆTkn(ω)v=ˆTn(ωk−1)ˆTn(ωk−2)⋯ˆTn(ω0)v.

Note that is an infinite sequence where each . Then we can define the iteration of with an initial seed (we use the hat notation to emphasize that the iterates are random variables generated by the empirical operator) as

 ˆvk+1n=ˆTnˆvkn=ˆTknˆv0n (4.1)

Notice that we only iterate for fixed . The sample size is constant in every stochastic process , where , for all . For a fixed , we can view all as measurable mappings from to via the mapping .

The relationship between the fixed points of the deterministic operator and the probabilistic fixed points of the random operator depends on how approximates . Motivated by the relationship between the classical and the empirical Bellman operator, we will make the following assumption.

###### Assumption 4.1

and . Also has a (possibly non-unique) fixed point such that .

Assumption 4.1 is equivalent to for almost all . Here, we benefit from defining all of the random operators together on the sample space , so that the above convergence statement makes sense.

We now introduce a natural probabilistic fixed point notion for , in analogy to the definition of a fixed point, for a deterministic operator.

###### Definition 4.1

A vector is a strong probabilistic fixed point for the sequence if

 limn→∞P(∥ˆTn^v−^v∥>ϵ)=0, ∀ϵ>0.

We note that the above notion is defined for a sequence of random operators, rather than for a single random operator.

###### Remark 4.1

We can give a slightly more general notion of a probabilistic fixed point which we call -strong probablistic fixed point. For a fixed , we say that a vector is an -strong probabilistic fixed point if there exists an such that for all we get . Note that, all strong probabilistic fixed points satisfy this condition for arbitrary and hence are -strong probabilistic fixed points. However the converse need not be true. In many cases we may be looking for an -optimal ‘solution’ with a ‘probabilistic guarantee’ where is fixed a priori. In fact, this would provide an approximation to the strong probabilistic fixed point of the sequence of operators.

It is well known that iteration of a deterministic contraction operator converges to its fixed point. It is unclear whether a similar property would hold for random operators, and whether they would converge to the strong probabilistic fixed point of the sequence in any way. Thus, we define an apparently weaker notion of a probabilistic fixed point that explicitly considers iteration.

###### Definition 4.2

A vector is a weak probabilistic fixed point for if

 limn→∞limsupk→∞P(∥ˆTknv−^v∥>ϵ)=0, ∀ϵ>0, ∀v∈R|S|

We use instead of because the latter limit may not exist for any fixed .

###### Remark 4.2

Similar to the definition that we gave in Remark 4.1, we can define an -weak probablistic fixed point. For a fixed , we say that a vector is an -weak probabilistic fixed point if there exists an such that for all we get . As before, all weak probabilistic fixed points are indeed weak probabilistic fixed points, but converse need not be true.

At this point the connection between strong/weak probabilistic fixed points of the random operator and the classical fixed point of the deterministic operator is not clear. Also it is not clear whether the random sequence converges to either of these two fixed point. In the following subsections we address these issues.

In this subsection, we construct a new stochastic process on that will be useful in our analysis. We first start with a simple lemma.

###### Lemma 4.1

The stochastic process is a Markov chain on .

\@trivlist

This follows from the fact that each iteration of is independent, and identically distributed. Thus, the next iterate only depends on history through the current iterate .  \@endparenv

Even though is a Markov chain, its analysis is complicated by two factors. First, is a Markov chain on the continuous state space , which introduces technical difficulties in general when compared to a discrete state space. Second, the transition probabilities of are too complicated to compute explicitly.

Since we are approximating by and want to compute , we should track the progress of to the fixed point of . Equivalently, we are interested in the real-valued stochastic process . If approaches zero then approaches , and vice versa.

The state space of the stochastic process is , which is simpler than the state space of , but which is still continuous. Moreover, is a non-Markovian process in general. In fact it would be easier to study a related stochastic process on a discrete, and ideally a finite state space. In this subsection we show how this can be done.

We make a boundedness assumption next.

###### Assumption 4.2

There exists a such that almost surely for all , . Also, .

Under this assumption we can restrict the stochastic process to the compact state space

 ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯B2κ∗(0)={v∈R|S| : ∥v∥≤2κ∗}.

We will adopt the convention that any element outside of will be mapped to its projection onto by any realization of .

Choose a granularity to be fixed for the remainder of this discussion. We will break up into intervals of length starting at zero, and we will note which interval is occupied by at each . We will define a new stochastic process on with state space . The idea is that will report which interval of is occupied by . Define via the rule:

 Xkn(ω)={0,if ∥^vk(ω)−v∗∥=0,η≥1,if (η−1)ϵg<∥^vk(ω)−v∗∥≤ηϵg, (4.2)

for all . More compactly,

 Xkn(ω)=⌈∥^vkn(ω)−v∗∥/ϵg⌉,

where denotes the smallest integer greater than or equal to . Thus the stochastic process is a report on how close the stochastic process is to zero, and in turn how close the Markov chain is to the true fixed point of .

Define the constant

 N∗≜⌈2κ∗ϵg⌉.

Notice is the smallest number of intervals of length needed to cover the interval . By construction, the stochastic process is restricted to the finite state space

The process need not be a Markov chain. However, it is easier to work with than either or because it has a discrete state space. It is also easy to relate back to .

Recall that denotes almost sure inequality between two random variables and defined on the same probability space. The stochastic processes and are defined on the same probability space, so the next lemma follows by construction of .

###### Lemma 4.2

For all , .

To proceed, we will make the following assumptions about the deterministic operator and the random operator .

for all .

###### Assumption 4.4

There is a sequence such that

 P(∥Tv−ˆTnv∥<ϵ)>pn(ϵ)

and as for all , .

We now discuss the convergence rate of . Let . On the event , we have

 ∥^vk+1n−v∗∥≤∥ˆTn^vkn−T^vk∥+∥T^vkn−v∗∥≤(αη+1)ϵg

where we used Assumption 4.3 and the definition of . Now using Assumption 4.4 we can summarize:

 If Xkn=η, then Xk+1n≤⌈αη+1⌉ with a probability at least pn(ϵg). (4.3)

We conclude this subsection with a comment about the state space of the stochastic process of . If we start with and if then we must have improvement in the proximity of to . We define a new constant

If is too small, then may be equal to and no improvement in the proximity of to can be detected by . For any , and strict improvement must hold. So, for the stochastic process , we can restrict our attention to the state space .

If we could understand the behavior of the stochastic processes , then we could make statements about the convergence of and . Although simpler than and , the stochastic process is still too complicated to work with analytically. We overcome this difficulty with a family of dominating Markov chains. We now present our dominance argument. Several technical details are expanded upon in the appendix.

We will denote our family of “dominating” Markov chains (MC) by . We will construct these Markov chains to be tractable and to help us analyze . Notice that the family has explicit dependence on . We do not necessarily construct on the probability space . Rather, we view as being defined on , the canonical measurable space of trajectories on , so . We will use to denote the probability measure of on . Since will be a Markov chain by construction, the probability measure will be completely determined by an initial distribution on and a transition kernel. We denote the transition kernel of as .

Our specific choice for is motivated by analytical expediency, though the reader will see that many other choices are possible. We now construct the process explicitly, and then compute its steady state probabilities and its mixing time. We will define the stochastic process on the finite state space , based on our observations about the boundedness of and . Now, for a fixed and (we drop the argument in the following for notational convenience) as assumed in Assumption 4.4 we construct the dominating Markov chain as:

 Yk+1n={max{Ykn−1,η∗},w.p.% pn,N∗,w.p. 1−pn. (4.4)

The first value corresponds to the case where the approximation error satisfies , and the second value corresponds to all other cases (giving us an extremely conservative bound in the sequel). This construction also ensures that for all , almost surely. Informally, will either move one unit closer to zero until it reaches , or it will move (as far away from zero as possible) to .

We now summarize some key properties of .

###### Proposition 4.1

For as defined above,

(i) it is a Markov chain;

(ii) the steady state distribution of , and the limit , exists;

(iii) as for all ;

\@trivlist

Parts (i) - (iii) follow by construction of and the fact that this family consists of irreducible Markov chains on a finite state space.  \@endparenv

We now describe a stochastic dominance relationship between the two stochastic processes and . The notion of stochastic dominance (in the usual sense) will be central to our development.

###### Definition 4.3

Let and be two real-valued random variables, then stochastically dominates , written , when for all increasing functions .

The condition is known to be equivalent to

 E[1{X≥θ}]≤E[1{Y≥θ}]  or  Pr{X≥θ}≤Pr{Y≥θ},

for all in the support of . Notice that the relation makes no mention of the respective probability spaces on which and are defined - these spaces may be the same or different (in our case they are different).

Let be the filtration on


text:
PUMPA - THE SMART LEARNING APP

AI system creates personalised training plan based on your mistakes

government is a system by which a country is governed. It is accountable for developing and implementing the rules of society,  for example, defense, the economy, public services, etc.

While the responsibilities of all governments are similar, the way how they execute their duties and responsibilities are different in every country. It mainly depends on the form of government in which it works.

Government

Different countries adopted different forms of government, including direct democracy, representative democracy, monarchy, oligarchy, autocracy, socialism, etc. In that Democracy and monarchy are the oldest forms of government.

Monarchy:

A monarchy is a form of government which has a single person as its head. Usually they are known by their titles such as King, Queen, Emperor, Empress.
The earlier monarchy was common across all the countries. But as soon as the demands of the people (like rights, and freedom) increased, the system also evolved.

At a certain period, the true form of monarchy disappeared. Now monarchy is considered a rare case (except few countries like England)

Monarchy

Emergence of monarchies
• In the early period of society, men were hunters  and gathered food. But after  settling near rivers they practised agriculture.
• When the man started to live in groups, tribes were formed. Every tribe had its chief.
• These groups fought among themselves for land, water and other resources.
• Those who emerged victorious formed kingdoms by uniting the other tribal groups.
• These kingdoms later integrated to form empires.
Hunter and gatherer

The Defeat of monarchy:

Monarchies started to face their downfall firstly in Europe during the $$18$$th century. The fall-out movement of Monarchy was known as the Enlightenment.