Monday, December 17, 2012
latex and bibtex
1 create a file .bib.
2 in the lyx file, the bottom of it, insert --- insert list/toc --- bibtex
note: the year-author problem.
setting --- biblio... --- citation style -> default.
Friday, December 7, 2012
john carmack quotes.
Focused, hard work is the real key to success. Keep your eyes on the goal, and just keep taking the next step towards completing it. If you aren't sure which way to do something, do it both ways and see which works better.
focus is a matter of deciding what things you're not going to do.
focus is a matter of deciding what things you're not going to do.
Wednesday, December 5, 2012
FSM Verilog project, Two FPGA transmission.
This project is to letting FPGA transmission, the final result:
reset FPGA A and B,
NOTE: about write FSM, usually we have 3 always blocks.
1. transition cur_state <= next_state, sequential, using <= statement.
2. what is the next_state? this part should be combinational, the sensitivity list should be any signal that could change the next_state, see following codes for examples. Inside this block, the code should be blocking using =.
3. what should we do in each state? this part is sequential, like a DFF device, using <=.
//---------------------Final functionality.
FPGA A set switches and push button, B's leds should lit up according to A's switches.
B set sw and push button, A's leds should lit up according to B's switches.
//-------------------data pattern:
uart_tx: 1 when idle, startBit 0, 8bit data, 1bit parity, 1bit stopbit (high)
//-----------------------transmitter.
`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Engineer: Wenshuai Hou
// transmitter: when the button is pressed, it reads the 8bit value from the SW, send it out serially through uart_tx, and wait for rx_done for 15cycles, if not acked, retransmit.
module transmitter(
input clock_50M,
input reset,
input [7:0] sw,
input rx_done,
input btn,
output reg uart_tx
);
parameter [1:0] IDLE = 0,
XMIT = 1,
ACK = 2;
reg [1:0] curr, next;
reg [3:0] count, waiting;
// this always block is always sequential, <=
always @ (posedge clock_50M or posedge reset) begin
if(reset == 1) curr <= IDLE;
else curr <= next;
end
//this one determines the next_state, should be combinational.
always @ (curr or btn or count or waiting or rx_done) begin
case(curr)
IDLE:
next = (btn == 1)? XMIT: IDLE;
XMIT:
next = (count == 0)? ACK: XMIT;
ACK: begin
if(rx_done == 1)
next = IDLE;
else if(rx_done == 0 && waiting < 15)
next = ACK;
else
next = XMIT;
end
endcase
end
// this always block determines what the FSM does in each state.
reg [10:0] tx_data;
always @ (posedge clock_50M) begin
case(curr)
IDLE:
begin
uart_tx <= 1;
count <= 10;
waiting <= 0;
tx_data <= {1'b0, sw, (^sw), 1'b1};
end
XMIT:
begin
uart_tx <= tx_data[count];
count <= count - 1;
waiting <= 0;
end
ACK:
begin
uart_tx <= 1;
waiting <= waiting + 1;
count <= 10;
end
endcase
end
endmodule
reset FPGA A and B,
NOTE: about write FSM, usually we have 3 always blocks.
1. transition cur_state <= next_state, sequential, using <= statement.
2. what is the next_state? this part should be combinational, the sensitivity list should be any signal that could change the next_state, see following codes for examples. Inside this block, the code should be blocking using =.
3. what should we do in each state? this part is sequential, like a DFF device, using <=.
//---------------------Final functionality.
FPGA A set switches and push button, B's leds should lit up according to A's switches.
B set sw and push button, A's leds should lit up according to B's switches.
//-------------------data pattern:
uart_tx: 1 when idle, startBit 0, 8bit data, 1bit parity, 1bit stopbit (high)
//-----------------------transmitter.
`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Engineer: Wenshuai Hou
// transmitter: when the button is pressed, it reads the 8bit value from the SW, send it out serially through uart_tx, and wait for rx_done for 15cycles, if not acked, retransmit.
module transmitter(
input clock_50M,
input reset,
input [7:0] sw,
input rx_done,
input btn,
output reg uart_tx
);
parameter [1:0] IDLE = 0,
XMIT = 1,
ACK = 2;
reg [1:0] curr, next;
reg [3:0] count, waiting;
// this always block is always sequential, <=
always @ (posedge clock_50M or posedge reset) begin
if(reset == 1) curr <= IDLE;
else curr <= next;
end
//this one determines the next_state, should be combinational.
always @ (curr or btn or count or waiting or rx_done) begin
case(curr)
IDLE:
next = (btn == 1)? XMIT: IDLE;
XMIT:
next = (count == 0)? ACK: XMIT;
ACK: begin
if(rx_done == 1)
next = IDLE;
else if(rx_done == 0 && waiting < 15)
next = ACK;
else
next = XMIT;
end
endcase
end
// this always block determines what the FSM does in each state.
reg [10:0] tx_data;
always @ (posedge clock_50M) begin
case(curr)
IDLE:
begin
uart_tx <= 1;
count <= 10;
waiting <= 0;
tx_data <= {1'b0, sw, (^sw), 1'b1};
end
XMIT:
begin
uart_tx <= tx_data[count];
count <= count - 1;
waiting <= 0;
end
ACK:
begin
uart_tx <= 1;
waiting <= waiting + 1;
count <= 10;
end
endcase
end
endmodule
//-----------------------receiver part
//////////////////////////////////////////////////////////////////////////////////
// Company:
// Engineer: Wenshuai Hou
//////////////////////////////////////////////////////////////////////////////////
module reveiver(
input clock_50M,
input reset,
input uart_rx, //serial input
output reg tx_done, //ack to the transmitter
output reg [7:0] leds //lit up the LEDS based on the received word.
);
parameter [1:0] IDLE = 0,
READ = 1,
ACK = 2;
reg [1:0] curr, next;
reg [9:0] rx_data;
reg [3:0] count;
always @ (posedge clock_50M or posedge reset) begin
if(reset == 1) curr <= IDLE;
else curr <= next;
end
always @ (curr or uart_rx or count) begin
case(curr)
IDLE: next = (uart_rx ==0)? READ:IDLE;
// negedge of UART_RX signify the receiving.
READ: next = (count == 9)? ACK: READ; // to the ACK if receive complete
ACK: next = IDLE;
endcase
end
always@ (posedge clock_50M) begin
case(curr)
IDLE: begin
count <= 0 ;
tx_done <= 0 ;
end
READ: begin
rx_data[count] <= uart_rx; //save the received values.
count <= count +1;
end
ACK: begin
tx_done <= ((^rx_data[8:0]) == 0); //check for even parity.
leds <= rx_data[7:0];
end
endcase
end
endmodule
Monday, December 3, 2012
DateNetwork review chapter 4.
chapter 4, multiaccess communication.
//--------------------------------------------------
4.1 introduction.
different types of networks.
//--------------------------------------------------
4.2 slotted multiaccess and the aloha system.
Idealized slotted multiaccess model assumptions:
1. slotted system
2. Poisson arrival
3. collision or perfect reception.
4. 0, 1, e immediate feedback.
5. retransmission of collisions.
6a. no buffering, lower bound for delay, no queuing time.
6b. infinite nodes. gives upper bound for delay, because packets were in the same queue can interfere with each other, causing collision.
Slotted aloha with 6a assumption.
m nodes, n backlogged,
$q_a$ arrival transmission probability for each unbacklogged node.
$q_r$ retransmission probability for each backlogged node.
using drift method:
$$
D_n = (m-n) q_a - P_{success} \\
P_{success} \approx G(n) e^{G(n)} \\
G(n) = (m-n) q_a + n q_r
$$
$$
D_n = (m-n) q_a - P_{success} \\
P_{success} \approx G(n) e^{G(n)} \\
G(n) = (m-n) q_a + n q_r
$$
using the approximation $(1-x)^y \approx e^{-xy}$ when x is small.
G(n) is the attempted transmission in one slot, when there is n backlogged nodes.
The only case of interest is $q_r > q_a$. When $q_r$ is small enough for stability, it can be shown that the delay exceeds TDM.
assume the attempted transmissions in one slot is Poisson(G(n)),
The optimal throughput is obtained at $G(n) = 1 \rightarrow P_{success} = 1/e$, $P_{idle} = P(Poisson(G(n)) = 0) = e^{-G(n) } = 1/e$,
therefore $P(collision ) = 1- 2/e$
instead of 6a, for 6b, $G(n) = \lambda + n q_r$, the arrive straight line becomes horizontal $\lambda$
meaning:
$$
D_n = \lambda - P_{success}
$$
the undesirable stable point disappeared, but once n passes the unstable equilibrium, n tends to increase without bound, thus the throughput becomes 0.
Define statbility:
infinite node(6b), the system is stable for a given arrival rate if the expected delay is finite.
aloha is unstable.
G(n) is the attempted transmission in one slot, when there is n backlogged nodes.
The only case of interest is $q_r > q_a$. When $q_r$ is small enough for stability, it can be shown that the delay exceeds TDM.
assume the attempted transmissions in one slot is Poisson(G(n)),
The optimal throughput is obtained at $G(n) = 1 \rightarrow P_{success} = 1/e$, $P_{idle} = P(Poisson(G(n)) = 0) = e^{-G(n) } = 1/e$,
therefore $P(collision ) = 1- 2/e$
instead of 6a, for 6b, $G(n) = \lambda + n q_r$, the arrive straight line becomes horizontal $\lambda$
meaning:
$$
D_n = \lambda - P_{success}
$$
the undesirable stable point disappeared, but once n passes the unstable equilibrium, n tends to increase without bound, thus the throughput becomes 0.
Define statbility:
infinite node(6b), the system is stable for a given arrival rate if the expected delay is finite.
aloha is unstable.
//--------------------------------------------------
4.3 splitting algorithm
resolve the collision before move on, fully exploit the feedback information.
example:
2 node collision, CRP = E[Geo(1/2)] + 1 = 3.
two improvement:
1. automatically split after (e,0,), avoid a w.p.1 collision.
2. discard the R half after (e,e,).
Proof: after the first e, split to $l,r$.
$$
P(r | l>1, l+r >1) = P(r | l>1) = P(r)
$$
which is the same as the untested.
FCFS splitting algorithm.
resolve the collision before move on, fully exploit the feedback information.
example:
2 node collision, CRP = E[Geo(1/2)] + 1 = 3.
two improvement:
1. automatically split after (e,0,), avoid a w.p.1 collision.
2. discard the R half after (e,e,).
Proof: after the first e, split to $l,r$.
$$
P(r | l>1, l+r >1) = P(r | l>1) = P(r)
$$
which is the same as the untested.
FCFS splitting algorithm.
//--------------------------------------------------end
DateNetwork Review, chapter 3.
Chapter3: Delay model:
//-------------------------------------------------------------------------
3.1 introduction
multiplexing: TDM, FDM, statistical multiplexing.
//-------------------------------------------------------------------------
3.2 queuing models - little's theorem
Very general, very important
\[
N = \lambda T
\]
N: average/typical number of customers in the system
T: average delay in the system
$\lambda$: arrival rate.
example1:
P{a server is busy} = $\lambda$ * {average service time}
//-------------------------------------------------------------------------
3.3 MM1
TOOL: Markov chain.
main results:
\[
\rho = \frac{\lambda}{\mu} \\
p_0 = 1 - \rho \\
p_n = \rho^n (1-\rho) \\
N = \frac{\rho}{1-\rho} \\
T = \frac{N}{T} \\
W = T - \frac{1}{\mu} \\
N_Q = N - \rho = \lambda W
\]
An every interesting question to ask is:
"is the queue typical seen by an arrival?".
it is possible to be non-typical, for example, deterministic arrival 1/min, service time 0.5 min,
average system N = 0.5
however, the customer in system seen by an arrival is always 0.
conclusion:
$a_n$ : occupancy distribution upon arrival
$p_n$ : steady state occupancy distribution
$d_n$ : occupancy distribution upon departure.
if arrival process is poisson: $a_n = p_n$.
if markov process is a birth death process: $d_n = a_n$.
//-------------------------------------------------------------------------
3.4 MMm, MMinfty, MMmm
MMm
Markov chain solve for steady state distribution, $p_n$.
define queueing probability:
$P_{queueing} = \sum_{n = m}^{\infty} p_n $
known as Erlang C formula, honoring Denmark's A.K. Erlang.
\[
\rho = \frac{\lambda}{m \mu} \\
N_Q = P_Q \frac{\rho}{1-\rho} \\
W = N_Q / \lambda \\
T = W + \frac{1}{\mu} \\
N = \lambda T \\
\]
note the connection with MM1 here.
explanation: for those who come and join the queue, the system works like $m\mu$ superserver. Write down the MarkovChain for the number of customers waiting in the queue, then it is same as MM1 system.
$M/M/\infty$
This case is very interesting, because:
\[
p_n = (\frac{\lambda}{\mu})^n \frac{e^{-\frac{\lambda}{\mu}}}{n!} \Rightarrow Poisson(\frac{\lambda}{\mu})
\]
What is system delay? No queuing time !!!! W = 0
\[
T = \frac{1}{\mu} \\
N = \frac{\lambda}{\mu} \\
N_Q = 0 \\
W = 0
\]
Intuitively.
M/M/m/m Loss system
again, our tool is markov chain, solve for $p_n$.
actually, there is an easier way. This is a truncated $MM\infty$ case, for those who are accepted, the system indeed has $\infty$ servers. Everything stays the same except for a normalization constant.
and note the common term $e^{-\frac{\lambda}{\mu}}$ cancels.
\[
p_0 = [\sum_{n = 0}^{m} (\frac{\lambda}{\mu})^n \frac{1}{n!}]^{-1}
p_n = p_0 (\frac{\lambda}{\mu})^n \frac{1}{n!}
\]
The most important quantity is the blocking probability (Erlang B formua): $p_m$.
with such probability, any new arrival seen m customer already in system, and it will be rejected.
//-------------------------------------------------------------------------
3.5 MG1
Most important formula: Pollaczek - Khinchin formula. PK formula.
\[
\bar{X} = \textrm{average service time} \\
\bar{X^2} = \textrm{second moment of average service time} \\
W = \frac{\lambda \bar{X^2}}{2(1-\rho)}
\]
other quantities can be found using Little's law.
example1:
MM1
\[
\bar{X} = \frac{1}{\mu}
\Rightarrow
E[X^2] = \frac{2}{\mu ^2}
W = \frac{\rho}{\mu-\lambda}
\]
MD1
\[
E[X^2] = E[X]^2 = \frac{1}{\mu ^2}
\Rightarrow
W = \frac{\rho}{2(\mu - \lambda)}
\]
we note MD1 has only half the queuing delay than the MM1.
FOLK's law: the more random, the more delay.
Proof of PK formula by the author of the book.
how long will a new arrival has to wait in queue?
$$W = R + \frac{1}{\mu} N_Q$$
R: mean residual time.
$N_Q$: number of customer in queue seen by arrival.
using little law: $N_Q = \lambda * W$
\[
W = \frac{R}{1-\rho}
\]
What is R?
in the interval [0,t], $M(t)$ is the number of service completed.
$$
\begin{split}
\frac{1}{t} \int_{0}^{t} r(\tau) d\tau &= \frac{1}{t} \sum_{i = 1}^{M(t)} \frac{x_i ^2}{2}\\
&= \frac{M(t)}{t} \sum_{i = 1}^{M(t)} \frac{x_i ^2}{2 M(t)} \\
R &= \lambda \frac{E[X^2]}{2}
\end{split}
$$
by letting $t\rightarrow \infty$
MG1 with vacation.
At the end of busy period(with probability $1-\rho$), a server that goes to vacation from time to time, with
$E[V]$: average vacation time.
$E[V^2]$: second moment of average vacation time.
We note that service time and vacation time are almost indistinguishable.
Treat R as "residual service time or vacation time."
The derivation is similar to the proof of PK formula:
$$
\begin{split}
R &= \lim_{t\rightarrow \infty} {\frac{M(t)}{t} \sum_{i = 1}^{M(t)}\frac{X_i ^2}{2M(t)}+ \frac{L(t)}{t} \sum_{i = 1}^{L(t)}\frac{V_i ^2}{2L(t)}} \\
& = \frac{\lambda E[X^2]}{2} + \frac{(1-\rho)E[V^2]}{2E[V]} \\
\frac{L(t)}{t} & \rightarrow \frac{1-\rho}{E[V]}
\end{split}
$$
where $L(t)$ is the number of vacation completed during [0, t].
Basically, the vacations increase $p_0$, however, the system can still be viewed as two subsystems:
1. when the system is working, this gives the first part of the R.
2. w.p. $1-\rho$, the system goes to vacation, leading to the second part of the R.
finally:
$$
W = \frac{\lambda E[X^2]}{2(1-\rho)} + \frac{E[V^2]}{2E[V]}
$$
MG1 with reservation.
let consider only a single user, for the i th packet:
1. R: residual till the end of the current transmission, which could either be really transmission or reservation making.
2. N*E[X]: transmission of the before-coming packets.
3. V: (denoted same as vacation) it must wait a full reservation slot, in which its reservation is made.
The system is designed s.t. before its transmission, there bound to be a reservation slot.
again
$$
\begin{split}
V &\leftarrow E[V] \\
R &\leftarrow \frac{\lambda E[X^2]}{2} + \frac{E[V^2]}{2E[V]} (1-\rho) \\
W &= \frac{R+V}{1-\rho} = \frac{\lambda E[X^2]}{2(1-\rho)} + \frac{E[V^2]}{2E[V]} + \frac{E[V]}{1-\rho}
\end{split}
$$
This is fully gated system, meaning ony those packets that arrived prior to the user's preceding reservation interval are transmitted.
therefore every packet has to experience a full reservation slot.
Exhaustive system: all available packets of a user are transmitted during the corresponding data interval.
partially gated system: transmit those packets arrived up to the beginning of the data interval.
Note the exhaustive system is equivalent to the vacation system, only those who arrive see vacation/reservation have to wait.
Priority queuing MG1
non-preemptive: high class CANNOT interrupt low class at service.
preemptive: high class interrupt low class at service, no resumption for the low class. 臭流氓!
Assuming class 1 has the highest priority, class n has the lowest.
non-preemptive is easier:
$\mu_i $ $\lambda_i $ are different.
during the waiting of class2, those later-comer class 1 will jump the queue!
$$
\begin{split}
W_1 &= R + \frac{N_Q ^1}{\mu_1} \\
N_Q^1 &= \lambda_1 W_1 \\
W_1 &= \frac{R}{1-\rho_1} \\
\textrm{"class 1 jump the queue while class 2 waiting"} \\
W_2 &= R + \frac{N_Q ^1}{\mu_1} + \frac{N_Q ^2}{\mu_2} + \frac{\lambda_1 W_2}{\mu_1} \\
W_2 &= \frac{R}{(1-\rho_1)(1- \rho_1 - \rho_2)} \\
\textrm{"finally"} \\
W_k &= \frac{R}{(1-\rho_1 - \ldots - \rho_{k-1})(1-\rho_1 - \ldots - \rho_{k})} \\
\text{"R like a weighted sum"} \\
R &= \frac{1}{2} \sum_{i=1}^{n} \lambda_i E[X_i ^2 ]
\end{split}
$$
The calculation involves all class 1 - n, because it is a non-preemptive system.
preemptive system:
The arrival sees the system as a MG1, ignoring the class (k+1) to n.
$$
\begin{split}
W_k &= \frac{R_k }{1-\rho_1 - \ldots - \rho_k } \\
R_k &= \frac{\sum_{i = 1}^{k} \lambda_i E[X_i ^2]}{2} \\
\end{split}
$$
an explanation for this.
If we only consider the first k class, the capacity assigned to class k is no longer $\rho _k$, but a normalized one:
$$
\frac{\rho_k}{\rho_1 + \ldots + \rho_k}
$$
therefore the service time becomes:
$$
\mu_k \Rightarrow \mu_k \frac{\rho_k}{\rho_1 + \ldots + \rho_k}
$$
which is a improvement, because the denominator is less than 1.
finally.
$$
W_k = R_k + N_Q ^k \frac{\rho_1 + \ldots + \rho_k}{\rho_k \mu_k} \\
= R_k + \lambda_k W_k \frac{\rho_1 + \ldots + \rho_k}{\rho_k \mu_k} \\
= R_k + (\rho_1 + \ldots + \rho_k)W_k
$$
This leads to the same result.
//-------------------------------------------------------------------------
3.6 networks of transmission lines.
//-------------------------------------------------------------------------
3.7 time reversibility - Burke's theorem
backward transition probability:
$$
P_{ij}^* = P{(X_m = j | X_{m+1} = i)} = \frac{p_j P_{ji}}{p_i}
$$
definition:
The markov chain is time reversible if $P_{ij}^* = P_{ij}$, forward and backward transition happens with equal probability.
Chain is time reversible if and only if: $p_i P_{ij} = p_j P_{ji}$,(local balance equation) which is true for birth death process, all M/M/*.
Burke's theorem:
consider M/M/* system, with arrival rate $\lambda$, suppose system starts from steady state, then:
1. the departure rate is Poisson with $\lambda$.
2. at each time t, N in the system is independent of the sequence of departure times prior to t.
Proof: Since the chain is TR.
1. arrival and departure are indistinguishable.
(which also proves for birth death process, $d_n = a_n $)
2. at time t, N is is independent of the arrival sequence after t.
example: two MM1 in tandem.
the first queue is MM1 by nature.
the departure process of queue 1 is independent of the service time of queue2, therefore queue2 is also MM1. (the queue2 is not a MM1, it just happens behave like a MM1)
by part b of Burke's, at time t, N1 in queue1 is independent of prior to t departure, also of the N2 of queue2.
$$
P[N1 = n, N2 = m] = P[N1 = n] P[N2 = m]
$$
//-------------------------------------------------------------------------
3.8 Networks of queues - Jackson's theorem.
solve linear system:
$$
\lambda_j = r_j + \sum_{i = 1}^{K}\lambda_i P_{ij}
$$
then $\rho_j = \frac{\lambda_j }{\mu_j}$
assuming that $\rho _j <1$, for all j, then
$$
P(n) = \prod _{j = 1}^{K} {\rho_j ^n(1-\rho_j)}
$$
as if they were all independent MM1.
closed Jackson's theorem
first, for state independent system:
solve the linear system:
$$
\lambda_j = \sum_{i = 1}^{K}\lambda_i P_{ij}
$$
define
$$
\rho_j= \frac{\lambda_j }{\mu_j}
$$
j = 1, ..., K
$$
G(M) = \sum_{n1+n2+\ldots+n_K = M} {\rho_1 ^{n_1} \rho_2 ^{n_2} \ldots \rho_K ^{n_K}}
$$
Closed Jackson network:
under the preceding assumption
$$
P(n_1, n_2, \ldots, n_K) = \frac{\rho_1 ^{n_1} \rho_2 ^{n_2} \ldots \rho_K ^{n_K}}{G(M)}
$$
where $G(M)$ can be viewed as a simple normalization constant.
The key is:
1. solve for the internal arrival rates.
2. treat each queue like independent MM1.
//-------------------------------------------------------------------------end
//-------------------------------------------------------------------------
3.1 introduction
multiplexing: TDM, FDM, statistical multiplexing.
//-------------------------------------------------------------------------
3.2 queuing models - little's theorem
Very general, very important
\[
N = \lambda T
\]
N: average/typical number of customers in the system
T: average delay in the system
$\lambda$: arrival rate.
example1:
P{a server is busy} = $\lambda$ * {average service time}
//-------------------------------------------------------------------------
3.3 MM1
TOOL: Markov chain.
main results:
\[
\rho = \frac{\lambda}{\mu} \\
p_0 = 1 - \rho \\
p_n = \rho^n (1-\rho) \\
N = \frac{\rho}{1-\rho} \\
T = \frac{N}{T} \\
W = T - \frac{1}{\mu} \\
N_Q = N - \rho = \lambda W
\]
An every interesting question to ask is:
"is the queue typical seen by an arrival?".
it is possible to be non-typical, for example, deterministic arrival 1/min, service time 0.5 min,
average system N = 0.5
however, the customer in system seen by an arrival is always 0.
conclusion:
$a_n$ : occupancy distribution upon arrival
$p_n$ : steady state occupancy distribution
$d_n$ : occupancy distribution upon departure.
if arrival process is poisson: $a_n = p_n$.
if markov process is a birth death process: $d_n = a_n$.
//-------------------------------------------------------------------------
3.4 MMm, MMinfty, MMmm
MMm
Markov chain solve for steady state distribution, $p_n$.
define queueing probability:
$P_{queueing} = \sum_{n = m}^{\infty} p_n $
known as Erlang C formula, honoring Denmark's A.K. Erlang.
\[
\rho = \frac{\lambda}{m \mu} \\
N_Q = P_Q \frac{\rho}{1-\rho} \\
W = N_Q / \lambda \\
T = W + \frac{1}{\mu} \\
N = \lambda T \\
\]
note the connection with MM1 here.
explanation: for those who come and join the queue, the system works like $m\mu$ superserver. Write down the MarkovChain for the number of customers waiting in the queue, then it is same as MM1 system.
$M/M/\infty$
This case is very interesting, because:
\[
p_n = (\frac{\lambda}{\mu})^n \frac{e^{-\frac{\lambda}{\mu}}}{n!} \Rightarrow Poisson(\frac{\lambda}{\mu})
\]
What is system delay? No queuing time !!!! W = 0
\[
T = \frac{1}{\mu} \\
N = \frac{\lambda}{\mu} \\
N_Q = 0 \\
W = 0
\]
Intuitively.
M/M/m/m Loss system
again, our tool is markov chain, solve for $p_n$.
actually, there is an easier way. This is a truncated $MM\infty$ case, for those who are accepted, the system indeed has $\infty$ servers. Everything stays the same except for a normalization constant.
and note the common term $e^{-\frac{\lambda}{\mu}}$ cancels.
\[
p_0 = [\sum_{n = 0}^{m} (\frac{\lambda}{\mu})^n \frac{1}{n!}]^{-1}
p_n = p_0 (\frac{\lambda}{\mu})^n \frac{1}{n!}
\]
The most important quantity is the blocking probability (Erlang B formua): $p_m$.
with such probability, any new arrival seen m customer already in system, and it will be rejected.
//-------------------------------------------------------------------------
3.5 MG1
Most important formula: Pollaczek - Khinchin formula. PK formula.
\[
\bar{X} = \textrm{average service time} \\
\bar{X^2} = \textrm{second moment of average service time} \\
W = \frac{\lambda \bar{X^2}}{2(1-\rho)}
\]
other quantities can be found using Little's law.
example1:
MM1
\[
\bar{X} = \frac{1}{\mu}
\Rightarrow
E[X^2] = \frac{2}{\mu ^2}
W = \frac{\rho}{\mu-\lambda}
\]
MD1
\[
E[X^2] = E[X]^2 = \frac{1}{\mu ^2}
\Rightarrow
W = \frac{\rho}{2(\mu - \lambda)}
\]
we note MD1 has only half the queuing delay than the MM1.
FOLK's law: the more random, the more delay.
Proof of PK formula by the author of the book.
how long will a new arrival has to wait in queue?
$$W = R + \frac{1}{\mu} N_Q$$
R: mean residual time.
$N_Q$: number of customer in queue seen by arrival.
using little law: $N_Q = \lambda * W$
\[
W = \frac{R}{1-\rho}
\]
What is R?
in the interval [0,t], $M(t)$ is the number of service completed.
$$
\begin{split}
\frac{1}{t} \int_{0}^{t} r(\tau) d\tau &= \frac{1}{t} \sum_{i = 1}^{M(t)} \frac{x_i ^2}{2}\\
&= \frac{M(t)}{t} \sum_{i = 1}^{M(t)} \frac{x_i ^2}{2 M(t)} \\
R &= \lambda \frac{E[X^2]}{2}
\end{split}
$$
by letting $t\rightarrow \infty$
MG1 with vacation.
At the end of busy period(with probability $1-\rho$), a server that goes to vacation from time to time, with
$E[V]$: average vacation time.
$E[V^2]$: second moment of average vacation time.
We note that service time and vacation time are almost indistinguishable.
Treat R as "residual service time or vacation time."
The derivation is similar to the proof of PK formula:
$$
\begin{split}
R &= \lim_{t\rightarrow \infty} {\frac{M(t)}{t} \sum_{i = 1}^{M(t)}\frac{X_i ^2}{2M(t)}+ \frac{L(t)}{t} \sum_{i = 1}^{L(t)}\frac{V_i ^2}{2L(t)}} \\
& = \frac{\lambda E[X^2]}{2} + \frac{(1-\rho)E[V^2]}{2E[V]} \\
\frac{L(t)}{t} & \rightarrow \frac{1-\rho}{E[V]}
\end{split}
$$
where $L(t)$ is the number of vacation completed during [0, t].
Basically, the vacations increase $p_0$, however, the system can still be viewed as two subsystems:
1. when the system is working, this gives the first part of the R.
2. w.p. $1-\rho$, the system goes to vacation, leading to the second part of the R.
finally:
$$
W = \frac{\lambda E[X^2]}{2(1-\rho)} + \frac{E[V^2]}{2E[V]}
$$
MG1 with reservation.
let consider only a single user, for the i th packet:
1. R: residual till the end of the current transmission, which could either be really transmission or reservation making.
2. N*E[X]: transmission of the before-coming packets.
3. V: (denoted same as vacation) it must wait a full reservation slot, in which its reservation is made.
The system is designed s.t. before its transmission, there bound to be a reservation slot.
again
$$
\begin{split}
V &\leftarrow E[V] \\
R &\leftarrow \frac{\lambda E[X^2]}{2} + \frac{E[V^2]}{2E[V]} (1-\rho) \\
W &= \frac{R+V}{1-\rho} = \frac{\lambda E[X^2]}{2(1-\rho)} + \frac{E[V^2]}{2E[V]} + \frac{E[V]}{1-\rho}
\end{split}
$$
This is fully gated system, meaning ony those packets that arrived prior to the user's preceding reservation interval are transmitted.
therefore every packet has to experience a full reservation slot.
Exhaustive system: all available packets of a user are transmitted during the corresponding data interval.
partially gated system: transmit those packets arrived up to the beginning of the data interval.
Note the exhaustive system is equivalent to the vacation system, only those who arrive see vacation/reservation have to wait.
Priority queuing MG1
non-preemptive: high class CANNOT interrupt low class at service.
preemptive: high class interrupt low class at service, no resumption for the low class. 臭流氓!
Assuming class 1 has the highest priority, class n has the lowest.
non-preemptive is easier:
$\mu_i $ $\lambda_i $ are different.
during the waiting of class2, those later-comer class 1 will jump the queue!
$$
\begin{split}
W_1 &= R + \frac{N_Q ^1}{\mu_1} \\
N_Q^1 &= \lambda_1 W_1 \\
W_1 &= \frac{R}{1-\rho_1} \\
\textrm{"class 1 jump the queue while class 2 waiting"} \\
W_2 &= R + \frac{N_Q ^1}{\mu_1} + \frac{N_Q ^2}{\mu_2} + \frac{\lambda_1 W_2}{\mu_1} \\
W_2 &= \frac{R}{(1-\rho_1)(1- \rho_1 - \rho_2)} \\
\textrm{"finally"} \\
W_k &= \frac{R}{(1-\rho_1 - \ldots - \rho_{k-1})(1-\rho_1 - \ldots - \rho_{k})} \\
\text{"R like a weighted sum"} \\
R &= \frac{1}{2} \sum_{i=1}^{n} \lambda_i E[X_i ^2 ]
\end{split}
$$
The calculation involves all class 1 - n, because it is a non-preemptive system.
preemptive system:
The arrival sees the system as a MG1, ignoring the class (k+1) to n.
$$
\begin{split}
W_k &= \frac{R_k }{1-\rho_1 - \ldots - \rho_k } \\
R_k &= \frac{\sum_{i = 1}^{k} \lambda_i E[X_i ^2]}{2} \\
\end{split}
$$
an explanation for this.
If we only consider the first k class, the capacity assigned to class k is no longer $\rho _k$, but a normalized one:
$$
\frac{\rho_k}{\rho_1 + \ldots + \rho_k}
$$
therefore the service time becomes:
$$
\mu_k \Rightarrow \mu_k \frac{\rho_k}{\rho_1 + \ldots + \rho_k}
$$
which is a improvement, because the denominator is less than 1.
finally.
$$
W_k = R_k + N_Q ^k \frac{\rho_1 + \ldots + \rho_k}{\rho_k \mu_k} \\
= R_k + \lambda_k W_k \frac{\rho_1 + \ldots + \rho_k}{\rho_k \mu_k} \\
= R_k + (\rho_1 + \ldots + \rho_k)W_k
$$
This leads to the same result.
//-------------------------------------------------------------------------
3.6 networks of transmission lines.
//-------------------------------------------------------------------------
3.7 time reversibility - Burke's theorem
backward transition probability:
$$
P_{ij}^* = P{(X_m = j | X_{m+1} = i)} = \frac{p_j P_{ji}}{p_i}
$$
definition:
The markov chain is time reversible if $P_{ij}^* = P_{ij}$, forward and backward transition happens with equal probability.
Chain is time reversible if and only if: $p_i P_{ij} = p_j P_{ji}$,(local balance equation) which is true for birth death process, all M/M/*.
Burke's theorem:
consider M/M/* system, with arrival rate $\lambda$, suppose system starts from steady state, then:
1. the departure rate is Poisson with $\lambda$.
2. at each time t, N in the system is independent of the sequence of departure times prior to t.
Proof: Since the chain is TR.
1. arrival and departure are indistinguishable.
(which also proves for birth death process, $d_n = a_n $)
2. at time t, N is is independent of the arrival sequence after t.
example: two MM1 in tandem.
the first queue is MM1 by nature.
the departure process of queue 1 is independent of the service time of queue2, therefore queue2 is also MM1. (the queue2 is not a MM1, it just happens behave like a MM1)
by part b of Burke's, at time t, N1 in queue1 is independent of prior to t departure, also of the N2 of queue2.
$$
P[N1 = n, N2 = m] = P[N1 = n] P[N2 = m]
$$
//-------------------------------------------------------------------------
3.8 Networks of queues - Jackson's theorem.
solve linear system:
$$
\lambda_j = r_j + \sum_{i = 1}^{K}\lambda_i P_{ij}
$$
then $\rho_j = \frac{\lambda_j }{\mu_j}$
assuming that $\rho _j <1$, for all j, then
$$
P(n) = \prod _{j = 1}^{K} {\rho_j ^n(1-\rho_j)}
$$
as if they were all independent MM1.
closed Jackson's theorem
first, for state independent system:
solve the linear system:
$$
\lambda_j = \sum_{i = 1}^{K}\lambda_i P_{ij}
$$
define
$$
\rho_j= \frac{\lambda_j }{\mu_j}
$$
j = 1, ..., K
$$
G(M) = \sum_{n1+n2+\ldots+n_K = M} {\rho_1 ^{n_1} \rho_2 ^{n_2} \ldots \rho_K ^{n_K}}
$$
Closed Jackson network:
under the preceding assumption
$$
P(n_1, n_2, \ldots, n_K) = \frac{\rho_1 ^{n_1} \rho_2 ^{n_2} \ldots \rho_K ^{n_K}}{G(M)}
$$
where $G(M)$ can be viewed as a simple normalization constant.
The key is:
1. solve for the internal arrival rates.
2. treat each queue like independent MM1.
//-------------------------------------------------------------------------end
harmonica tabs.
godfather:
5 -6 7 -7 -6 7 -6 -7 -6 -5 6
Speak soft-ly love and hold me warm a-gainst your
5
heart,
5 -6 7 -7 -6 7 -6 -7 -6 -5 5
I feel your words, the ten-der trem-bling mo-ments
-4
start,
-4 -5 -6 -7 -4 -5-6 -6
We're in a world, our ve-ry own,
5 6 -5 -5 5 6 -5 -5 5 -7 7 -6
Sha-ring a love that on-ly few have ev-er known,
-6 -6 6 6 -7 -6 -5 5
Wine col-ored days, warmed by the sun,
5 6 5 -4 -4 -5 -4 5
Deep vel-vet nights, when we are one,
5 -6 7 -7 -6 7 -6 -7 -6 -5 6
Speak soft-ly love, so no one hears us but the
5
sky,
5 -6 7 -7 -6 7 -6 -7 -6 -5 5
The vows of love, we make, will live, un-til we
-4
die,
-4 -5 -6 -7 -5 -6 -7 6
My life is yours and all be-cause,
5 6 -5 -5 5 6 -5 -5 5 -7 7
You came in-to my world with love, so soft-ly,
-6
love.
Godfather 2.
S-L-O-W-L-Y and S-O-F-T-L-Y (with lots of feeling)
8 -8 8 -9 8 8 7
8 -8 8 -9 8 8 -7
8 -8 8 9 8 -8 -9 8
7 -7 7 8 -8 -7
8 -8 8 -9 8 8 7
8 -8 8 -9 8 8 -7
8 -8 8 9 8 -8 -9 8
7 -7 7 8 -8 -7
End with:
6 6 6 6 -6 -7 7
happy birthday to you
6 6 -6 6 7 -7
6 6 -6 6 -8 7
6 6 9 8 7 -7 -6
-9 -9 8 7 -8 7
5 -6 7 -7 -6 7 -6 -7 -6 -5 6
Speak soft-ly love and hold me warm a-gainst your
5
heart,
5 -6 7 -7 -6 7 -6 -7 -6 -5 5
I feel your words, the ten-der trem-bling mo-ments
-4
start,
-4 -5 -6 -7 -4 -5-6 -6
We're in a world, our ve-ry own,
5 6 -5 -5 5 6 -5 -5 5 -7 7 -6
Sha-ring a love that on-ly few have ev-er known,
-6 -6 6 6 -7 -6 -5 5
Wine col-ored days, warmed by the sun,
5 6 5 -4 -4 -5 -4 5
Deep vel-vet nights, when we are one,
5 -6 7 -7 -6 7 -6 -7 -6 -5 6
Speak soft-ly love, so no one hears us but the
5
sky,
5 -6 7 -7 -6 7 -6 -7 -6 -5 5
The vows of love, we make, will live, un-til we
-4
die,
-4 -5 -6 -7 -5 -6 -7 6
My life is yours and all be-cause,
5 6 -5 -5 5 6 -5 -5 5 -7 7
You came in-to my world with love, so soft-ly,
-6
love.
Godfather 2.
S-L-O-W-L-Y and S-O-F-T-L-Y (with lots of feeling)
8 -8 8 -9 8 8 7
8 -8 8 -9 8 8 -7
8 -8 8 9 8 -8 -9 8
7 -7 7 8 -8 -7
8 -8 8 -9 8 8 7
8 -8 8 -9 8 8 -7
8 -8 8 9 8 -8 -9 8
7 -7 7 8 -8 -7
End with:
6 6 6 6 -6 -7 7
happy birthday to you
6 6 -6 6 7 -7
6 6 -6 6 -8 7
6 6 9 8 7 -7 -6
-9 -9 8 7 -8 7
Sunday, December 2, 2012
mac screenshot 截图
总是忘记 每次都要google
在这里写一下
Command-Shift-4, then select an area: Take a screenshot of an area and save it as a file on the desktop
Command-Control-Shift-4, then select an area: Take a screenshot of an area and save it to the clipboard
在这里写一下
Command-Shift-4, then select an area: Take a screenshot of an area and save it as a file on the desktop
Command-Control-Shift-4, then select an area: Take a screenshot of an area and save it to the clipboard
关于纸张的大小. size
常用的纸张有A4 A3..... 但是他们的大小 和 长宽的比例是多少呢?
一张A4 的对折就能变成一张A3的纸, 而且长宽的比例不变
这要求 如果A4 纸的长y 宽x
$$
y = \alpha *x \\
x = \alpha * y/2\\
\Rightarrow
\alpha = \sqrt{2}
$$
然后定义A0纸张的大小为$1 m^2 $ 比例为$\sqrt{2}$ 这样每次对折都可以得到 A1, A2,A3,A4,A5 ....
而造纸厂只需要造 和 储存 一种型号的纸张A0,
真聪明!
y = \alpha *x \\
x = \alpha * y/2\\
\Rightarrow
\alpha = \sqrt{2}
$$
然后定义A0纸张的大小为$1 m^2 $ 比例为$\sqrt{2}$ 这样每次对折都可以得到 A1, A2,A3,A4,A5 ....
而造纸厂只需要造 和 储存 一种型号的纸张A0,
真聪明!
如何点pho
pho -- pronounced as fuh
/////--------------------在天书菜单上能看到如下的肉类
tai - round eye steak 一般是生的 比较薄片的肉, 在汤里一汤就熟了. 如果是外带 到家已经是熟的了 就变成了 chin
chin - well done brisket 同tai 只不过是熟的
nam - well done flank 这个是熟的 有点像是干切牛肉的东西.
gau - fatty brisket 这个是我的最爱 , 是半肥半瘦的片状牛肉
gan - tendon 牛筋 也很好吃
sach - tripe 大爱牛百叶.
bo vien - meat ball 肉圆
-------------------------简单的英文
brisket - 牛胸肉
flank - 侧肉, 腰窝肉
tendon - 牛筋
tripe - 牛百叶,
/////--------------------在天书菜单上能看到如下的肉类
tai - round eye steak 一般是生的 比较薄片的肉, 在汤里一汤就熟了. 如果是外带 到家已经是熟的了 就变成了 chin
chin - well done brisket 同tai 只不过是熟的
nam - well done flank 这个是熟的 有点像是干切牛肉的东西.
gau - fatty brisket 这个是我的最爱 , 是半肥半瘦的片状牛肉
gan - tendon 牛筋 也很好吃
sach - tripe 大爱牛百叶.
bo vien - meat ball 肉圆
-------------------------简单的英文
brisket - 牛胸肉
flank - 侧肉, 腰窝肉
tendon - 牛筋
tripe - 牛百叶,
---------------------具体吃法
点好了就等吃了 一般都有小份和 大份的.
先上一份豆芽, basil(九层塔), 青辣椒, 柠檬.
九层塔的叶子摘下来泡汤, 豆芽加入汤中, 柠檬挤出汁水入汤, 那个青辣椒真的很辣....
桌上一般还有一个红色的酱 还有海鲜酱. 随便加. ... 我喜欢挤到盘子上沾着肉吃 不然回影响汤的味道.
------------------记得付钱!
latex on blogger, 支持latex.
首先 建立一个新的post(帖子), 然后转换到html mode. 在最上方加入:
<script type="text/x-mathjax-config"> MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); </script> <script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"> </script>
然后换回compose mode. 然后... 然后就成啦!
来试试
\[P(E) = {n \choose k} p^k (1-p)^{n-k}\]
使用的latex 语法,short guide:
ftp://ftp.ams.org/pub/tex/doc/amsmath/short-math-guide.pdf
OR
http://fluidmind.org/articles/typesetting-equations/ (强烈推荐)
对于已经比较熟悉latex 的同志, 附上 latex cheating sheet.
http://www.stdout.org/~winston/latex/latexsheet.pdf
<script type="text/x-mathjax-config"> MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}}); </script> <script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"> </script>
然后换回compose mode. 然后... 然后就成啦!
来试试
\[P(E) = {n \choose k} p^k (1-p)^{n-k}\]
使用的latex 语法,short guide:
ftp://ftp.ams.org/pub/tex/doc/amsmath/short-math-guide.pdf
OR
http://fluidmind.org/articles/typesetting-equations/ (强烈推荐)
对于已经比较熟悉latex 的同志, 附上 latex cheating sheet.
http://www.stdout.org/~winston/latex/latexsheet.pdf
Saturday, December 1, 2012
关于 指数分布 最小和无记忆
如果有 x1, x2, .... ,xn, n 个 iid（独立同分布） 的指数分布。 expo(mu)
min(x1,...., xn) 也是一个指数分布 expo(n*mu)。 证明很简单：
P(min <y) = 1- P(min > y) = 1- (P(所有都大于 y)) =.....
而且要牢记 exponential 的memoryless（无记忆） 的特性
由此可以导出一些意思的东西。
-------------------------------一道题目
你走进银行 一共有四个柜台，a,b,c,d 在被服务， 他们的服务时间服从指数分布 iid expo(1). i.e. 平均每人花一分钟， 在你后面没有别人进来，
问你是最后一个离开的概率是多少？
1/4！ 多好看！ 因为首先 abcd中有一个人先完成了手续就离开了 这是你上前被服务。 从这个时间点开始， 在柜台的四个人都是 崭新的exponential分布！（memoryless.）（至于这是否符合现实， 就不是我能管的事情了。 ）
四个崭新的同分布， 其中任一个最大的概率是1/4.
问你要等待的时间是多少？
当然是expected time. 首先你要等一个E[min(a,d,c,d)] = 1/4, 因为 min(a,b,c,d) ~ expo(4).
然后就是你的服务时间。
总时间 = 1/4+1 = 5/4
问a是最后一个离开的概率是多少？
用全概率公式做
a 如果是第一个离开的， 那他/她是最后一个离开的概率是~~~~~~~~ 0 （废话）
a 如果不是第一个离开的，with probability 3/4, (w.p.) 这是你进入柜台。 那他是最后一个离开的概率是1/4
所以a 是最后一个离开的概率是 3/4*1/4 = 3/16
这个有一个巧解（不是巧姐！） ，
1. a.b.c,d 其实是不可分辨的 indistinguishable.
2. 包括你在内的五个人中总有一个人 是要最后离开 （再次废话）
所以 排除你是最后一个离开的概率 然后平分：
(1-1/4)/4 = 3/16。
看 有时候废话的力量如此之大！
证明两个独立高斯变量的和差是独立的。
x1, x2, 是iid高斯 (mu, sigma^2)。 那么x1+x2, x1 - x2 也是独立的高斯。
这个题目以前证过， 从他们的概率分布开始 最后能推出和差的pdf。 前几天被别人的一句无心的话点醒了。：
“对于高斯变量， 不相关 等价于 独立”
对啊！
E[(x1+x2)(x1-x2)] = 0. QED.
当然值得注意的一些废话：
1. 独立高斯的和 差 也是高斯。
2. 两个高斯的和 差 的range = (-inft, +inft)
//---------------如果不是 identical distributed 的呢？
独立高斯
x1 ~ N (mu1, sig1^2 )
x2 ~ N (mu2, sig2^2 )
E[(x1+x2)(x1-x2)] = E(x1^2) - E(x2^2) = sig1^2 + mu1^2 - sig2^2 - mu2^2
如果为0 ， 就成了！
这个题目以前证过， 从他们的概率分布开始 最后能推出和差的pdf。 前几天被别人的一句无心的话点醒了。：
“对于高斯变量， 不相关 等价于 独立”
对啊！
E[(x1+x2)(x1-x2)] = 0. QED.
当然值得注意的一些废话：
1. 独立高斯的和 差 也是高斯。
2. 两个高斯的和 差 的range = (-inft, +inft)
//---------------如果不是 identical distributed 的呢？
独立高斯
x1 ~ N (mu1, sig1^2 )
x2 ~ N (mu2, sig2^2 )
E[(x1+x2)(x1-x2)] = E(x1^2) - E(x2^2) = sig1^2 + mu1^2 - sig2^2 - mu2^2
如果为0 ， 就成了！
禅和摩托车修理艺术 读后感
昨天晚上扫完了这本书， 五味杂陈， 说不上来什么感觉。 总是被震撼到了。 赶紧上amazon 买了英文版的 寒假的时候打算好好看看。 如何能应用到生活中来。
几点感想：
1.
这本书值得多看几遍，书中也说的 做事别求快 要做到自己觉得完成了才算完成， 做到自己内心平静了才算好。 而不是做完了就算了。 就好像做题的举一反三一样。一道题有很多值得推敲的地方。多想想 想到自己觉得平静了就可以move on.
2.
给我最最最最大的震撼就是一个人对思考 对真理的追求竟能如此痴狂 到最后疯了， 当然是在常人的意义上是疯了。 想想自己过的真是行尸走肉一般。 思考至疯 而不要娱乐至死。
3.
这本书根本就不是写给大家看的， 至少一开始不是的。也许所有的伟大的作品一开始都只是作者的感情的倾泻。 他自己的自言自语只是为了把自己不完整。 他必须要一个人独自走过那个黑暗的峡谷。 后来他找到了自己心中的真理， 想分享给大家 觉得有这个义务 才会不停的投稿 不停的被拒 不停的投稿 121 次 才有了我昨天晚上的心灵上的震撼。
4.
人类的一些关键性的突破是疯子完成的 体制外的深刻思考促成了体制的改革， 于是想起一本书： 疯狂与文明 马上amazon 定下 等书。
未完 第二遍补全。
概率中的 独立 和 不交合 independent vs. disjoint 事件
学而不思则罔！
ind - 独立
mutually exclusive, disjoint - 不交合， 不相关， 互斥。。。。。
如果两个事件不相关， 就是不能同时发生， 那么他们一定不独立！
disjoint ---> not ind
ind ----> not disjoint. （独立则可同时发生）
所以两个事件之间的关系只有：
1. ind and not disjoint.
2. not ind and disjoint.
具体到概率的应用上
///------------------------------废话 基础知识 。
如果两个事件 A B 独立 。P(AB ) = P(A)P(B).
这个更多的是从bayes 的角度出发： P(A|B) = P(A)
对于任意两个时间 P(A or B ) = P(A) +P(B) +P(A and B), 可以从Venn diagram 有直观的了解（但是非严格证明）
进而， 两个事件disjoint: P(A or B ) = P(A ) + P(B)
/// ---------------------一个例子
考虑跑两个银币。 TT, HH TH, HT.
1. ind and not disjoint.
A = 第一次抛出头 = {HH,HT}
B = 第二次抛出头 = {TH, HH}
共同事件 HH, so they are no disjoint。
2. not ind and disjoint.
这个就多了去了。
A = {HH}
B = {TT}
两事件不能同时发生，不独立。
Tuesday, November 20, 2012
人生的意义：生活的理想就是理想的生活
最近想了很多很多关于人生的意义的事情。
人生没有意义！
为什么要想这个沉重的话题呢。 每一个人都可以去想去思考这个topic， 不需要太多的知识 不需要太多的背景， 不会被几个大头名词：存在主意， experience machine 被吓跑， 只要我努力去想不停的去想 我能穷尽所有别人想过的主意。 但是我还是没有能想到人生的意义是什么。 好像是龙应台在被追问到人生的意义的时候：
“请问人生的意义是什么？ 请诚实作答， 不许说谎！”
“我思考了这个问题很久， 我现在可以很负责任的告诉你， 人生没有意义”
我为什么不马上自杀？
人生的意义这个问题当然是重要的， 如果人生没有意义 我为什么还要活着。 就算我是含着金勺子出生（当然我不是，或者生命就是我最宝贵的礼物？） 人生总是要经历一些苦的。 每一个正常人都会在生命的某一个时刻想要自杀。 就好像肖申克救赎里 red 说的“every man got his weakest point” 。 那么我为什么不赶紧自杀 省的浪费地球的资源？
会有转机么？人类已经思考这个问题几千年了 （也许更久）， 也没有想出个所以然来 。我很喜欢加缪把这个问题提高到了哲学的最高的地位： 我为什么不选择自杀？ 至于唯心还是唯物， 牛顿还是爱因斯坦， 杨过还是张无忌 这个都是在我选择不自杀的之后要烦恼的问题了。
看来在我有生之年是不会有转机了， 看来不会在2012 突然有神降临 给我指明出路 告诉我人生的意义 让我为之奋斗！
还是加缪在自己哲学随记中提到了西西弗斯的神话， 勇敢的对生活说 “是” 就是对人生的荒诞性的奋起反抗， 人生的意义也体现出来了。 说实话， 我听着这句话好半天， 我有种想哭的冲动， 或者是我有种该哭的冲动 ， 隐约好像是正理 但是我其实还是没有看懂。 豆瓣上有人说看到西西弗斯这段的时候嚎啕大哭。 我真为这位仁兄或者仁姐汗颜， 你丫是真懂了么！ 不是说我嫉妒别人境界高能看懂， 只是身边有太多这种例子。
少年不识愁滋味 欲赋新词强作愁 如今尝尽愁 欲说还休 。 （说的太好了！）
扯远了， 总是加缪也没有给我我想要的答案。
好像“为何生” 总是和 “死之后” 联系在一起的。 小的时候常常陷入恐惧之中，每每想到人死之后的感觉， 我觉得应该是和睡着了但不做梦的感觉差不多吧 ， 那种和现实的彻底的隔断让我感到一种莫名的孤独和寒冷 。后来我才知道聪明的人已经发明了宗教。 这正是个好东西， 赋予了人类生命的价值。 给了我一个人生意义的答案。 等等！ 谁给我的？ 还不是人类自己给自己的？ 这就好像是保护自己的一种机制 每每思考为什么不去自杀， 生命还值不值得去过 总是有几个人大叫一声然后就去实践去了。 宗教总是告诉我们 现世的意义在于它决定了你的后世！或者是天堂地狱 或者是轮回涅槃。 宗教特别对自杀的人毫不留情， 其原因也就是因为它是一种保护机制。 stop thinking!!!! 我为什么要停止思考 ，作为一个人类我有特权是思考这个问题（别跟我说子非鱼什么的） 。 也正是因为我是人类我才会折磨自己思考这个没有答案的问题。 宗教不是最终的答案 尽管它很聪明 我很喜欢帕斯卡的务实的逻辑
1。 信上帝 结果有上帝： 天堂 无限开心
2. 不信上帝 结果有上帝： 地狱 无限悲哀
3. 不信上帝 结果没上帝 = 信上帝 结果没上帝 = 不疼不痒
所以人应该信上帝 。
看上去多么美好的逻辑 其实有两个巨大缺陷
1. 如果因为这种逻辑信上帝 那是真信么？
2. 这种理论同样适用于任何神 ， 那么那个宗教才是“正确的”. 事实上大部分宗教的神都有排他性。
季羡林说人生的意义在于承前启后， 也许我的人生没有意义， 但是我不能否定我们的后世的人生没有意义 所以我要繁殖？ 我要活着？ 但是我一点都不关心我死了之后谁还传着我的DNA 我的子孙还会不会被神带去天堂。 我想知道的是 我的意义是什么！ 我想知道我为什么活着！ 我对人类和整个宇宙都有一种悲观的态度 。 且不说当代人活的就好像自己是最后一代一样去虐待地球母亲 。 我觉得人类总是要灭亡的， 人类就好像是在烂泥里打滚的猪一样瞎折腾。 抱着这种信念 人生就更没有意义啦！
我觉得人生的目的就是没有！ 突然我想到了那句广告词， “人生就像旅行 不在乎目的地 而在于沿途的风光”。 多么巧妙的而又深刻的对比！ 旅行也是一种经历 没有目的地 重要的是用心感受沿途的风景。 我甚至觉得人生就是人进入了黑客帝国那种 experience machine (EM) 一样， 在没有进入em之前 有人向我推荐了它 就好像豆瓣上推荐读书一样。 em的说明书上说的这段旅程没有任何意义 而且天上一日 地上十年 所以等我出来的时候 才过了一个多星期。 多好啊。 我就抱着这样的期盼未知的心态进入了em。 选择了标准的配置 出生在了地球上 ， 与此同时其他的60亿人也同时在线 一起在em中。 我甚至觉得em之外的生活是一种衣食无忧 科技高度发达的社会 能源无穷无尽 所有定理都证完了 所有方程都解决了， 人们活的太无聊了 才会发明出这种em这个机器解闷的。 但是问题又来了！ em中的生活没有意义 em之外的生活有没有意义对我现在的状态毫无关系！ 唯一的好处可能是对生活的豁达 如果我相信人死了之后就从em中醒来 那我就在不怕死了 我间接的达到了一种佛家的一切皆空的金刚经的境界。
但是我还是没有想出我为什么不马上自杀。 绝不是习惯了的原因， 我习惯活着了。 所以我就要活着？ 当痛苦累积到一定程度的时候 我绝对会打破这个习惯！ （这里引用加缪的思想）。
我想啊想啊想啊 就是没有结果， 我希望我能想出一个积极的人生意义 让我为之奋斗。。看来是不太可能了 。
尼采让我成为超人。 但是我这短短的人生那来的时间去那样折磨自己啊。
稻盛和夫在《活法》一书中让我百分百的抓紧一切时间努力 这样在死的时候就能成为一个比呱呱坠地的时候更好的灵魂。 如果我死了就好像长眠一样 灵魂肉体都不复存在 那我就算变成了一个更好的灵魂又怎么样呢！
我就是想不出一个答案！ 也许这就是人的烦恼吧 因为是人才会想这个问题。 但是想不出这个问题的答案 活着还能自称是人么？ 我也怕想出一个完全消极的意义， 没有意义总比让我天天扔雪球的意义来的好些。。。 或者说如果天天扔雪球就是我人生的终极意义那我也会过的很开心？
今天晚上看 肖申克的救赎 突然想到 andy 为什么要越狱。 在监狱里终老一生 和在太平洋小岛上终老一生 在人生的意义上有什么不同么。 我不关心对别人的意义是否不同 我不关心andy是否也顺带救赎了red 唤醒了其他的凡人。 我关心的只是 如果我是andy 我会越狱么? 我当然会 我傻么 我才不要为别人背黑锅。 我想andy之前有条件而没有越狱是因为他认为他对自己妻子的死有一定责任 因为他不善于表达 。 后来red的开导 加上2个月的in the hole 禁闭 他才摆脱了思想上的包袱 去追求自己想要的人生吧。在监狱中过一生和在小岛上过一生 最大的不同在于自由 在于快乐 在于自己选择了自己想要的人生 而不是过着别人强加给我的生活。 他隐忍了20年 挖了20年不曾放弃自己 不曾放弃希望 爬过500yards的粪管道 这都是概括了一切艰难困苦
但是在andy开车 迎着风 去自己心中的小岛的时候 他一定是极度快乐的 就那一刻真实的快乐就值得！
对啊 人生在世最重要的就是快乐啊 这么简单的道理 ！ 诺贝尔奖得主问自己儿子为什么活着 他小儿子很干净的回答道“好玩 ” 。 就是快乐啊 ！ 人生在世 谁没有想过 如果我能怎么怎么 那我一定是世界上最幸福的人。 那就勇敢的去做啊！ 成为自己想成为的人 过自己想过的生活 让自己充实快乐 这就是旅行的意义 我认为也就是人生的意义 。 也许有人说我低俗 目光短浅 然后想用佛法一切皆空教化我。 对不起 我目前的境界就是这样的 我还会去想 但是目前也就告一段落了
我想出来的人生意义就是去成为自己心中想成为的那个人 过上自己心中期望的生活 让自己真正的快乐 生活的理想就是理想的生活。
note： 这篇东西本来就是写给自己看的 如果您有任何想法 请告诉我， 谁知道您的一句无心之言 会不会给我带来无尽的启发？ 对您来说也是无尽的福报了。
我没有回头去整理 过一阵子我会回来做这件事情。
如果您有耐心读完 那么愿您有美好的一生
如果您没有耐心读完 那么您也没有损失什么 毕竟仁见仁 智见智 人生的意义这种问题还是自己痛苦的思考出来的比较实用 别让别人告诉你怎么思考。
人生没有意义！
为什么要想这个沉重的话题呢。 每一个人都可以去想去思考这个topic， 不需要太多的知识 不需要太多的背景， 不会被几个大头名词：存在主意， experience machine 被吓跑， 只要我努力去想不停的去想 我能穷尽所有别人想过的主意。 但是我还是没有能想到人生的意义是什么。 好像是龙应台在被追问到人生的意义的时候：
“请问人生的意义是什么？ 请诚实作答， 不许说谎！”
“我思考了这个问题很久， 我现在可以很负责任的告诉你， 人生没有意义”
我为什么不马上自杀？
人生的意义这个问题当然是重要的， 如果人生没有意义 我为什么还要活着。 就算我是含着金勺子出生（当然我不是，或者生命就是我最宝贵的礼物？） 人生总是要经历一些苦的。 每一个正常人都会在生命的某一个时刻想要自杀。 就好像肖申克救赎里 red 说的“every man got his weakest point” 。 那么我为什么不赶紧自杀 省的浪费地球的资源？
会有转机么？人类已经思考这个问题几千年了 （也许更久）， 也没有想出个所以然来 。我很喜欢加缪把这个问题提高到了哲学的最高的地位： 我为什么不选择自杀？ 至于唯心还是唯物， 牛顿还是爱因斯坦， 杨过还是张无忌 这个都是在我选择不自杀的之后要烦恼的问题了。
看来在我有生之年是不会有转机了， 看来不会在2012 突然有神降临 给我指明出路 告诉我人生的意义 让我为之奋斗！
还是加缪在自己哲学随记中提到了西西弗斯的神话， 勇敢的对生活说 “是” 就是对人生的荒诞性的奋起反抗， 人生的意义也体现出来了。 说实话， 我听着这句话好半天， 我有种想哭的冲动， 或者是我有种该哭的冲动 ， 隐约好像是正理 但是我其实还是没有看懂。 豆瓣上有人说看到西西弗斯这段的时候嚎啕大哭。 我真为这位仁兄或者仁姐汗颜， 你丫是真懂了么！ 不是说我嫉妒别人境界高能看懂， 只是身边有太多这种例子。
少年不识愁滋味 欲赋新词强作愁 如今尝尽愁 欲说还休 。 （说的太好了！）
扯远了， 总是加缪也没有给我我想要的答案。
好像“为何生” 总是和 “死之后” 联系在一起的。 小的时候常常陷入恐惧之中，每每想到人死之后的感觉， 我觉得应该是和睡着了但不做梦的感觉差不多吧 ， 那种和现实的彻底的隔断让我感到一种莫名的孤独和寒冷 。后来我才知道聪明的人已经发明了宗教。 这正是个好东西， 赋予了人类生命的价值。 给了我一个人生意义的答案。 等等！ 谁给我的？ 还不是人类自己给自己的？ 这就好像是保护自己的一种机制 每每思考为什么不去自杀， 生命还值不值得去过 总是有几个人大叫一声然后就去实践去了。 宗教总是告诉我们 现世的意义在于它决定了你的后世！或者是天堂地狱 或者是轮回涅槃。 宗教特别对自杀的人毫不留情， 其原因也就是因为它是一种保护机制。 stop thinking!!!! 我为什么要停止思考 ，作为一个人类我有特权是思考这个问题（别跟我说子非鱼什么的） 。 也正是因为我是人类我才会折磨自己思考这个没有答案的问题。 宗教不是最终的答案 尽管它很聪明 我很喜欢帕斯卡的务实的逻辑
1。 信上帝 结果有上帝： 天堂 无限开心
2. 不信上帝 结果有上帝： 地狱 无限悲哀
3. 不信上帝 结果没上帝 = 信上帝 结果没上帝 = 不疼不痒
所以人应该信上帝 。
看上去多么美好的逻辑 其实有两个巨大缺陷
1. 如果因为这种逻辑信上帝 那是真信么？
2. 这种理论同样适用于任何神 ， 那么那个宗教才是“正确的”. 事实上大部分宗教的神都有排他性。
季羡林说人生的意义在于承前启后， 也许我的人生没有意义， 但是我不能否定我们的后世的人生没有意义 所以我要繁殖？ 我要活着？ 但是我一点都不关心我死了之后谁还传着我的DNA 我的子孙还会不会被神带去天堂。 我想知道的是 我的意义是什么！ 我想知道我为什么活着！ 我对人类和整个宇宙都有一种悲观的态度 。 且不说当代人活的就好像自己是最后一代一样去虐待地球母亲 。 我觉得人类总是要灭亡的， 人类就好像是在烂泥里打滚的猪一样瞎折腾。 抱着这种信念 人生就更没有意义啦！
我觉得人生的目的就是没有！ 突然我想到了那句广告词， “人生就像旅行 不在乎目的地 而在于沿途的风光”。 多么巧妙的而又深刻的对比！ 旅行也是一种经历 没有目的地 重要的是用心感受沿途的风景。 我甚至觉得人生就是人进入了黑客帝国那种 experience machine (EM) 一样， 在没有进入em之前 有人向我推荐了它 就好像豆瓣上推荐读书一样。 em的说明书上说的这段旅程没有任何意义 而且天上一日 地上十年 所以等我出来的时候 才过了一个多星期。 多好啊。 我就抱着这样的期盼未知的心态进入了em。 选择了标准的配置 出生在了地球上 ， 与此同时其他的60亿人也同时在线 一起在em中。 我甚至觉得em之外的生活是一种衣食无忧 科技高度发达的社会 能源无穷无尽 所有定理都证完了 所有方程都解决了， 人们活的太无聊了 才会发明出这种em这个机器解闷的。 但是问题又来了！ em中的生活没有意义 em之外的生活有没有意义对我现在的状态毫无关系！ 唯一的好处可能是对生活的豁达 如果我相信人死了之后就从em中醒来 那我就在不怕死了 我间接的达到了一种佛家的一切皆空的金刚经的境界。
但是我还是没有想出我为什么不马上自杀。 绝不是习惯了的原因， 我习惯活着了。 所以我就要活着？ 当痛苦累积到一定程度的时候 我绝对会打破这个习惯！ （这里引用加缪的思想）。
我想啊想啊想啊 就是没有结果， 我希望我能想出一个积极的人生意义 让我为之奋斗。。看来是不太可能了 。
尼采让我成为超人。 但是我这短短的人生那来的时间去那样折磨自己啊。
稻盛和夫在《活法》一书中让我百分百的抓紧一切时间努力 这样在死的时候就能成为一个比呱呱坠地的时候更好的灵魂。 如果我死了就好像长眠一样 灵魂肉体都不复存在 那我就算变成了一个更好的灵魂又怎么样呢！
我就是想不出一个答案！ 也许这就是人的烦恼吧 因为是人才会想这个问题。 但是想不出这个问题的答案 活着还能自称是人么？ 我也怕想出一个完全消极的意义， 没有意义总比让我天天扔雪球的意义来的好些。。。 或者说如果天天扔雪球就是我人生的终极意义那我也会过的很开心？
今天晚上看 肖申克的救赎 突然想到 andy 为什么要越狱。 在监狱里终老一生 和在太平洋小岛上终老一生 在人生的意义上有什么不同么。 我不关心对别人的意义是否不同 我不关心andy是否也顺带救赎了red 唤醒了其他的凡人。 我关心的只是 如果我是andy 我会越狱么? 我当然会 我傻么 我才不要为别人背黑锅。 我想andy之前有条件而没有越狱是因为他认为他对自己妻子的死有一定责任 因为他不善于表达 。 后来red的开导 加上2个月的in the hole 禁闭 他才摆脱了思想上的包袱 去追求自己想要的人生吧。在监狱中过一生和在小岛上过一生 最大的不同在于自由 在于快乐 在于自己选择了自己想要的人生 而不是过着别人强加给我的生活。 他隐忍了20年 挖了20年不曾放弃自己 不曾放弃希望 爬过500yards的粪管道 这都是概括了一切艰难困苦
但是在andy开车 迎着风 去自己心中的小岛的时候 他一定是极度快乐的 就那一刻真实的快乐就值得！
对啊 人生在世最重要的就是快乐啊 这么简单的道理 ！ 诺贝尔奖得主问自己儿子为什么活着 他小儿子很干净的回答道“好玩 ” 。 就是快乐啊 ！ 人生在世 谁没有想过 如果我能怎么怎么 那我一定是世界上最幸福的人。 那就勇敢的去做啊！ 成为自己想成为的人 过自己想过的生活 让自己充实快乐 这就是旅行的意义 我认为也就是人生的意义 。 也许有人说我低俗 目光短浅 然后想用佛法一切皆空教化我。 对不起 我目前的境界就是这样的 我还会去想 但是目前也就告一段落了
我想出来的人生意义就是去成为自己心中想成为的那个人 过上自己心中期望的生活 让自己真正的快乐 生活的理想就是理想的生活。
note： 这篇东西本来就是写给自己看的 如果您有任何想法 请告诉我， 谁知道您的一句无心之言 会不会给我带来无尽的启发？ 对您来说也是无尽的福报了。
我没有回头去整理 过一阵子我会回来做这件事情。
如果您有耐心读完 那么愿您有美好的一生
如果您没有耐心读完 那么您也没有损失什么 毕竟仁见仁 智见智 人生的意义这种问题还是自己痛苦的思考出来的比较实用 别让别人告诉你怎么思考。
Monday, November 19, 2012
compile C++ in terminal.
1. use commands such as, pwd, ls, cd .... into the corresponding folder.
2. an example:
g++ -o main.o a.cpp b.cpp c.cpp main.cpp -lgsl -lgslcblas
make sure to include all .cpp,
-lgsl -lgslcblas in case of using gsl library.
3. ./main.o
an easier way of doing this:
write a batch.txt file including all necessary commands.
in terminal, type in: source batch.txt
2. an example:
g++ -o main.o a.cpp b.cpp c.cpp main.cpp -lgsl -lgslcblas
make sure to include all .cpp,
-lgsl -lgslcblas in case of using gsl library.
3. ./main.o
an easier way of doing this:
write a batch.txt file including all necessary commands.
in terminal, type in: source batch.txt
get rid of "deprecated conversion from constant string to char* " warning
add "-Wno-write-strings".
get this idea from the following link:
http://stackoverflow.com/questions/59670/how-to-get-rid-of-deprecated-conversion-from-string-constant-to-char-warnin
get this idea from the following link:
http://stackoverflow.com/questions/59670/how-to-get-rid-of-deprecated-conversion-from-string-constant-to-char-warnin
Subscribe to:
Posts (Atom)