2008年2月29日星期五

区间的随机划分

描述数学问题的时候,自然语言很容易有二义性。在叙述随机问题的时候,尤其是这样。比较著名的例子是Bertrand paradox。在一个空间上的某种分布,映射到另一个空间上以后就成了另一种分布。

昨天上课走神的时候,我想到了一个区间的随机划分问题。给定[0,1]区间,给定正整数n,现在要把[0,1]区间划分成n段,使得划分具有某种随机的特性。这不是随机划分的准确描述,我的问题恰恰就是,如何准确描述随机划分,以避免发生类似的Bertrand paradox?

根据直觉,我和同学给出了两种候选的随机划分方案,都是构造性的。
方案一:生成n-1个独立的,服从U[0,1]分布的随机变量x_1,...,x_(n-1),令他们的顺序统计量为y_1,...,y_(n-1),补充定义y_0=0,y_n=1,则{[y_i,y_(i+1)],i=0,...,n-1}是一个随机划分。
方案二:生成n个独立的,服从U[0,1]分布的随机变量x_1,...,x_n,记s为他们的和,令y_i=(x_1+...+x_i)/s,i=1,...,n,补充定义y_0=0,则{[y_i,y_(i+1)],i=0,...,n-1}是一个随机划分。

接下来,我们就要回答,这两种方案是否得到相同的随机划分?
要回答这个问题,我们首先要定义什么叫做两个随机划分方案等价。最直观的,可以定义为他们产生的分点的联合密度函数几乎处处相同。我们算了一下,对于n=2的情形,上述两种方案不等价。事实上,n=2时只有一个分点,也就是要比较两个一维随机变量的密度函数。方案一的结果显然是均匀分布,方案二粗略看来也应该是均匀的,很对称呀,但其实不然,老老实实计算x1/(x1+x2)的分布函数,发现结果真的不是均匀分布。

我们发现,虽然两种方案的得到的分点联合密度不同,但是可以算出来小区间长的期望都是1/n,而且每一种方案的小区间长都服从相同的分布,只不过两种方案的分布不同。受到这一点启发,我们给出了随机划分的一个准确定义(类似方案二):
如果非负数x1+...+xn=1,且x1,...,xn服从相同的分布F,则称x1,...,xn是[0,1]的F随机划分。
可以证明上述两个方案都是随机划分,划分的分布函数F也可以求出来
方案一的是多项式函数,方案二的是有理函数。计算过程和结果的具体形式用TeX写更好看些,以后贴图吧。

这样定义两个随机划分等价就水到渠成了:当且进当二者的分布函数相同。

2008年2月28日星期四

海内 记事本 快捷键保存的GreaseMonkey脚本

以前习惯用Gmail草稿当作记事本,缺点是加载那么多脚本比较笨重,本来要记或者要查的事情很简单,打开却要打开半天,打开后搞的浏览器很疲惫。
自从海内记事本上线后,我一直用它替代Gmail的这个功能。唯一不爽的就是Ctrl+S不是保存记事本的快捷键,每次一按,就弹出一个窗口要保存网页的HTM了,很囧。昨天晚上我终于不能忍了,加了一个GreaseMonky脚本
YUI里面没有找到相关的组合键事件的API,索性手动判断了,实现起来也不太复杂,处理好冒泡终止就好了。
P.S.做的过程中发现openjs有现成的shortcut工具挺不错的。

2008年2月24日星期日

PPC+GPS bluetooth+Google Map实践

去爬山很重要的一点是知道自己在什么地方,gps定位不可少。去年年底买了gps蓝牙模块,软件一直没搞好,今天终于搞定了。
实验环境~
PPC:Qtek S200,大陆叫多普达830
GPS bluetooth:Holux m-1000
GPS software:
gpsgate,用来让多个gps客户端程序共享一个gps信号输入设备,相当于网关或交换机
google map,可以看卫星图,很直观,需要能上互联网,因为卫星图片是从Google网站上动态加载的
这两个软件都可以从网上下载到cab安装文件
实验步骤~
1、打开holux开关,等到橙色的灯开始闪烁时,表明已经找到gps卫星了。
2、打开PPC的蓝牙,搜索设备,找到holux。只需添加一次,以后就不用每次添加了。
3、启动gpsgate,在输入的tab里,选择GPS Bluetooth,找到holux,然后选择串行端口服务,确定。这时gpsgate图标变成绿色,表明gpsgate正确收到holux的信号输入。
3、在gpsgate输出tab中,添加Virture Com/nmea,高级选项,删除com3端口(如果有的话),然后添加虚拟端口com3,确定。这时提示com3 running ok。
4、启动Google Map,选项,gps,手动设置为com3/4800,启动gps,显示我的位置。
实验结论~
能够看到自己所在的位置的卫星图,是不是很科幻?不,很现实,而且很爽!
ozi是绿野论坛上的人比较推荐的一款软件,可以自己定制地图,画路标,显示经纬海拔,比较专业。以后慢慢研究~

2008年2月21日星期四

erlex : play erlang with flex

昨天完成了一个范例小程序,可以用来群聊。客户端是浏览器里的Flash,服务器端是erlang写的脚本。
基本框架是服务器监听两个端口,8765替代80用来让浏览器通过http协议装载html和swf文件,2345端口是原生Socket通信,负责聊天数据的推拉。
先来看看http的实现吧,在erlang脚本中只需要一句话:
inets:start(httpd, [{server_name,"erlex"},{bind_address, "59.66.121.94"},{port, 8765},{server_root,"www"}).
一个httpd就跑起来了(不用找Apache),然后把它放到后台去不用管了。这里server_root给的是相对路径,所有html,swf文件都在里面。
主要来看原生Socket的通讯。
1、客户端,熟悉Java的同志一定对ActionScript有一见如故的感觉。全部代码可以去
http://code.google.com/p/erlex/
看,我已经check in了,这里简单点一句
private function send(content:String):void{
    var buf:ByteArray = new ByteArray();
    buf.writeByte(0x02);
    buf.writeUTF(content);
    socket.writeBytes(buf,0,buf.length);
}
开了一段字节数组,先向里面丢了一个0x02,表示这个数据包是客户端说的话,后面是一个字符串,头两个字节表示跟着的字符数组的长度,跟着的字符数组是字符串的UTF8表示。socket在write之后应该flush一下,目前问题不大。
2、服务器端,大多数同志可能对erlang不是很熟悉,我多讲几句吧。
因为要支持多个客户端同时连接,因此用到了erlang的拿手好戏:并发编程。我们为每一个Socket连接准备一个erlang的process(可以理解为Java的线程,但是相当轻量级,官方测试数据证明了erlang这方面的性能),同时准备一个总线process,做传递消息枢纽。
par_connect(Listen)->
    case gen_tcp:accept(Listen) of
    {ok, Socket} ->
        spawn(fun() -> par_connect(Listen) end),
        loop(Socket);
    end.
上面的函数用来捕获一个TCP连接,在loop中处理,并启动一个新process,执行同样的par_connect函数,这是一种并行递归。
loop(Socket)->
    receive
        {tcp, Socket, Bin} ->
            [H1,_,_|T1] = binary_to_list(Bin),
            case H1 of
            2 ->
                bus ! {broadcast, self(), T1},
                loop(Socket);
    end.
这个函数所在的process可能接收到各种消息,其中{tcp, Socket, Bin}是收到一个TCP数据包(由原子tcp确定),Bin中存放的是数据包的TCP正文二进制流。我们先把它转换成字节数组binary_to_list,再模式匹配[H1,_,_|T1],得到H1是第一个字节,表示数据包的用途,2的意思就是上面0x02,然后用,_,_忽略后面两个字节(如果在ActionScript中用writeUTFBytes就没有这个麻烦),用T1装字节数组后面的内容。然后通过
bus ! {broadcast, self(), T1},
发给总线。其中bus在程序开始注册为总线process,self()表示当前process id,可以用来确定说话人的身份。
值得注意的是最后又调用了loop方法似乎是递归,很快要堆栈溢出的,不过erlang编译器把他当作迭代调用,这是erlang风格,erlang有很多很特别的风格。我认为最酷的还是process间通信的风格,发送消息用!加term,收到消息用recieve加模式匹配,和分布式算法的伪代码描述一模一样!

总线查出说话人的名字,并把他说的话发给所有process
[{_,SpeakerName}|_] = ets:lookup(TableID,SpeakerPid),
lists:foreach(fun({Pid,Name}) -> Pid ! {send, SpeakerName, Content} end , ets:tab2list(TableID))
这里用到了list的遍历、闭包以及erlang数据表ets的操作。
loop函数中再加一个recieve子句
{send, SpeakerName, Content}->
    ok = gen_tcp:send(Socket, list_to_binary(SpeakerName++" says: "++Content)),
这就发回给客户端了,ActionScript中这样接收:
socket.addEventListener( ProgressEvent.SOCKET_DATA, onSocketData );
其中
private function onSocketData( event:ProgressEvent ):void {
    var data:String = socket.readUTFBytes(socket.bytesAvailable);
    history.text=history.text+"\n"+data.toString();
}
history是多行文本框。

事实上,利用ets可以避免使用总线,只是考虑多个process间不共享存储的分布式场景,才用的。erlang为分布式计算而生。