text:
270
views
0
recommends
+1 Recommend
1 collections
0
shares
• Record: found
• Abstract: found
• Conference Proceedings: found
Is Open Access

# Living in Parallel: Adventures in double consciousness and pluralism

Proceedings of EVA London 2020 (EVA 2020)

AI and the Arts: Artificial Imagination

6th July – 9th July 2020

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

This paper attempts to redefine Double Consciousness (DC) as a framework through a number of emerging application areas, including: i) Living in Virtual Reality, ii) Dream Hacking and iii) DMTx Technology. The following questions will be used to frame the investigation: What are the opportunities that these application areas offer in terms of living in parallel? What are the corresponding challenges? Can adopting these forms of DC help us to see ourselves from other perspectives? How will DC technology change the experience of reality for individuals, for groups and for society? What are the ethics of these DC technologies? What are the limits of DC and how can Pluralism contribute?

### Most cited references26

• Record: found
• Abstract: found
• Article: found
Is Open Access

### Portable Devices to Induce Lucid Dreams—Are They Reliable?

(2019)
Introduction One of the main current challenges in lucid dreaming (LD) research is to develop a simple and reliable way to induce it (Stumbrys et al., 2012). This is because, for most people, LD is very pleasurable but also very rare (LaBerge and Rheingold, 1990; Mota-Rolim et al., 2013). Along with its recreational nature, LD also has potential clinical applications, such as the treatment of recurrent nightmares in post-traumatic stress disorder (Aurora et al., 2010; Mota-Rolim and Araujo, 2013; Morgenthaler et al., 2018). This has attracted the attention of high-tech companies, which have been launching portable LD induction devices commercially available to the general public. This equipment captures electroencephalographic (EEG) activity for the online detection of rapid eye movement (REM) sleep, the sleep stage associated with typical dreaming (Aserinsky and Kleitman, 1953; Dement and Kleitman, 1957; for review, see Hobson et al., 2000). To induce lucidity, most devices provide visual, auditory, and/or tactile stimuli as sensory cues, which can become incubated into the dream content to alert dreamers that they are dreaming but without waking them up (LaBerge et al., 1981a; LaBerge and Levitan, 1995). Other devices provide transcranial alternating current stimulation (tACS) of the frontal cortex (Voss et al., 2014). Here we review 10 such devices: DreamLight, NovaDreamer, Aurora, Remee, REM-Dreamer, ZMax, Neuroon, iBand, LucidCatcher, and Aladdin (Figure 1). Figure 1 Up: Internal views of (A) REM-Dreamer sleeping mask and (B) LucidCatcher headband (images reproduced with permission from ELI Company and Luciding Inc). Down: Table comparing the devices. Stim, Stimulus; REM detect, online REM sleep detection; tech info, technological information; sci test, scientifically tested; L, light; S, sound; V, vibration; EM, eye movement; A, accelerometer; T, temperature; P, pulse oximeter; tACS, transcranial alternating current stimulation. Neuroon, iBand, Aurora, and Aladdin electrodes are placed on Fp1/Fp2 referenced to FpZ; ZMax electrodes are placed on AF7/AF8 referenced to FpZ; and LucidCatcher electrodes are placed on Fp1/Fp2 referenced to TP9/TP10. The pioneers: DreamLight and NovaDreamer In the early 1980s, neuroscientists tried to induce LD by verbal suggestion (LaBerge et al., 1981a), musical tones (Kueny, 1985), tactile stimuli (Rich, 1985), and olfactory stimuli (LaBerge et al. unpublished data). In 1987, Stephen LaBerge conducted the first study on inducing LD by light stimulation during REM sleep: of 28 volunteers, 17 (61%) reported having experienced at least one LD episode (LaBerge, 1987). With the success of light stimulation, LaBerge and Levitan (LaBerge and Levitan, 1995) tested for the first time a portable computerized biofeedback device, named DreamLight. Lights were used during REM sleep in 14 subjects for 4–24 nights. As a way to control for the placebo effect, lights were delivered on alternate nights, without the volunteers' knowledge. Eleven subjects (78%) reported 32 LD episodes: 22 happened on nights with the light cues and 10 on nights without them. Besides, the volunteers reported seeing the cues in their dreams significantly more often on light-cue nights compared to non-light-cue nights (73 vs. 9, respectively). Following these experiments, LaBerge and co-workers from the Lucidity Institute released the first commercialized product to induce LD: the sleeping mask NovaDreamer. This device detects REM sleep automatically and delivers flashing lights to incubate these stimuli into the dream, as a cue to induce lucidity. The mask was available in the market until 2004, when its production was discontinued. In 2009, the Lucidity Institute reported working on a new NovaDreamer, which would be released in 2016, but since then, no update has been announced. The modern devices Products That Are Available in the Market Aurora was the first headband launched on a crowdfunding platform. Its campaign started in December 2013, asking for US$90,000, and in 40 days, they raised almost US$ 240,000. Aurora has electrodes for EEG oscillation detection and accelerometers that track body movements. According to their site: “Our experiments with real-time sleep stage detection have proven very accurate with 90% of our experimental subjects”; however, the developers do not provide enough scientific information on how their algorithm calculates accuracy, nor make the data supporting this claim accessible. They also admit some limitations of the method and posted as a disclaimer that the “REM-detection algorithm is not yet perfect.” To date, the system is not available for immediate purchase but can be ordered. The Aurora platform is open-source and thus allows users to contribute in developing the system. Remee is the cheapest sleeping mask and the only one that does not use online sleep stage detection. According to their site: “Using a series of smart timers, light patterns are displayed throughout the night…” This means that lights can appear during REM sleep or during the other sleep stages: sleep onset (N1), superficial sleep (N2), and deep sleep (N3). It is known that LD happens predominantly during REM sleep (LaBerge et al., 1981b, 1986) and less often during N1 and N2 sleep stages (LaBerge, 1980a,b, 1990; LaBerge et al., 1981a; Dane and Van de Caslte, 1984; Stumbrys and Erlacher, 2012; Mota-Rolim et al., 2015). However, if lights appear during N3, they will most probably fail to induce LD, since there are no reports of LD during this sleep stage. Besides, this mask may potentially impair sleep quality by disturbing the slow waves that occur during N3, which are related to the homeostatic restoration function of sleep (Benington and Heller, 1995). The REM-Dreamer device (Figure 1A) has two features among all masks. First, it can induce lucidity by recording and playing voice messages, such as the user saying “I am dreaming,” for instance, which can incubate into dreams (LaBerge et al., 1981a). Second, it allows communication between the dreamer and the machine. This feature is based on the ideas that (1) subjective eye movements during dreaming correlate with objective eye movements (that is, real eyeball rotations), as postulated by the “scanning hypothesis” (Roffwarg et al., 1962; for review, see Arnulf, 2011; LaBerge et al., 2018a,b); and (2) it is possible to voluntarily move the eyes to indicate dream lucidity (Hearne, 1978; LaBerge, 1980a,b). Thus, when the dreamer perceives the cues, the dreamer can move the eyes in such a predetermined manner that the device would sense this movement and stop generating the stimuli. The sleeping mask utilizes infrared sensors to detect when the user is in REM sleep; however, not enough technical information is available on how the algorithm implements this. Hypnodyne's ZMax became available for sale in 2018 and is the most expensive device nowadays. ZMax is a sleep-monitoring headband that delivers light, vibrotactile, and auditory stimuli, and also allows audio-recording of dream experiences. ZMax is currently being tested in various universities and scientific institutions around the world. The device monitors sleep through two frontal sensors, which capture brain activity and ocular movements. In contrast to other devices that use dry EEG sensors, ZMax uses proprietary disposable solid hydrogel electrodes. In addition, it includes sensors for heart rate (acquired through a photoplethysmogram; PPG), temperature, ambient light, sound, and body movements. ZMax features offline autoscoring and online REM sleep detection algorithms, whose technical information is available and comprehensive. The accuracy of ZMax relies in part on individual EEG phenotype detection. To do this, REM sleep classification is initially delayed for 2 h, a period that will usually include at least the first sleep cycle. When this time has elapsed, the system analyzes the sleep data collected thus far and extracts a brief phenotype description of the individual. The result is saved in a subject-specific file, which can be loaded for subsequent trials, before data collection. Importantly, ZMax's online algorithms, whether for REM sleep detection or for stimulus protocols, require a computer to be connected through a wireless connection dongle because the algorithmic computations occur on the computer and are transmitted back to ZMax. Despite ZMax not being open-source, it allows for the scripting of several functions in JavaScript for custom stimuli. ZMax can also be interfaced with various other programming languages (MATLAB, Python, PHP, C++, Java, etc.) through an exposed TCP/IP 1 data socket. Products That Are Under Development Neuroon includes a mobile app dream diary, which is a good method to increase dreams and LD recall (LaBerge and Rheingold, 1990). It is open-source and also was launched in a crowdfunding platform: they asked for US$100,000 in pledges in June 2017, and 1 month later, they achieved almost$360,000. Besides measuring EEG activity, Neuroon has a pulse oximeter (PPG) and sensors for temperature and ocular movements, which would allow for online detection of REM sleep. The technical documentation of Neuroon is accessible; however, despite claiming the use of established techniques to induce LD (i.e., visual and tactile stimulation; Paul et al., 2014), the product is yet to be scientifically tested. More recently, the company behind Neuroon has filed for bankruptcy, and its future is thus uncertain. iBand is the device that got the most crowdfunding support. They started their campaign in September 2016, asking for €50,000, and in 44 days received around €64,500. This headband has sensors that measure brain rhythms, body movement, temperature, and heart rate, and claims to analyze them through an “auto-learning software algorithm.” However, its platform is not open-source, and the technical details of this algorithm are not available. LucidCatcher (Figure 1B) and Aladdin are the only headbands that promise to induce LD using tACS of the frontal region. Since frontal gamma power (~40 Hz) increases during LD (Mota-Rolim et al., 2008, 2010; Voss et al., 2009), Voss et al. (2014) used a low current to induce gamma activity on the frontal region during REM sleep and successfully increased self-awareness subjective scores during dreaming. Despite the claim that the Voss et al. (2014) study “was replicated by Aladdin in an IRB-approved clinical study,” we could not find these data nor any related scientific publication. Importantly, there has not been a published reproduction of Voss et al. (2014) to date. It should also be noted that intracranial recordings have recently questioned whether transcranial electric stimulation can directly affect neuronal circuits, since traditional transcranial electric stimulation techniques require 4–6 mA to directly affect neuronal circuits (Vöröslakos et al., 2018), at least 16 times more than in the Voss et al. (2014) protocol. Therefore, it can be argued that the Voss et al. (2014) results were likely due to indirect mechanisms, i.e., the sensation of the electrotactile stimulus may have brought participants closer to waking up. This would increase cortical activation, particularly in key brain areas involved in LD (Mota-Rolim et al., 2008, 2010; Voss et al., 2009; Dresler et al., 2012; for review, see Baird et al., 2019), and therefore may have led to heightened dream consciousness. Conclusions and Perspectives Most devices that were launched on crowdfunding platforms, mainly Aurora, iBand, and Neuroon, were able to raise much more resources than they asked for, which indicates that the public is interested in LD induction technologies. To date and to the authors' knowledge, the only research-ready equipment available in the market is ZMax; other devices, such as Neuroon, Aladdin, and LucidCatcher have had their release dates continually delayed. Only Neuroon and ZMax provide minimal technical information on how their algorithm detects REM sleep online, but none makes the data fully available. Most importantly, only DreamLight has been empirically tested with published results (Figure 1, table); thus, we conclude that better-controlled validation studies are necessary to prove the effectiveness of LD induction devices. More scientific studies on other techniques to induce LD are also clearly warranted, and in particular, more reproducible studies in which LD can be induced. In a systematic review, Stumbrys et al. (2012) investigated 35 studies, which employed (a) cognitive techniques—such as autosuggestion, reality testing, and alpha feedback, for example (n = 26); (b) external stimulation—such as light, acoustic, and vibrotactile (n = 11); and (c) application of donepezil, which is an acetylcholinesterase inhibitor (n = 1). The authors observed that the methodological quality of the works analyzed was relatively low, and none of the induction techniques reported in these studies induced LD reliably and consistently. More research is needed to increase our understanding of external sensory stimulus processing during sleep and the conditions and the stimulus properties required for reliable dream content incubation, while preventing awakenings (Appel et al., 2018). Promising results were obtained by two recent studies that applied galantamine (another acetylcholinesterase inhibitor), in combination with cognitive techniques, such as sleep interruption plus mnemonic induction of lucid dreams (MILDs; LaBerge et al., 2018a,b) or sleep interruption plus meditation and dream reliving (MDR; Sparrow et al., 2018). The association of the portable devices with cognitive and pharmacological techniques has great potential to improve the reliability of LD induction techniques. Author Contributions All authors listed have made a substantial, direct and intellectual contribution to the work, and approved it for publication. Conflict of Interest Statement AP worked for Inteliclinic, the company that developed Neuroon, for 3 months in 2017 as a consultant. The remaining authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.
Bookmark
• Record: found

### Visual Grammar

(2018)
Bookmark
• Record: found

### Alien Information Theory: Psychedelic Drug Technologies and the Cosmic Game

(2019)
Bookmark

### Author and article information

###### Conference
July 2020
July 2020
: 387-395
###### Affiliations
Director LTRC

Principal Research Fellow Ravensbourne University London, UK
###### Article
10.14236/ewic/EVA2020.69

Proceedings of EVA London 2020
EVA 2020
30
London
6th July – 9th July 2020
Electronic Workshops in Computing (eWiC)
AI and the Arts: Artificial Imagination
###### Product
Product Information: 1477-9358BCS Learning & Development
Self URI (journal page): https://ewic.bcs.org/
###### Categories
Electronic Workshops in Computing


text:
The Node Voltage Method is one of the well-organized methods for analyzing a circuit. It is based on Kirchhoff’s Current Law. The Node Voltage Method is embedded inside the popular circuit simulator, $\small \text{SPICE}$.

Written by Willy McAllister.

### Contents

This article teaches you the Node Voltage Method by working through two example circuits. We also figure out how to handle the special case of a floating voltage source (something called a supernode).

Node voltage method

• Assign a reference node (ground).
• Assign node voltage names.
• Solve the nodes with a voltage source connected to the reference node.
• Write Kirchhoff’s Current Law for each node.
• Solve the resulting system of equations.
• Solve the currents.

## The circuit analysis challenge

“Solving a circuit” means figuring out all the voltages and currents in the circuit. At the outset, every circuit element has an unknown voltage and unknown current. For a circuit with $E$ elements, solving the circuit requires us to create and simultaneously solve $2E$ independent equations. Where do we find these equations? Half of them come from individual element $i$-$v$ laws (like Ohm’s Law). The rest come from the connections between elements (represented by KCL or KVL).

No matter what procedure you use to solve a circuit, there is no getting around the requirement to create and solve $2E$ simultaneous equations. This can be a lot of work, but there are ways to organize the effort to make it very efficient. The Node Voltage Method is one of two very efficient procedures we have for solving circuits. (The other is the Mesh Current Method.)

The Node Voltage Method is not mysterious new science. It is simply a procedure for creating the $2E$ equations. We will demonstrate the Node Voltage Method with this circuit,

## Prepare the schematic

Start every circuit analysis by finding and naming all the nodes. Then identify one of the nodes to be the reference node. The reference node is also called the ground node. The potential of the ground node is defined to be $0\,\text V$.

I picked node $\greenD c$ to be the reference node, as shown by the little triangle symbol. Node $\greenD c$ is a good choice because it has lots of connections and the two sources are directly connected.

## Definition: node voltage

To use the Node Voltage Method we need a new term: node voltage. A node voltage is a potential difference measured between the reference node and another node in the circuit. (Up to now, we’ve talked about the voltage across the terminals of a single element. This is called an element voltage (or branch voltage). The concepts are very similar but not identical.)

The example circuit has two node voltages, labeled $\goldD{v_a}$ and $\goldD{v_b}$.

The node voltage arrows always start at the reference node. Each one arcs up to another circuit node, in this case to nodes $a$ and $b$.

A node voltage can also be an element voltage. For example, $v_b$ is a node voltage and also the element voltage for the $5\,\Omega$ resistor, $6\,\Omega$ resistor, and the current source. But notice how the schematic shows no element voltage for the $20\,\Omega$ resistor. It can be derived from the difference of two node voltages, $v_a - v_b$.

## Control the current arrow

Let’s mess around a little with the node voltage concept. Node voltages control the direction of the current arrow! What does that mean?

We didn’t indicate an element voltage for the $20\,\Omega$ resistor. Instead, we can express that element voltage using the two node voltages on either side of the resistor. The element voltage could be written as either,

$\large v_{\text{R}20} = v_a - v_b\qquad$ or $\large \qquad v_{\text{R}20} = v_b - v_a$

We make our choice depending on which way we want the current arrow to point.

Essential skill - The difference expression controls the current arrow.

The element voltage across the $20\,\Omega$ resistor can be written with either $v_a$ or $v_b$ in the first position in the difference equation. Whichever voltage we write first is considered the more positive when we use the sign convention for passive components. The choice of the first voltage term determines the direction of the current arrow. The current arrow points into the resistor terminal with the first voltage term.

Above left, $v_a$ is in the first position. The voltage arrow points towards node $a$, and the current arrow points into node $a$.

Above right, $v_b$ is now in the first position. The voltage arrow is flipped towards node $b$, and the current arrow turns around and points into node $b$.

We are going to use our new skill immediately, to control the direction of the current arrow in the first term of the KCL equation coming up next.

## Node Voltage Method

The Node Voltage Method is this sequence of steps,

• Assign a reference node (ground).
• Assign node voltage names to the remaining nodes.
• Solve the easy nodes, the ones with a voltage source connected to the reference node.
• Write Kirchhoff’s Current Law for each node. Do Ohm’s Law in your head.
• Solve the resulting system of equations to find all the node voltages.
• Solve the currents you want using Ohm’s Law.

### Assign a reference node

We already did this above, but let’s do it again. Our example circuit has three nodes, $\greenD a$, $\greenD b$, and $\greenD c$. Node $\greenD c$ has a lot of connections, $4$, and it connects directly to both sources. This makes it a good candidate to play the role of reference node. Node $\greenD c$ has been marked with the ground symbol so everyone knows our choice for reference node.

### Assign node voltage names

Our circuit has $N=3$ nodes. After picking a reference node, we identify $N-1 = 2$ node voltages and name them $v_a$ and $v_b$, shown above.

Note: There is an obvious opportunity here to simplify the two parallel resistors, $6\,\Omega$ with $5\,\Omega$. I won’t do that because I want to focus on the steps of the Node Voltage Method.

### Solve the easy nodes

Are there any easy nodes? There’s a voltage source connected directly between node $\greenD a$ and the reference node $\greenD c$. That makes $\greenD a$ an easy node. We know right away voltage $v_a = 140\,\text V$.

### Write Kirchhoff’s Current Law for the remaining node(s)

The next step is to write KCL equations for the remaining nodes. For us, that’s just node $\greenD b$.

Essential skill - Scribble on the schematic!
The challenging part of writing KCL equations is getting the signs right. Scribble on the schematic. A lot. Draw voltage signs and current arrows to help you get the signs right in the KCL equation.

Essential skill - Do Ohm’s Law in your head as you write KCL.
As you write each term of the KCL equation, do Ohm’s Law in your head and immediately write the current in terms of node voltages divided by resistance.

Let’s first work out the individual currents flowing in the three resistors connected to node $\greenD b$. Remember, scribbling is good.

I labeled the element voltage on the $20\,\Omega$ resistor with $v_a$ as the leading term, to get the current arrow to point towards the right, flowing into node $b$.

The current flowing into node $b$ from the $20\,\Omega$ resistor is $+\dfrac{(v_a - v_b)}{20}$.

The currents flowing out of node $b$ from the $6\,\Omega$ and $5\,\Omega$ resistors are $\dfrac{v_b}{6}$ and $\dfrac{v_b}{5}$.

The $6\,\Omega$ and $5\,\Omega$ currents will appear in KCL with a negative sign, because I will be using the form of KCL that says “The sum of currents flowing into a node is zero.”. You can do KCL the way you prefer. Either way is fine as long as you pay attention and get the signs right.

The current source is driving its current of $18\,\text A$ into node $b$.

We now write the KCL equation for node $b$,

$\displaystyle \sum_{n=1}^{n=4} i_{in_n} = 0$

$+\dfrac{(v_a - v_b)}{20} - \dfrac{v_b}{6} - \dfrac{v_b}{5} + 18 = 0$

This is the equation we have to solve to find $v_b$ (since we already know $v_a$). Notice how the first and last terms appear with $+$ signs because these currents flow into node $b$, and the two middle terms appear with $-$ signs because they are flowing out.

The Node Voltage Method is pretty cool. Without too much effort, we came up with one equation in one unknown, $v_b$. When we solved this same circuit in a previous article with the improvised application of the fundamental laws, we had to manage $10$ equations with $10$ unknowns. The Node Voltage Method has a built-in efficiency that manages this complexity.

### Solve the node voltages

Our system of equations happens to be just one equation. Let’s solve it to find the node voltage.

$+\dfrac{140}{20} - \dfrac{v_b}{20} - \dfrac{v_b}{6} - \dfrac{v_b}{5} = -18$

$- \dfrac{v_b}{20} - \dfrac{v_b}{6} - \dfrac{v_b}{5} = -18 - 7$

$\left (- \dfrac{3}{60} - \dfrac{10}{60} - \dfrac{12}{60} \right ) \, v_b = -25$

$v_b = -25 \, \left (- \dfrac{60}{25} \right )$

$v_b = 60 \,\text V$

We have all the node voltages, $v_a = 140\,\text V$ and $v_b = 60\,\text V$.

### Solve the unknown currents using Ohm’s Law

Now we can solve the unknown currents using Ohm’s Law.

$i_{20\,\Omega} = \dfrac{(v_a-v_b)}{20} = \dfrac{(140-60)}{20} = 4\,\text A$

$i_{6\,\Omega} = -\dfrac{v_b}{6} = -\dfrac{60}{6} = -10\,\text A \quad$ This current is flowing down through the resistor.

$i_{5\,\Omega} = -\dfrac{v_b}{5} = -\dfrac{60}{5} = -12\,\text A\quad$ This current is flowing down as well.

Ta daaa! The circuit is solved.

You can confirm the answer by simulating this example. Open the link, and click on DC in the to menu to perform a DC analysis. Do a quick mental addition to confirm KCL at node $b$. Do the currents add up to zero?

Is the Node Voltage Method magic?

Going through this Node Voltage Method seemed like a lot less work than creating, managing, and solving a system of $2E$ independent equations with $2E$ unknown voltages and currents. Is this some sort of magic?

No, there is no magic. The Node Voltage Method is simply a cleverly organized way to approach the same $2E$ equations. The main innovations are,

• We are confident we can do Ohm's Law in our heads while writing the KCL equations. Being this quick with Ohm's Law makes it seem like half of the independent equations are no big deal. We used Ohm's Law towards the end to find the resistor currents. This didn't seem like much of a chore, either.
• Using the concept of *node voltage* instead of element voltage is a brilliant move that basically annotates KVL equations right on the schematic, so we don't have to write KVL equations.
• We recognized that a few node voltages have trivial solutions, the ones connected to a voltage source whose other terminal is ground. This typically knocks out one or two equations.
• What remains to solve are the KCL equations at the non-trivial nodes.
How does the Node Voltage Method make the KVL equations "go away"?

With the Node Voltage Method, we don't even bother to write down the KVL equations that are always part of the $2E$ collection. Let's write them anyway and see why.

Our circuit has three meshes, in the left, middle, and right 'windows' of the schematic.

KVL for the left mesh,

$+140 - (140 - v_b) - v_b = 0$

This left mesh equation really illustrates the point of node voltages. We express the voltage across the $20\,\Omega$ resistor in terms of node voltages instead of its own element voltage. With this notation, the equation collapses to $0 = 0$.

KVL for the middle mesh,

$+v_b - v_b = 0$

KVL for the right mesh,

$+v_b - v_b = 0$

All three mesh equations reduce to $0 = 0$ and basically drop out of the procedure. This is what your textbook means if it says something like, "With the Node Voltage Method, the KVL equations are written implicitly on the schematic."

## Guided example

Solve this circuit using the Node Voltage Method.

If you want to work this problem on your own, go for it! Copy this schematic and work through the steps of the Node Voltage Method listed above. Even if you don’t carry the computation all the way through, I encourage you to at least do the steps up to writing the KCL’s.

Assign a reference node.

Assign the reference node.

The node at the bottom of the schematic is a good choice for the reference node, because it has many connections ($3$) and it connect to the negative terminal of the voltage source.

Assign node voltage names to the remaining nodes.

Name the nodes and assign node voltages.

There are three other nodes besides the reference node. I named them $\greenD a$, $\greenD b$, and $\greenD c$, with the corresponding node voltages, $v_a$, $v_b$, and $v_c$.

Solve the easy nodes first.

Solve the easy nodes.

Node $\greenD a$ is an easy node because it connects to a voltage source whose other terminal connects to ground.

We know the voltage at node $\greenD a$ by inspection is $v_a = 75\,\text V$.

Write Kirchhoff’s Current Law for each node. Do Ohm’s Law in your head.

Write Kirchhoff's Current Law for the remaining nodes, with scribbling.

Before writing KCL, it is good practice to scribble notes on the schematic to establish the direction of the current arrows. This helps get the sign and order of the voltage terms right. I'm setting up the current arrows so I can use the form of KCL that sums the currents going into a node.

Take a good look at the numerators of each scribble. Notice how you can pick the order of the voltages to control the direction of the current arrow. Check out how the current in the $10\,\Omega$ resistor is specified two different ways by exchanging the voltage terms.

Node $\greenD b$: $\qquad+\dfrac{v_a - v_b}{25} - \dfrac{v_b}{50} + \dfrac{v_c - v_b}{10} = 0$

Node $\greenD c$: $\qquad+\dfrac{v_a - v_c}{100} + \dfrac{v_b-v_c}{10} - \dfrac{v_c }{25} = 0$

Solve the resulting system of equations for all node voltages.

Solve the system of equations.

I'm going find the two unknown node voltages, $v_b$ and $v_c$, using elimination by multiply and add.

First, tidy up by gathering like terms together, and move the already-solved $v_a$ terms over to the right,

$\text{Node }\greenD b$: $\qquad-\dfrac{v_b}{25} - \dfrac{v_b}{50} - \dfrac{ v_b}{10} + \dfrac{v_c}{10} = -\dfrac{v_a}{25}$

$\text{Node }\greenD c$: $\qquad+\dfrac{v_b}{10} - \dfrac{v_c}{100} - \dfrac{v_c}{10} - \dfrac{v_c }{25} = -\dfrac{v_a}{100}$

Simplify to get a system of two equations in two unknowns,

$\text{Node }\greenD b$: $\qquad-\dfrac{8}{50} v_b + \dfrac{1}{10}v_c = -\dfrac{75}{25} = -3$

$\text{Node }\greenD c$: $\qquad+\dfrac{1}{10}v_b - \dfrac{15}{100} v_c = -\dfrac{75}{100} = -\dfrac{3}{4}$

To eliminate $v_c$, multiply the first equation by $\dfrac{15}{10}$ and add it to the other equation,

\begin{aligned} &\text{Node }\greenD b: &\dfrac{15}{10} \times \biggl [ -\dfrac{8}{50} v_b + \dfrac{1}{10}v_c & = -3 \ \ \biggr ] \\ \\ &\text{Node }\greenD c: &+\biggl [ +\dfrac{1}{10}v_b - \dfrac{15}{100} v_c & = -\dfrac{3}{4} \ \biggr ] \end{aligned}

Multiply through. The $v_c$ terms cancel. Add the equations,

\begin{aligned} &\text{Node }\greenD b: & \biggl [-\dfrac{15 \cdot 8}{10 \cdot 50}\,v_b + \cancel{\dfrac{15\cdot 1}{10 \cdot 10}\,v_c} & = -\dfrac{15 \cdot 3}{10 \cdot 1} \ \biggr ] \\ \\ &\text{Node }\greenD c: &+ \biggl [ +\dfrac{1}{10}v_b - \cancel{\dfrac{15}{100} v_c} & = \,-\dfrac{3}{4} \ \ \biggr ] \\ \\ &\text{Sum}: &\left ( \dfrac{-15 \cdot 8}{500} + \dfrac{1}{10} \right ) \, v_b & = -\dfrac{45}{10}-\dfrac{3}{4} \\ \\ &&\dfrac{-120 + 50}{500}\,v_b &= -\dfrac{90}{20}-\dfrac{15}{20} \\ \\ &&-\dfrac{70}{500}\,v_b &= -\dfrac{105}{20} \\ \\ &&v_b &= -\dfrac{105}{20}\cdot -\dfrac{500}{70} \\ \\ &&v_b &= +37.5\,\text V \end{aligned}

Now go back and plug our new $v_b$ into either of the original KCL equations to find $v_c$,
(I will use the equation for node $\greenD c$.)

\begin{aligned} &\text{Node }\greenD c: &+\dfrac{1}{10}\,v_b - \dfrac{15}{100} v_c &= -\dfrac{3}{4} \\ \\ &&+\dfrac{1}{10}\,37.5 - \dfrac{15}{100} v_c &= -\dfrac{3}{4} \\ \\ &&-\dfrac{15}{100} v_c &= -0.75 - 3.75 \\ \\ &&v_c &= -4.5\cdot -\dfrac{100}{15} \\ \\ &&v_c &= +30\,\text V \end{aligned}

Solve any currents you want to know using Ohm’s Law.

Solve the currents using Ohm's Law.

\begin{aligned} &i_{ab\,25\Omega} = \dfrac{75 - 37.5}{25} &&= 1.5\,\text A &&\text{current arrow pointing to the right.} \\ \\ &i_{bg\,50\Omega} = \dfrac{37.5}{50} &&= 0.75\,\text A &&\text{current arrow pointing down.} \\ \\ &i_{bc\,10\Omega} = \dfrac{37.5-30}{10} &&= 0.75\,\text A &&\text{current arrow pointing to the right.} \\ \\ &i_{ac\,100\Omega} = \dfrac{75-30}{100} &&= 0.45\,\text A &&\text{current arrow pointing to the right.} \\ \\ &i_{cg\,25\Omega} = \dfrac{30}{25} &&= 1.2\,\text A &&\text{current arrow pointing down.} \end{aligned}

As a bonus, the current provided by the voltage source is,

$i_v = i_{100\Omega}+i_{ab\,25\Omega} = 0.45\,\text A + 1.5\,\text A = 1.95\,\text A$

The solved circuit looks like this,

### Simulation model

You can confirm your answer by simulating the guided example circuit. Open the link, and click on DC in the to menu to perform a DC analysis.

## A twist - floating voltage source

Sometimes you come across a circuit where a voltage source does not have either of its terminals connected to the reference node. A source like this is said to be floating. A floating source is a problem for the Node Voltage Method, but it is not too big of a challenge.

In this circuit, battery $\text V_2$ is floating. Let’s use the Node Voltage Method and see what happens.

• The reference node has been selected and marked with the ground symbol.
• The other three nodes have been named and assigned node voltages, $\goldD{v_a}$, $\goldD{v_b}$ and $\goldD{v_c}$.
• Node $\greenD a$ is an easy node, since it is connected to $\text V1$ and then to ground. We immediately know $\goldD{v_a} = \text V_1$.
• The next step is to write a KCL equation for node $b$.

$\quad i_{\text R2} \quad + \quad i_{\text R_3} + i_{\text V_2} = 0$

$\dfrac{(v_a - v_b)}{\text R2} - \dfrac{v_b}{\text R3} + i_{\text V_2}? = 0$

Oops, we have to somehow figure out the current in the floating battery, $i_{\text V_2}$. But the defining equation for the battery does not mention current. Its defining equation is $v = \text V$. There is no $i$ involved. A battery doesn’t tell us what its own current is. So what do we do?

At this point we break away from the standard script for Node Voltage Method, and resort to our own creativity. It is okay to do this. Remember the Node Voltage script nothing more than an efficient way to create simultaneous equations. The floating battery is giving us a little trouble, so we’re going to do a little improvising. Here’s the circuit again,

We make two observations,

• The voltage at node $c$ has a rigid relationship to the voltage at node $b$. Namely, $v_c = v_b + \text V_2$. Let’s add this equation to our system of equations.

• The current in battery $i_{\text V_2}$ is identical to the current in resistor $\text R1$. This gives us a way to figure out $i_{\text V_2}$.

$i_{\text V_2} = i_{\text R_1} = \dfrac{\text V_1 - v_c}{\text R1}$

We know how to express $v_c$ in terms of $v_b$, giving us this expression for $i_{\text V_2}$,

$i_{\text V_2} = \dfrac{\text V_1 - (v_b + \text V_2)}{\text R1}$

Now we can go back and finish up the KCL equation for node $b$.

$\dfrac{(v_a - v_b)}{\text R2} - \dfrac{v_b}{\text R3} + \dfrac{\text V_1 - (v_b + \text V_2)}{\text R1} = 0$

This equation is a little more complicated than usual, but it is still just one equation in one unknown, $v_b$. Once we solve for $v_b$, we use our extra equation to immediately get $v_c$.

$v_c = v_b + \text V_2$

Done! We have the three node voltages. In this floating battery example, we had one easy node, one KCL equation, and one equation representing the interlocked nodes of the floating battery.

If you want to find currents, proceed with Ohm’s Law as we did earlier.

The floating voltage source is a favorite for teachers to put on tests, to see how you respond to an unexpected circuit configuration. We got through the difficulty by being observant and remembering that it is alright to come up with your own extra equation if needed.

### Supernode

This pair of constrained floating nodes is called a supernode. I could have used that term and come up with some rules for what to do. Instead, we resorted to our creativity to work through the puzzle. Some textbooks add extra steps to the Node Voltage Method to account for a supernode. But I like to keep the steps simple and allow myself to mess around and come up with an extra constraint equation when needed.

## Summary

The Node Voltage Method is one of two efficient methods of solving a circuit. This method is embedded inside the popular circuit simulator, $\small \text{SPICE}$. The steps in the Node Voltage Method are,

• Assign a reference node (ground).
• Assign node voltage names to the remaining nodes.
• Solve the easy nodes first, the ones with a voltage source connected to the reference node.
• Write Kirchhoff’s Current Law for each node. Do Ohm’s Law in your head.
• Solve the resulting system of equations to find all the node voltages.
• Solve the currents you want using Ohm’s Law.

If the circuit includes a floating voltage source, come up with an extra equation to account for the unknown current in the voltage source.

format: plain


text:
## Archive for the ‘games’ Category

### Inverse of a hash function

Sunday, March 18th, 2012

I’ve used Thomas Wang’s integer hash functions for years for various purposes. Using techniques invented by Bob Jenkins for general hashing (e.g., hashes of strings), Wang derived several hash specialized for fixed size integer input. His 64-bit version is

``````uint64_t hash(uint64_t key) {
key = (~key) + (key << 21); // key = (key << 21) - key - 1;
key = key ^ (key >> 24);
key = (key + (key << 3)) + (key << 8); // key * 265
key = key ^ (key >> 14);
key = (key + (key << 2)) + (key << 4); // key * 21
key = key ^ (key >> 28);
key = key + (key << 31);
return key;
}
``````

Key properties include avalanche (changing any input bit changes about half of the output bits) and invertibility. Recently I wanted to make explicit use of the inverse, in order to verify that zero would never arise as the hash of a given set of inputs. This property would allow me to initialize the hash table in question (which takes up several gigabytes) with zeros and avoid an explicit occupied bit on each entry. Thus, I needed `inverse_hash(0)`.

Our function is the composition of the functions on each line, so we need to invert each one. Multiplication by 21 and 265 is easy; both numbers are odd, and therefore have multiplicative inverses mod ${2}^{64}$. The rest of the lines are invertible because they’re Feistel functions; they break the key into two pieces, leave one piece alone, run the second function through an invertible function that depends on the first. For example, the line `key = key ^ (key >> 24)` leaves the top 24 bits alone. Once you know the top 24 bits, you can reconstruct the next 24 bits with an xor, and one more round gives the remaining bits. The full inverse is

``````uint64_t inverse_hash(uint64_t key) {
uint64_t tmp;

// Invert key = key + (key << 31)
tmp = key-(key<<31);
key = key-(tmp<<31);

// Invert key = key ^ (key >> 28)
tmp = key^key>>28;
key = key^tmp>>28;

// Invert key *= 21
key *= 14933078535860113213u;

// Invert key = key ^ (key >> 14)
tmp = key^key>>14;
tmp = key^tmp>>14;
tmp = key^tmp>>14;
key = key^tmp>>14;

// Invert key *= 265
key *= 15244667743933553977u;

// Invert key = key ^ (key >> 24)
tmp = key^key>>24;
key = key^tmp>>24;

// Invert key = (~key) + (key << 21)
tmp = ~key;
tmp = ~(key-(tmp<<21));
tmp = ~(key-(tmp<<21));
key = ~(key-(tmp<<21));

return key;
}
``````

The cleverness of the original hash function is that each invertible step is also extremely fast. The inverse is slower, but only moderately.

Finally, I did indeed luck out:

``````inverse_hash(0) = 0x7ffffbffffdfffff
``````

This isn’t a valid pentago board in my packed representation, so zero initialization works. This turned out to be obvious in hindsight: all but the first step in the hash function leaves zero alone, and the last step is complement on the lower 21 bits, which is enough to know that `inverse_hash(0)` can’t be a valid pentago board. It’s still cool to have the full inverse, though.

I tried to email Thomas Wang in case he hadn’t had the occasion to write down the inverse explicitly, but unfortunately his HP email bounced. Impermanent email addresses make me sad.

### Near optimal holdem play with one round of betting

Sunday, December 25th, 2011

Consider the following simplified version of Texas holdem, with two players Alice and Bob:

1. Alice and Bob are each dealt two private cards.

2. Alice posts a small blind of 1, Bob posts a big blind of 2.

3. Alice either folds, calls, or raises by any amount $\ge 2$.

4. Bob either calls or folds.

5. Five more shared cards are dealt, and the winner is determined as usual.

6. Both Alice and Bob have infinite stack sizes, so only expected value matters.

Here’s Alice’s and Bob’s near optimal strategies if Alice only raises integers $\le 40$.  It turns out Alice can leverage her small blind, better advantage to gain an average of at least 0.39776:

one-round-strategy.txt

For Alice, the strategy is a linear combination of actions (‘f’ for fold or ‘b<n>’ for raise by n) for each hand.  For Bob, the strategy is the probability of calling with each hand and each bet by Alice.  These results are definitely optimal for integer bets $\le 40$ to within an expected equity of 1e-4, which I can say with reasonable confidence since it’s much easier to check Nash equilibrium computations then it is to perform them.  It’s also unlikely that Alice could gain all that much more by varying her bet further; she rarely uses the full range of betting options (raising by 40 only with AA and even then only 0.1% of the time, which is likely a numerical error), and I doubt that using fractional bets would dramatically increase her equity.

A few interesting aspects of the results:

1. Alice never folds.  This is clearly an artifact of Bob’s inability to reraise.

2. We have crazy bluffing!  With 63s Alice raises by 15 70% of the time!  63s is slightly worse equity-wise than 85o, but apparently the flush possibilities the bluff worthwhile.

3. Alice’s strategy is extremely nonsmooth, presumably to hide information.  For example, with 87s Alice’s most likely raises are 13 (40% of the time), 16 (10% of the time), and 22 (29% of the time), with small probabilities in between and on either side.  In other words, remembering anything like the optimal strategy looks pretty hopeless (but let me know if you think otherwise!).

Overall, Alice tends to either flat call (around 43% of the time), raise a moderate amount between 4 and 7 (trailing off up to 16), or go all out with a raise of 20 or 21.  The plot follows.  Alice almost never raises by 2 or 3 or more than 23.

It turns out to be possible to compute the optimal strategy for both players by solving a single (though fairly large) linear program.  The case of a simple zero sum game with outcomes given by a payoff matrix is described on Wikipedia; the key is to let one of the players (Alice) rescale their probability vector so that their “expected” outcome ignoring the rescale is at least 1, then minimize the amount of scaling necessary (the sum of the elements of the vector).  A given strategy of Alice’s has utility at least 1 if the utility is at least one for each of Bob’s pure strategies, which gives one linear constraint for each of Bob’s strategies.

In our simplified poker game, the strategies for Alice and Bob can be expressed as a huge Cartesian product over the situations in which they have to decide.  Alice has a choice of bet for each hand she receives, and Bob has a choice of call/fold for each hand and value of Alice’s bet.  The rescaling trick still works in this more general context; we simply let Alice’s probability vector in each situation scale and constrain them to all have the same sum to provide a single global scale.  The constraint of “utility at least 1″ is more complicated, though, since the total number of Bob’s pure strategies is exponential due to the Cartesian product.  To avoid the exponential blowup, we formulate Bob’s response to Alice as its own nested linear program, which gives us a problem of the form

$\underset{x}{\mathrm{min}}{c}^{T}x\phantom{\rule{1em}{0ex}}s.t.\phantom{\rule{1em}{0ex}}\mathrm{Ax}=b,\forall y.Cy=d⇒{x}^{T}Gy\ge 1$

Here $x$ and $y$ are Alice’s and Bob’s strategies, $\mathrm{Ax}=b$ and $\mathrm{Cy}=d$ enforce that probabilities sum to a fixed scaled amount or one, respectively, and ${x}^{T}Gy$ is Alice’s payoff for a given pair of strategies.  See the code for more details if you’re curious; it’s fairly well commented.

Now we get to the cool part: we can apply linear programming duality to turn the universal quantification in the above problem into an existential inequality, which turns the whole thing into a standard linear program.  Thanks to Tomas Tinoco De Rubira for this idea, after I naively asked if it was possible to express nested linear programs in his general convex programming package cvxpy.  Flipping back and forth between universal and existential quantification is the whole point of convex duality: you can prove that a linear program can’t possibly have value greater than $v$ by exhibiting a single feasible solution to the dual program.  Strong duality has to hold to get an exact match, which we have in our case since the subprograms are always feasible.  Again, I’ll leave all the details to the comments in the code.

The unfortunate part is lack of sparsity: the payoff matrix $G$ in the above convex program (which remains after we dualize into a linear program) has $O\left({n}^{2}m\right)$ nonzeros, where $n=169$ is the number of holdem hands and $m$ is the number of Alice’s possible bets.  It’s possible to store the relevant information in only $O\left({n}^{2}+m\right)$ space, but impossible to compute a matrix vector multiply with it faster than $O\left({n}^{2}m\right)$ without using asymptotically faster (meaning slow) matrix multiplication.  If I write a bunch of structure-aware code it’s possible to take advantage of structure to solve the resulting KKT systems required for linear programming in low constant $O\left({n}^{2}m\right)$ time and $O\left({n}^{2}+m\right)$ space as well, but write now I’m expanding the whole thing out into an explicit sparse matrix and passing it to cvxopt, which causes a bunch of extra blowup via sparse factorization.  Bad.

Thus, without (fun but time consuming) structure awareness, my laptop is unable to scale beyond 40 bet options for Alice, and more importantly to the more interesting case of Bob retaliating with another round of betting.  However, the current structure wouldn’t suffer any additional cost for two rounds of betting each with $⌊\sqrt{40}⌋=6$ rounds of betting, so that’s something to try next.

### Minimal continuous poker

Sunday, November 13th, 2011

Consider the following poker-like game, played with two players: Alice and Bob.  Bob posts a blind of 1.  Both players are dealt a single, continuous hand chosen uniformly at random from $\left[0,1\right]$.  Alice can fold, call, or raise any amount $b>0$ (calling means $b=0$).  Bob either calls or folds.

My original plan was to work out the Nash equilibrium for this game, and therefore derive interesting smooth curves describing the optimal way for Alice to bluff and generally obscure her hand.  It didn’t quite work out that way, but the result is still interesting.

Let $A$ be the optimal expected payoff for Alice, $A\left(x\right)$ the optimal expected payoff given Alice’s specific hand x.  Clearly A(x) is a weakly increasing function of x; if x’ > x but A(x’) < A(x), Alice can improve A(x’) to A(x) by pretending she has hand x and using the same strategy.  If A(x) > 0 for some x, so that Alice’s optimal strategy is better than folding, then Alice will never fold since any nonzero probability of folding would reduce her utility.  Thus there is a threshold hand ${x}_{t}$ below which Alice always folds (technically, always “might as well” fold, but we’ll gloss over this detail for the moment), and above which Alice always calls but might vary the amount she raises by.  A similar argument applied to Bob gives a threshold function ${y}_{t}\left(b\right)$ s.t. Bob folds if $y<{y}_{t}\left(b\right)$ and calls if $y>{y}_{t}\left(b\right)$.

These and other similar preliminaries aside, I spent a while banging my head against the wall before temporarily giving up and picking a simpler game.  Specifically, make the bet $b$ a fixed constant.  If $b=0$, Bob always checks, and Alice’s optimal strategy is (unsurprisingly) to call if $x>1/2$.  This gives a payoff of $A=1/4$.  If $b>0$, Bob’s function ${y}_{t}\left(b\right)$ is a constant. The values of ${x}_{t}$, ${y}_{t}$, and $A$ at the Nash equilibrium turn out to be

$\begin{array}{rl}{x}_{t}=& \frac{2+2b+{b}^{2}}{\left(2+b{\right)}^{2}}\\ {y}_{t}=& \frac{1+b}{2+b}\\ A=& \frac{2+2b}{\left(2+b{\right)}^{3}}\end{array}$

A few notes: for any $b>0$, ${x}_{t}<{y}_{t}$, since Bob knows Alice’s threshold and gains nothing by calling with hands only slightly over ${x}_{t}$.  Interestingly, Alice’s payoff remains unchanged if she varies her threshold anywhere satisfying ${x}_{t}<{y}_{t}$; the particular value of ${x}_{t}$ is only prevents Bob from increasing his utility with a different value of ${y}_{t}$.  However, the most important property of this result is that $A$ is a decreasing function of $b$.  If the bet is fixed, Alice would prefer it to be zero so that $A=1/4$.

Now back the general game, where Alice chooses the bet.  We have $A\ge 1/4$, since Alice can choose to always call or fold.  Can she do better, varying the bet in some exotic fashion so as to milk more money out of Bob while keeping her hand disguised?  Well, no.  Update: After disproving a conjecture (see below), the answer is maybe.

Let’s see what happens if Bob follows the optimal strategy from the fixed $b$ game, calling if $y>\left(1+b\right)/\left(2+b\right)$ and folding otherwise. Since Bob’s strategy is fixed, Alice can maximize her utility without any extra randomness, and we need only consider bets which are a deterministic function of $x$.  For $x<{x}_{t}$ she folds and $A\left(x\right)=0$, for $x>{x}_{t}$ she bets $b=b\left(x\right)$ with payoff

$\begin{array}{rl}A\left(x\right)=& 1\mathrm{Pr}\left({y}_{t}>y\right)+\left(1+b\right)\mathrm{Pr}\left(x>y>{y}_{t}\right)-\left(1+b\right)\mathrm{Pr}\left(y>x,{y}_{t}\right)\\ =& {y}_{t}+\left(1+b\right)\mathrm{max}\left(0,x-{y}_{t}\right)-\left(1+b\right)\left(1-\mathrm{max}\left(x,{y}_{t}\right)\right)\\ =& {y}_{t}+\left(1+b\right)\mathrm{max}\left(0,x-{y}_{t}\right)-\left(1+b\right)+\left(1+b\right)x+\left(1+b\right)\mathrm{max}\left(0,{y}_{t}-x\right)\\ =& {y}_{t}+\left(1+b\right)\left(x-1\right)+\left(1+b\right)|x-{y}_{t}|\\ \end{array}$

Differentiating w.r.t. $b$,

$\begin{array}{rl}A\left(x\right)\prime =& x-1+{y}_{t}\prime +|x-{y}_{t}|+\left(1+b\right)\mathrm{sgn}\left({y}_{t}-x\right){y}_{t}\prime \\ {y}_{t}\prime =& \frac{1}{2+b}-\frac{1+b}{\left(2+b{\right)}^{2}}=\frac{1-{y}_{t}}{2+b}\end{array}$

If $x<{y}_{t}$, this becomes

$\begin{array}{rl}A\left(x\right)\prime =& x-1+{y}_{t}\prime +{y}_{t}-x+\left(1+b\right){y}_{t}\prime \\ =& -1+\left(2+b\right)\left(1-{y}_{t}\right)/\left(2+b\right)+{y}_{t}\\ =& -1+1-{y}_{t}+{y}_{t}=0\end{array}$

so if $x<{y}_{t}$, Alice’s bet doesn’t matter.  If $x>{y}_{t}$, we have

$\begin{array}{rl}A\left(x\right)\prime =& x-1+{y}_{t}\prime +x-{y}_{t}-\left(1+b\right){y}_{t}\prime \\ =& 2x-1-b{y}_{t}\prime -{y}_{t}\\ =& 2x-1-b\left(1-{y}_{t}\right)/\left(2+b\right)-{y}_{t}\\ =& 2x-1-b/\left(2+b\right)+b\left(1+b\right)/\left(2+b{\right)}^{2}-\left(1+b\right)/\left(2+b\right)\\ =& 2x-1-\frac{2b+{b}^{2}-b-{b}^{2}+2+3b+{b}^{2}}{\left(2+b{\right)}^{2}}\\ =& 2x-1-\frac{2+4b+{b}^{2}}{\left(2+b{\right)}^{2}}\\ =& 2x-2+\frac{2}{\left(2+b{\right)}^{2}}\\ \end{array}$

which is negative as $b→\infty$ and zero at $b=\sqrt{1/\left(1-x\right)-2}$.

Thus $A\left(x\right)\prime =0$ iff $\left(2+b{\right)}^{2}=1/\left(1-x\right)$, or

$b=\sqrt{\frac{1}{1-x}-2}$

Unfortunately for Bob, $A\left(x\right)\prime >0$ at $b=0$ iff $2x-2+1/2>0$ iff $x>3/4$.  Thus Alice can beat $A=1/4$ by increasing her bet whenever $x>3/4$.  Abandoning hand calculation and turning to Mathematica, it turns out Alice’s optimal strategy achieves $A=7/24\approx .29$.

So, we haven’t found the Nash equilibrium yet, but at least our minimal poker game isn’t (necessarily) incredibly boring.  More analysis is required.  For pretty pictures’ sake, here’s a plot of Alice’s outcome as $x$ and $b$ vary:

Alice's expected outcome for hand x and bet b


text:
# November, 2015

## Ask Uncle Colin: Is my friend crazy?

Dear Uncle Colin, A friend of mine told me that $1 + 2 + 4 + 8 + ... = -1$. Is he crazy, or is there something going on here? -- Somehow Enumerating Ridiculous Infinitely Extended Sum Dear SERIES, There are a couple of 'proofs' of this non-fact that

## Review: Sumaze

Even as someone who owes at least some of his maths skills to computer games (I played L in the late 80s and would love to see it resurrected, and there's a lot to be said for the mental arithmetic in something like Football Manager), my heart still sinks a

## Rewriting a function without going piecewise

You know the ridiculous kind of pseudo-context question that makes you go 'Why doesn't Lisa get a proper hobby rather than timing her friends doing jigsaw puzzles?'? You could replace pretty much all of them with "A mathematician is trying to be clever by...". In this particular case, a mathematician


text:
Bastian Bloessl, Florian Klingler, Fabian Missbrenner and Christoph Sommer, "A Systematic Study on the Impact of Noise and OFDM Interference on IEEE 802.11p," Proceedings of 9th IEEE Vehicular Networking Conference (VNC 2017), Torino, Italy, November 2017, pp. 287-290.

### Abstract

To design, test, and evaluate applications for Vehicular Ad Hoc Networks (VANETs), researchers rely heavily on network simulations. These allow conducting experiments in a fast, cheap, and reproducible manner. In general, the accuracy of simulation results depends to a large degree on the quality of the simulation models. Here, the model of the physical layer is particularly crucial for the realism of the results. Given its relevance, it is unfortunate that there is a dispute within the community on how interference should be modeled. To fill this gap, we conduct a systematic study of the IEEE802.11p physical layer in which we cross-validate results from simulations, off-the-shelf devices, and lab equipment. The results of these experiments are all coherent and indicate that intra-technology interference, i.e., interference from other IEEE802.11p devices, has a similar impact than noise. Treating interference like noise is, therefore, not just a simplification that is adopted by many network simulators, but accurately captures reality.

### Quick access

Original Version (at publishers web site)
Authors' Version (PDF on this web site)
BibTeX

### Contact

Bastian Bloessl
Florian Klingler
Fabian Missbrenner
Christoph Sommer

### BibTeX reference

@inproceedings{bloessl2017systematic,     address = {Torino, Italy},     author = {Bloessl, Bastian and Klingler, Florian and Missbrenner, Fabian and Sommer, Christoph},     booktitle = {9th IEEE Vehicular Networking Conference (VNC 2017)},     doi = {10.1109/VNC.2017.8275633},     month = {November},     pages = {287-290},     publisher = {IEEE},     title = {{A Systematic Study on the Impact of Noise and OFDM Interference on IEEE 802.11p}},     year = {2017},    }

## Copyright notice

Links to final or draft versions of papers are presented here to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted or distributed for commercial purposes without the explicit permission of the copyright holder.

The following applies to all papers listed above that have IEEE copyrights: Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

The following applies to all papers listed above that are in submission to IEEE conference/workshop proceeedings or journals: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

The following applies to all papers listed above that have ACM copyrights: ACM COPYRIGHT NOTICE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or permissions@acm.org.

The following applies to all SpringerLink papers listed above that have Springer Science+Business Media copyrights: The original publication is available at www.springerlink.com.


text:
# Gower distance with R functions; “gower.dist” and “daisy”

I have 9 numeric and 5 binary (0-1) variables, with 73 samples in my dataset. I know that the Gower distance is a good metric for datasets with mixed variables.

I tried both daisy(cluster) and gower.dist(StatMatch) functions. We can assign weights in both fuctions; I assigned weights like that; 5 weights for numeric attributes and 1 for binary ones.

But they give different distance matrixes. Shouldn't they give the same results?
These are my features and first sample.

A    B      C   D   E   F   G   H    I       J       K   L       M       N
800 1200    0   0   0   0   1   2   0.31    0.33    0.1 0.62    0.35    0.44

A; Numeric (Square feet) B; Numeric (Dollar) C-D-E-F-G; Binary (Yes-No) H; Numeric (Number of children) J-K-L-M-N Numeric (Percent)

They in fact do give the same results. I am not sure how you are comparing them but here is an example:

# Create example data
set.seed(123)
# create nominal variable
nom <- factor(rep(letters[1:3], each=10))
# create numeric variables
vars <- as.matrix(replicate(17, rnorm(30)))
df <- data.frame(nom, vars)

library(cluster)
daisy.mat <- as.matrix(daisy(df, metric="gower"))

library(StatMatch)
gower.mat <- gower.dist(df)

# you can look directly to see the numbers are the same

# now identical will return FALSE, why?
identical(daisy.mat, gower.mat)
> identical(daisy.mat, gower.mat)
[1] FALSE

# This is because there is of extremely small differences
# in the numbers returned by the different functions
max(abs(daisy.mat - gower.mat))
> max(abs(daisy.mat - gower.mat))
[1] 5.551115e-17

# Using all.equal has a higher tolerance threshold
all.equal(daisy.mat, gower.mat, check.attributes = F)
> all.equal(daisy.mat, gower.mat, check.attributes = F)
[1] TRUE

Now that I understand you are adding an extra component to the daisy function there is still a solution. It lies in the documentation for gower.dist. The key part is in the first part of the documentation, namely that columns of mode logical will be considered as binary asymmetric variables. So you want to make sure your data structure is appropriate.

set.seed(123)
# create nominal variable
nom <- factor(rep(letters[1:3], each=10))
# create binary variables
bin <- as.matrix(replicate(5, rep(sample(c(0,1), 30, replace=T))))
# create numeric variables
vars <- as.matrix(replicate(9, rnorm(30)))
df <- data.frame(nom, bin, vars)

# You can see that the columns are not 'logical' types
# We need to change this
str(df)
> str(df)
'data.frame':   30 obs. of  15 variables:
$nom : Factor w/ 3 levels "a","b","c": 1 1 1 1 1 1 1 1 1 1 ...$ X1  : num  0 1 0 1 1 0 1 1 1 0 ...
$X2 : num 1 1 1 1 0 0 1 0 0 0 ...$ X3  : num  1 0 0 0 1 0 1 1 1 0 ...
$X4 : num 0 1 0 1 0 0 1 0 0 1 ...$ X5  : num  1 0 0 0 0 1 0 0 0 1 ...
$X1.1: num 1.026 -0.285 -1.221 0.181 -0.139 ...$ X2.1: num  -0.045 -0.785 -1.668 -0.38 0.919 ...
$X3.1: num 1.13 -1.46 0.74 1.91 -1.44 ...$ X4.1: num  0.298 0.637 -0.484 0.517 0.369 ...
$X5.1: num 1.997 0.601 -1.251 -0.611 -1.185 ...$ X6  : num  0.0597 -0.7046 -0.7172 0.8847 -1.0156 ...
$X7 : num -0.0886 1.0808 0.6308 -0.1136 -1.5329 ...$ X8  : num  0.134 0.221 1.641 -0.219 0.168 ...
$X9 : num 0.704 -0.106 -1.259 1.684 0.911 ... # make columns logical df[,2:6] <- sapply(df[,2:6], FUN=function(x) ifelse(x==1, TRUE, FALSE)) # now the columns are the correct types > str(df) 'data.frame': 30 obs. of 15 variables:$ nom : Factor w/ 3 levels "a","b","c": 1 1 1 1 1 1 1 1 1 1 ...
$X1 : logi FALSE TRUE FALSE TRUE TRUE FALSE ...$ X2  : logi  TRUE TRUE TRUE TRUE FALSE FALSE ...
$X3 : logi TRUE FALSE FALSE FALSE TRUE FALSE ...$ X4  : logi  FALSE TRUE FALSE TRUE FALSE FALSE ...
$X5 : logi TRUE FALSE FALSE FALSE FALSE TRUE ...$ X1.1: num  1.026 -0.285 -1.221 0.181 -0.139 ...
$X2.1: num -0.045 -0.785 -1.668 -0.38 0.919 ...$ X3.1: num  1.13 -1.46 0.74 1.91 -1.44 ...
$X4.1: num 0.298 0.637 -0.484 0.517 0.369 ...$ X5.1: num  1.997 0.601 -1.251 -0.611 -1.185 ...
$X6 : num 0.0597 -0.7046 -0.7172 0.8847 -1.0156 ...$ X7  : num  -0.0886 1.0808 0.6308 -0.1136 -1.5329 ...
$X8 : num 0.134 0.221 1.641 -0.219 0.168 ...$ X9  : num  0.704 -0.106 -1.259 1.684 0.911 ...

# now you can do your calls
daisy.mat <- as.matrix(daisy(df, metric="gower", type=list(asymm=c(2,3,4,5,6))))
gower.mat <- gower.dist(df)

# and you can see that the results are the same
all.equal(as.matrix(daisy.mat), gower.mat, check.attributes = F)
[1] TRUE

• Thank you Dr. Determan. Yes, they gave the same results if I do not specify in "daisy" function that my binary variables are asymmetric. So "daisy" got them as Interval. As I understood we cannot specify variable type to "gower.dist" function. – Emrah Bilgiç Nov 13 '14 at 1:55
• @EmrahBilgiç, Can you provide a reproducible example? – cdeterman Nov 13 '14 at 13:14
• Dr. Determan, you can see my data below my question. I can not specify my binary variables in "gower.dist" function I think. First code for gower.dist function: > gower.dist <-gower.dist(mydata) And second code for daisy function: > daisy <- daisy(mydata,metric="gower",type=list(asymm=c(3,4,5,6,7))) – Emrah Bilgiç Nov 13 '14 at 17:13
• Dr.Determan, as I understood, both fuctions are automatically making the required standardation for my mixed type variables. – Emrah Bilgiç Nov 13 '14 at 17:16
• @EmrahBilgiç, see above, you can in fact specify binary variables with gower.dist – cdeterman Nov 13 '14 at 17:32

Yes, They give the same result, just as proven by cdeterman.

One different I want to mention here is "gower.dist" actually use some kind of equal weights method (what they called weights in the function documents can only be 0 or 1), but "daisy" allow you to pass your weight vector by argument 'weights'.

Conclusion: If you want a more flexible way to calculate Gower Dissimilarity, I prefer using "daisy" from package "cluster". If you your main interest is building a synthetic dataset, use "gower.dist", it will save you a lot of time by direct using "NND.hotdeck".


text:
## A new year has started. Let’s look into the stars!

2019 started recently and everyone is exited what the new year will bring, thus, I would like to look into the stars with you. In a more scientific way than usual…

My name is Bernadett Stadler and I studied Industrial Mathematics at the Johannes Kepler University in Linz. Since May last year I am part of the ROMSOC program as a PhD student. I am involved in a cooperation of the university in Linz and the company Microgate in Bolzano. My research addresses the improvement of the image quality of extremely large telescopes. The goal is to enable a sharper view of more distant celestial objects.

### Extremely Large Telescope

The European Extremely Large Telescope (ELT) is a revolutionary scientific project for a 39m telescope that will allow to address many exiting unsolved questions about our Universe. Especially, the fundamental question of humanity: Are we alone?

The ELT is currently built by the European Southern Observatory (ESO) in the Atacama Desert in Chile and will be the largest optical/near-infrared telescope in the world. It will extend astrophysical knowledge by enabling studies of planets around other stars, the first galaxies in the Universe, supermassive black holes, and the nature of the Universe’s dark sector. To achieve all these goals, the telescope has to provide a sharp image that is not affected by atmospheric turbulences. That’s where my research topic comes into play.

Adaptive Optics (AO) systems correct optical distortions of the wavefront caused by atmospheric turbulences, e.g., wind or temperature differences. For that purpose, the atmosphere needs to be known sufficiently.

How can this be handled inside the system?
Light from a bright guide star, that can be either a star in the sky or an artificial star generated by a powerful laser beam, is used as a reference. A wavefront sensor indirectly measures the distortions of the wavefront using the light from guide stars. Subsequently, the wavefront is corrected utilizing deformable mirrors to obtain an image with excellent quality.

What is needed is a difficult but mathematically very interesting step. How to reconstruct the turbulence profile in the atmosphere and, subsequently, how to deform the mirror such that it corrects the wavefront. At that point, we need to go a little deeper into my research topic.

### Atmospheric Tomography

Atmospheric Tomography is the fundamental problem in many AO systems. Assuming a layered model of the atmosphere, the goal of the atmospheric tomography problem is to reconstruct the turbulent layers from the wavefront sensor measurements. Mathematically, such problems are ill-posed, i.e., the recovery of the solution from noisy measurements is unstable. Moreover, with such a huge telescope as the ELT several new challenges occur. The complex setup of such a system, in particular, the huge amount of data that has to be
processed in real-time, lead to non-trivial conditions on the algorithms. In my daily work, I am dealing with the development and efficient implementation of such algorithms.

I hope that after this brief insight into my research topic you are as excited about the project as I am and equally curious if we can find some aliens with the help of the ELT within the next years.

## A Trace of Christmas..

The upcoming Christmas season gives us an opportunity to stop for a moment and reflect about our daily activities, also those within the ROMSOC program. Very often, we find traces of Christmas in the most unexpected places, including our projects.

My name is Jonasz Staszek and I am currently working with Friedrich-Alexander-Universität Erlangen-Nürnberg as the ROMSOC ESR7 on a problem related strongly to the railways, in particular to the optimal employment of resources in cross-border rail traffic. In this blog entry, I would like to tell you a little about my project, the method I plan to use and the trace of Christmas in it.

The Problem

Citizens and residents of the European Union enjoy the right of freedom of movement and economic activity. Our companies also benefit from this while doing business abroad from their home country. In many cases though, both individuals and companies would not be able to benefit from these rights if appropriate technology, allowing mobility of people and goods, was not in place.

Numerous historical considerations are the source of various difficulties of railway carriers nowadays. Early on, each enterprise introducing railways chose the technology to suit its needs the best. Later in the 19th and 20th centuries, as railway companies were nationalized, each country made its own bold (and often costly) decisions about standardizing the railway system on its territory.

We face the consequences of such historical developments up until today and things are not likely to change in the near future, mainly due to enormous costs of such transformations. For example gauge, or the distance between rails on a track, is standardized nearly everywhere in Europe at 1435 mm, with the exception of Spain, Portugal, Finland and former USSR republics (1520/1524 mm). Another structural difference occurs with regard to power supply for electric locomotives – only in the EU we have five such systems. Yet another example could be drawn from all kinds of varying regulations in each individual state with regard to training and licensing of the drivers, mandatory safety systems installed on the network and in the locos, access to the railway network (e.g. a right to ride a train on a given section of the country’s network), etc.

Clearly, too many differences exist for an international railway carrier to be able to manage its resources centrally. Each country, with its specific railway system, usually has its own carrier(s), network manager(s) as well as driver training systems and safety regulations. Hence, international carriers usually have a separate entity to manage rail traffic on the territory of each respective country. Consequently, the decisions on the deployment of resources on certain trains are made in a dispersed fashion – by far and large each entity takes them on its own within the area of its responsibility. This could lead to a suboptimal use of the existing assets.

In my research, I intend to tackle exactly this problem – given the set of trains from point A to point B (not necessarily in the same country) ordered by the customers of a railway carrier and the existing resource base (locos and drivers), find the optimal (e.g. minimizing costs or maximizing utilization) attribution of assets to the connections to be carried out.

The solution approach

As the Christmas season is already very close, let me illustrate the way I intend to approach this problem with the use of a nice puzzle developed by my colleagues at FAU Erlangen-Nürnberg – please click here for the interactive version. This is a puzzle used in a competition organized by my chair every Christmas – for each correct solution a certain amount of money is transferred to a good cause.

The task is about colouring the balls in blue, red or yellow in such a way that no two connected balls get the same colour. In mathematical terms, we are dealing with a graph colouring problem here – we have an undirected graph G = (V, E) with  nodes and  edges which needs to be coloured with the colours from the set C with colours. We already know the colour for two of the nodes. Hence, we are looking for an attribution of the colour to the nodes  such that the following criteria are met:

• Each node v is coloured with exactly one colour:

$\sum_{k=1}^{|C|}x_{ik}=1\quad&space;\forall&space;i\in&space;V$

• No neighbour is coloured with the same colour

$x_{ik}+x_{jk}\leq&space;1,\quad\forall&space;(i,j)\in&space;E,\,\forall&space;k\in&space;C.$

• is a binary variable:

$x_{ik}\in&space;\{0,1\}\quad\forall&space;i\in&space;V,\,\forall&space;k\in&space;C$

To draw a connection between the Christmas tree and the resource allocation problem, we could think of the colours as the trains which need to run, the nodes as the resources and the edges as conflicts which prohibit the employment of a pair of resources on a given train (e.g. a driver not licensed for a given loco, a loco unable to operate on a given section of the network, etc.).

Such model formulations are frequently seen in the optimization of problems related to railways [1], [2], [3], [4]. They have primarily been used for train scheduling problems, e.g. helping dispatchers select the order in which trains should use platforms in a station. It is also popular as a modelling and optimization structure in other areas – it becomes increasingly useful as a method of optimizing the use of LTE transmission frequencies [5] [6].

After this small glimpse into my research, I wish you a blessed Christmas time this year, full of Lebkuchen (gingerbread) and Glühwein (mulled wine)!

References:

[1]  Lusby, Richard M., et al. “Railway Track Allocation: Models and Methods.” OR Spectrum, vol. 33, no. 4, 2009, pp. 843–883., doi:10.1007/s00291-009-0189-0.

[2] Cardillo, Dorotea De Luca, and Nicola Mione. “k L-List λ Colouring of Graphs.” European Journal of Operational Research, vol. 106, no. 1, 1998, pp. 160–164., doi:10.1016/s0377-2217(98)00299-9.

[3] Billionnet, Alain. “Using Integer Programming to Solve the Train-Platforming Problem.” Transportation Science, vol. 37, no. 2, 2003, pp. 213–222., doi:10.1287/trsc.37.2.213.15250.

[4] Cornelsen, Sabine, and Gabriele Di Stefano. “Track Assignment.” Journal of Discrete Algorithms, vol. 5, no. 2, 2007, pp. 250–261., doi:10.1016/j.jda.2006.05.001.

[5] Tsolkas, Dimitris, et al. “A Graph-Coloring Secondary Resource Allocation for D2D Communications in LTE Networks.” 2012 IEEE 17th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), 2012, doi:10.1109/camad.2012.6335378.


text:
Efficient Encryption from Random Quasi-Cyclic Codes

Carlos Aguilar, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, and Gilles Zémor

Abstract

We propose a framework for constructing efficient code-based encryption schemes from codes that do not hide any structure in their public matrix. The framework is in the spirit of the schemes first proposed by Alekhnovich in 2003 and based on the difficulty of decoding random linear codes from random errors of low weight. We depart somewhat from Aleknovich's approach and propose an encryption scheme based on the difficulty of decoding random quasi-cyclic codes. We propose two new cryptosystems instantiated within our framework: the Hamming Quasi-Cyclic cryptosystem (HQC), based on the Hamming metric, and the Rank Quasi-Cyclic cryptosystem (RQC), based on the rank metric. We give a security proof, which reduces the IND-CPA security of our systems to a decisional version of the well known problem of decoding random families of quasi-cyclic codes for the Hamming and rank metrics (the respective QCSD and RQCSD problems). We also provide an analysis of the decryption failure probability of our scheme in the Hamming metric case: for the rank metric there is no decryption failure. Our schemes benefit from a very fast decryption algorithm together with small key sizes of only a few thousand bits. The cryptosystems are very efficient for low encryption rates and are very well suited to key exchange and authentication. Asymptotically, for $\lambda$ the security parameter, the public key sizes are respectively in $\mathcal{O}({\lambda}^2)$ for HQC and in $\mathcal{O}(\lambda^{\frac{4}{3}})$ for RQC. Practical parameter compares well to systems based on ring-LPN or the recent MDPC system.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Code-based CryptographyPublic-Key EncryptionPost-Quantum CryptographyProvable Security
Contact author(s)
jean-christophe deneuville @ unilim fr
History
Short URL
https://ia.cr/2016/1194

CC BY

BibTeX

@misc{cryptoeprint:2016/1194,
author = {Carlos Aguilar and Olivier Blazy and Jean-Christophe Deneuville and Philippe Gaborit and Gilles Zémor},
title = {Efficient Encryption from Random Quasi-Cyclic Codes},
howpublished = {Cryptology ePrint Archive, Paper 2016/1194},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/1194}},
url = {https://eprint.iacr.org/2016/1194}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.